unscrambler.py

   1 #!/usr/bin/env python3
   2
   3 import logging
   4 from typing import Dict
   5
   6 import config
   7 import decorator_utils
   8 import list_utils
   9
  10 cfg = config.add_commandline_args(
  11     f'Unscramble! ({__file__})', 'A fast word unscrambler.'
  12 )
  13 cfg.add_argument(
  14     "--unscramble_indexfile",
  15     help="Path to a file of signature -> word index.",
  16     metavar="FILENAME",
  17     default="/usr/share/dict/sparse_index",
  18 )
  19
  20 logger = logging.getLogger(__name__)
  21
  22 letters_bits = 32
  23 letters_mask = 2 ** letters_bits - 1
  24
  25 fprint_bits = 52
  26 fprint_mask = (2 ** fprint_bits - 1) << letters_bits
  27
  28 fprint_feature_bit = {
  29     'e': 0,
  30     'i': 2,
  31     'a': 4,
  32     'o': 6,
  33     'r': 8,
  34     'n': 10,
  35     't': 12,
  36     's': 14,
  37     'l': 16,
  38     'c': 18,
  39     'u': 20,
  40     'p': 22,
  41     'm': 24,
  42     'd': 26,
  43     'h': 28,
  44     'y': 30,
  45     'g': 32,
  46     'b': 34,
  47     'f': 36,
  48     'v': 38,
  49     'k': 40,
  50     'w': 42,
  51     'z': 44,
  52     'x': 46,
  53     'q': 48,
  54     'j': 50,
  55 }
  56
  57 letter_sigs = {
  58     'a': 1789368711,
  59     'b': 3146859322,
  60     'c': 43676229,
  61     'd': 3522623596,
  62     'e': 3544234957,
  63     'f': 3448207591,
  64     'g': 1282648386,
  65     'h': 3672791226,
  66     'i': 1582316135,
  67     'j': 4001984784,
  68     'k': 831769172,
  69     'l': 1160692746,
  70     'm': 2430986565,
  71     'n': 1873586768,
  72     'o': 694443915,
  73     'p': 1602297017,
  74     'q': 533722196,
  75     'r': 3754550193,
  76     's': 1859447115,
  77     't': 1121373020,
  78     'u': 2414108708,
  79     'v': 2693866766,
  80     'w': 748799881,
  81     'x': 2627529228,
  82     'y': 2376066489,
  83     'z': 802338724,
  84 }
  85
  86
  87 class Unscrambler(object):
  88     sigs = []
  89     words = []
  90
  91     def __init__(self):
  92         pass
  93
  94     # 52 bits
  95     @staticmethod
  96     def _compute_word_fingerprint(word: str, population) -> int:
  97         fp = 0
  98         for pair in sorted(population.items(), key=lambda x: x[1], reverse=True):
  99             letter = pair[0]
 100             if letter in fprint_feature_bit:
 101                 count = pair[1]
 102                 if count > 3:
 103                     count = 3
 104                 shift = fprint_feature_bit[letter]
 105                 s = count << shift
 106                 fp |= s
 107         return fp << letters_bits
 108
 109     # 32 bits
 110     @staticmethod
 111     def _compute_word_letter_sig(letter_sigs, word: str, population) -> int:
 112         sig = 0
 113         for pair in sorted(population.items(), key=lambda x: x[1], reverse=True):
 114             letter = pair[0]
 115             if letter not in letter_sigs:
 116                 continue
 117             s = letter_sigs[letter]
 118             count = pair[1]
 119             if count > 1:
 120                 s <<= count
 121                 s |= count
 122             s &= letters_mask
 123             sig ^= s
 124         length = len(word)
 125         if length > 31:
 126             length = 31
 127         sig ^= length << 8
 128         sig &= letters_mask
 129         return sig
 130
 131     # 52 + 32 bits
 132     @staticmethod
 133     @decorator_utils.memoized
 134     def compute_word_sig(word: str) -> int:
 135         """Given a word, compute its signature for subsequent lookup
 136         operations.  Signatures are computed based on the letters in
 137         the word and their frequencies.  We try to cluster "similar"
 138         words close to each other in the signature space.
 139
 140         >>> train = Unscrambler.compute_word_sig('train')
 141         >>> train
 142         23178969883741
 143
 144         >>> retain = Unscrambler.compute_word_sig('retrain')
 145         >>> retain
 146         24282502197479
 147
 148         >>> retain - train
 149         1103532313738
 150
 151         """
 152         population = list_utils.population_counts(word)
 153         fprint = Unscrambler._compute_word_fingerprint(word, population)
 154         letter_sig = Unscrambler._compute_word_letter_sig(letter_sigs, word, population)
 155         assert fprint & letter_sig == 0
 156         sig = fprint | letter_sig
 157         return sig
 158
 159     @staticmethod
 160     def repopulate(
 161         letter_sigs: Dict[str, int],
 162         dictfile: str = '/usr/share/dict/words',
 163         indexfile: str = '/usr/share/dict/sparse_index',
 164     ) -> None:
 165         """Before calling this method, change letter_sigs from the default above
 166         unless you want to populate the same exact files."""
 167
 168         words_by_sigs = {}
 169         seen = set()
 170         with open(dictfile, "r") as f:
 171             for word in f:
 172                 word = word.replace('\n', '')
 173                 word = word.lower()
 174                 sig = Unscrambler.compute_word_sig(letter_sigs, word)
 175                 logger.debug("%s => 0x%x" % (word, sig))
 176                 if word in seen:
 177                     continue
 178                 seen.add(word)
 179                 if sig in words_by_sigs:
 180                     words_by_sigs[sig] += ",%s" % word
 181                 else:
 182                     words_by_sigs[sig] = word
 183         with open(indexfile, 'w') as f:
 184             for sig in sorted(words_by_sigs.keys()):
 185                 word = words_by_sigs[sig]
 186                 print(f'0x{sig:x}+{word}', file=f)
 187
 188     @staticmethod
 189     def lookup(word: str, *, include_fuzzy_matches=False) -> Dict[str, bool]:
 190         """Looks up a potentially scrambled word optionally including near
 191         "fuzzy" matches.
 192
 193         >>> Unscrambler.lookup('eanycleocipd', include_fuzzy_matches=False)
 194         {'encyclopedia': True}
 195
 196         """
 197         sig = Unscrambler.compute_word_sig(word)
 198         return Unscrambler.lookup_by_sig(
 199             sig, include_fuzzy_matches=include_fuzzy_matches
 200         )
 201
 202     @staticmethod
 203     def lookup_by_sig(sig, *, include_fuzzy_matches=False) -> Dict[str, bool]:
 204         """Looks up a word that has already been translated into a signature by
 205         a previous call to Unscrambler.compute_word_sig.  Optionally returns
 206         near "fuzzy" matches.
 207
 208         >>> sig = Unscrambler.compute_word_sig('sunepsapetuargiarin')
 209         >>> sig
 210         18491949645300288339
 211
 212         >>> Unscrambler.lookup_by_sig(sig, include_fuzzy_matches=True)
 213         {'pupigerous': False, 'pupigenous': False, 'unpurposing': False, 'superpurgation': False, 'unsupporting': False, 'superseptuaginarian': True, 'purpurogallin': False, 'scuppaug': False, 'purpurigenous': False, 'purpurogenous': False, 'proppage': False}
 214
 215         """
 216         # Cache the index; it doesn't change and this may be called
 217         # more than once.
 218         if len(Unscrambler.sigs) == 0:
 219             if 'unscramble_indexfile' in config.config:
 220                 indexfile = config.config['unscramble_indexfile']
 221             else:
 222                 indexfile = "/usr/share/dict/sparse_index"
 223             with open(indexfile, 'r') as rf:
 224                 lines = rf.readlines()
 225             for line in lines:
 226                 line = line[:-1]
 227                 (fsig, word) = line.split('+')
 228                 fsig = int(fsig, 16)
 229                 Unscrambler.sigs.append(fsig)
 230                 Unscrambler.words.append(word)
 231
 232         ret = {}
 233         (exact, location) = list_utils.binary_search(Unscrambler.sigs, sig)
 234         start = location - 5
 235         if start < 0:
 236             start = 0
 237         end = location + 6
 238         if end > len(Unscrambler.words):
 239             end = len(Unscrambler.words)
 240
 241         for x in range(start, end):
 242             word = Unscrambler.words[x]
 243             fsig = Unscrambler.sigs[x]
 244             if include_fuzzy_matches is True or (fsig == sig):
 245                 ret[word] = fsig == sig
 246         return ret
 247
 248
 249 #
 250 # To repopulate, change letter_sigs and then call Unscrambler.repopulate.
 251 # See notes above.  See also ~/bin/unscramble.py --populate_destructively.
 252 #
 253
 254
 255 if __name__ == "__main__":
 256     import doctest
 257
 258     doctest.testmod()