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