unscrambler.py

   1 #!/usr/bin/env python3
   2
   3 import logging
   4 from typing import Dict, Mapping
   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     """A class that unscrambles words quickly by computing a signature
  89     (sig) for the word based on its position independent letter
  90     population and then using a pregenerated index to look up known
  91     words the same set of letters.
  92
  93     Note that each instance of Unscrambler caches its index to speed
  94     up lookups number 2..N; careless reinstantiation will by slower.
  95
  96     Sigs are designed to cluster similar words near each other so both
  97     lookup methods support a "fuzzy match" argument that can be set to
  98     request similar words that do not match exactly in addition to any
  99     exact matches.
 100
 101     """
 102
 103     def __init__(self):
 104         # Cached index per instance.
 105         self.sigs = []
 106         self.words = []
 107
 108         if 'unscramble_indexfile' in config.config:
 109             indexfile = config.config['unscramble_indexfile']
 110         else:
 111             indexfile = "/usr/share/dict/sparse_index"
 112
 113         with open(indexfile, 'r') as rf:
 114             lines = rf.readlines()
 115         for line in lines:
 116             line = line[:-1]
 117             (fsig, word) = line.split('+')
 118             fsig = int(fsig, 16)
 119             self.sigs.append(fsig)
 120             self.words.append(word)
 121
 122     # 52 bits
 123     @staticmethod
 124     def _compute_word_fingerprint(
 125         word: str, population: Mapping[str, int]
 126     ) -> int:
 127         fp = 0
 128         for pair in sorted(
 129             population.items(), key=lambda x: x[1], reverse=True
 130         ):
 131             letter = pair[0]
 132             if letter in fprint_feature_bit:
 133                 count = pair[1]
 134                 if count > 3:
 135                     count = 3
 136                 shift = fprint_feature_bit[letter]
 137                 s = count << shift
 138                 fp |= s
 139         return fp << letters_bits
 140
 141     # 32 bits
 142     @staticmethod
 143     def _compute_word_letter_sig(
 144         letter_sigs: Mapping[str, int],
 145         word: str,
 146         population: Mapping[str, int],
 147     ) -> int:
 148         sig = 0
 149         for pair in sorted(
 150             population.items(), key=lambda x: x[1], reverse=True
 151         ):
 152             letter = pair[0]
 153             if letter not in letter_sigs:
 154                 continue
 155             s = letter_sigs[letter]
 156             count = pair[1]
 157             if count > 1:
 158                 s <<= count
 159                 s |= count
 160             s &= letters_mask
 161             sig ^= s
 162         length = len(word)
 163         if length > 31:
 164             length = 31
 165         sig ^= length << 8
 166         sig &= letters_mask
 167         return sig
 168
 169     # 52 + 32 bits
 170     @staticmethod
 171     @decorator_utils.memoized
 172     def compute_word_sig(word: str) -> int:
 173         """Given a word, compute its signature for subsequent lookup
 174         operations.  Signatures are computed based on the letters in
 175         the word and their frequencies.  We try to cluster "similar"
 176         words close to each other in the signature space.
 177
 178         >>> train = Unscrambler.compute_word_sig('train')
 179         >>> train
 180         23178969883741
 181
 182         >>> retain = Unscrambler.compute_word_sig('retrain')
 183         >>> retain
 184         24282502197479
 185
 186         >>> retain - train
 187         1103532313738
 188
 189         """
 190         population = list_utils.population_counts(word)
 191         fprint = Unscrambler._compute_word_fingerprint(word, population)
 192         letter_sig = Unscrambler._compute_word_letter_sig(
 193             letter_sigs, word, population
 194         )
 195         assert fprint & letter_sig == 0
 196         sig = fprint | letter_sig
 197         return sig
 198
 199     @staticmethod
 200     def repopulate(
 201         letter_sigs: Dict[str, int],
 202         dictfile: str = '/usr/share/dict/words',
 203         indexfile: str = '/usr/share/dict/sparse_index',
 204     ) -> None:
 205         """Before calling this method, change letter_sigs from the default above
 206         unless you want to populate the same exact files.
 207
 208         """
 209         words_by_sigs = {}
 210         seen = set()
 211         with open(dictfile, "r") as f:
 212             for word in f:
 213                 word = word.replace('\n', '')
 214                 word = word.lower()
 215                 sig = Unscrambler.compute_word_sig(letter_sigs, word)
 216                 logger.debug("%s => 0x%x" % (word, sig))
 217                 if word in seen:
 218                     continue
 219                 seen.add(word)
 220                 if sig in words_by_sigs:
 221                     words_by_sigs[sig] += ",%s" % word
 222                 else:
 223                     words_by_sigs[sig] = word
 224         with open(indexfile, 'w') as f:
 225             for sig in sorted(words_by_sigs.keys()):
 226                 word = words_by_sigs[sig]
 227                 print(f'0x{sig:x}+{word}', file=f)
 228
 229     def lookup(
 230         self, word: str, *, include_fuzzy_matches: bool = False
 231     ) -> Dict[str, bool]:
 232         """Looks up a potentially scrambled word optionally including near
 233         "fuzzy" matches.
 234
 235         >>> u = Unscrambler()
 236         >>> u.lookup('eanycleocipd', include_fuzzy_matches=False)
 237         {'encyclopedia': True}
 238
 239         """
 240         sig = Unscrambler.compute_word_sig(word)
 241         return self.lookup_by_sig(
 242             sig, include_fuzzy_matches=include_fuzzy_matches
 243         )
 244
 245     def lookup_by_sig(
 246         self, sig: int, *, include_fuzzy_matches: bool = False
 247     ) -> Dict[str, bool]:
 248         """Looks up a word that has already been translated into a signature by
 249         a previous call to Unscrambler.compute_word_sig.  Optionally returns
 250         near "fuzzy" matches.
 251
 252         >>> sig = Unscrambler.compute_word_sig('sunepsapetuargiarin')
 253         >>> sig
 254         18491949645300288339
 255
 256         >>> u = Unscrambler()
 257         >>> u.lookup_by_sig(sig, include_fuzzy_matches=True)
 258         {'pupigerous': False, 'pupigenous': False, 'unpurposing': False, 'superpurgation': False, 'unsupporting': False, 'superseptuaginarian': True, 'purpurogallin': False, 'scuppaug': False, 'purpurigenous': False, 'purpurogenous': False, 'proppage': False}
 259
 260         """
 261         ret = {}
 262         (exact, location) = list_utils.binary_search(self.sigs, sig)
 263         start = location - 5
 264         if start < 0:
 265             start = 0
 266         end = location + 6
 267         if end > len(self.words):
 268             end = len(self.words)
 269
 270         for x in range(start, end):
 271             word = self.words[x]
 272             fsig = self.sigs[x]
 273             if include_fuzzy_matches is True or (fsig == sig):
 274                 ret[word] = fsig == sig
 275         return ret
 276
 277
 278 #
 279 # To repopulate, change letter_sigs and then call Unscrambler.repopulate.
 280 # See notes above.  See also ~/bin/unscramble.py --populate_destructively.
 281 #
 282
 283
 284 if __name__ == "__main__":
 285     import doctest
 286
 287     doctest.testmod()