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(word: str, population: Mapping[str, int]) -> int:
 125         fp = 0
 126         for pair in sorted(population.items(), key=lambda x: x[1], reverse=True):
 127             letter = pair[0]
 128             if letter in fprint_feature_bit:
 129                 count = pair[1]
 130                 if count > 3:
 131                     count = 3
 132                 shift = fprint_feature_bit[letter]
 133                 s = count << shift
 134                 fp |= s
 135         return fp << letters_bits
 136
 137     # 32 bits
 138     @staticmethod
 139     def _compute_word_letter_sig(
 140         letter_sigs: Mapping[str, int],
 141         word: str,
 142         population: Mapping[str, int],
 143     ) -> int:
 144         sig = 0
 145         for pair in sorted(population.items(), key=lambda x: x[1], reverse=True):
 146             letter = pair[0]
 147             if letter not in letter_sigs:
 148                 continue
 149             s = letter_sigs[letter]
 150             count = pair[1]
 151             if count > 1:
 152                 s <<= count
 153                 s |= count
 154             s &= letters_mask
 155             sig ^= s
 156         length = len(word)
 157         if length > 31:
 158             length = 31
 159         sig ^= length << 8
 160         sig &= letters_mask
 161         return sig
 162
 163     # 52 + 32 bits
 164     @staticmethod
 165     @decorator_utils.memoized
 166     def compute_word_sig(word: str) -> int:
 167         """Given a word, compute its signature for subsequent lookup
 168         operations.  Signatures are computed based on the letters in
 169         the word and their frequencies.  We try to cluster "similar"
 170         words close to each other in the signature space.
 171
 172         >>> train = Unscrambler.compute_word_sig('train')
 173         >>> train
 174         23178969883741
 175
 176         >>> retain = Unscrambler.compute_word_sig('retrain')
 177         >>> retain
 178         24282502197479
 179
 180         >>> retain - train
 181         1103532313738
 182
 183         """
 184         population = list_utils.population_counts(word)
 185         fprint = Unscrambler._compute_word_fingerprint(word, population)
 186         letter_sig = Unscrambler._compute_word_letter_sig(letter_sigs, word, population)
 187         assert fprint & letter_sig == 0
 188         sig = fprint | letter_sig
 189         return sig
 190
 191     @staticmethod
 192     def repopulate(
 193         letter_sigs: Dict[str, int],
 194         dictfile: str = '/usr/share/dict/words',
 195         indexfile: str = '/usr/share/dict/sparse_index',
 196     ) -> None:
 197         """Before calling this method, change letter_sigs from the default above
 198         unless you want to populate the same exact files.
 199
 200         """
 201         words_by_sigs = {}
 202         seen = set()
 203         with open(dictfile, "r") as f:
 204             for word in f:
 205                 word = word.replace('\n', '')
 206                 word = word.lower()
 207                 sig = Unscrambler.compute_word_sig(letter_sigs, word)
 208                 logger.debug("%s => 0x%x" % (word, sig))
 209                 if word in seen:
 210                     continue
 211                 seen.add(word)
 212                 if sig in words_by_sigs:
 213                     words_by_sigs[sig] += ",%s" % word
 214                 else:
 215                     words_by_sigs[sig] = word
 216         with open(indexfile, 'w') as f:
 217             for sig in sorted(words_by_sigs.keys()):
 218                 word = words_by_sigs[sig]
 219                 print(f'0x{sig:x}+{word}', file=f)
 220
 221     def lookup(
 222         self, word: str, *, include_fuzzy_matches: bool = False
 223     ) -> Dict[str, bool]:
 224         """Looks up a potentially scrambled word optionally including near
 225         "fuzzy" matches.
 226
 227         >>> u = Unscrambler()
 228         >>> u.lookup('eanycleocipd', include_fuzzy_matches=False)
 229         {'encyclopedia': True}
 230
 231         """
 232         sig = Unscrambler.compute_word_sig(word)
 233         return self.lookup_by_sig(sig, include_fuzzy_matches=include_fuzzy_matches)
 234
 235     def lookup_by_sig(
 236         self, sig: int, *, include_fuzzy_matches: bool = False
 237     ) -> Dict[str, bool]:
 238         """Looks up a word that has already been translated into a signature by
 239         a previous call to Unscrambler.compute_word_sig.  Optionally returns
 240         near "fuzzy" matches.
 241
 242         >>> sig = Unscrambler.compute_word_sig('sunepsapetuargiarin')
 243         >>> sig
 244         18491949645300288339
 245
 246         >>> u = Unscrambler()
 247         >>> u.lookup_by_sig(sig, include_fuzzy_matches=True)
 248         {'pupigerous': False, 'pupigenous': False, 'unpurposing': False, 'superpurgation': False, 'unsupporting': False, 'superseptuaginarian': True, 'purpurogallin': False, 'scuppaug': False, 'purpurigenous': False, 'purpurogenous': False, 'proppage': False}
 249
 250         """
 251         ret = {}
 252         (exact, location) = list_utils.binary_search(self.sigs, sig)
 253         start = location - 5
 254         if start < 0:
 255             start = 0
 256         end = location + 6
 257         if end > len(self.words):
 258             end = len(self.words)
 259
 260         for x in range(start, end):
 261             word = self.words[x]
 262             fsig = self.sigs[x]
 263             if include_fuzzy_matches is True or (fsig == sig):
 264                 ret[word] = fsig == sig
 265         return ret
 266
 267
 268 #
 269 # To repopulate, change letter_sigs and then call Unscrambler.repopulate.
 270 # See notes above.  See also ~/bin/unscramble.py --populate_destructively.
 271 #
 272
 273
 274 if __name__ == "__main__":
 275     import doctest
 276
 277     doctest.testmod()