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: Dict[int, str] = {}
 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(self, word: str, *, window_size: int = 5) -> Dict[str, bool]:
 222         """Looks up a potentially scrambled word optionally including near
 223         "fuzzy" matches.
 224
 225         >>> u = Unscrambler()
 226         >>> u.lookup('eanycleocipd', window_size=0)
 227         {'encyclopedia': True}
 228
 229         """
 230         sig = Unscrambler.compute_word_sig(word)
 231         return self.lookup_by_sig(sig, window_size=window_size)
 232
 233     def lookup_by_sig(self, sig: int, *, window_size: int = 5) -> Dict[str, bool]:
 234         """Looks up a word that has already been translated into a signature by
 235         a previous call to Unscrambler.compute_word_sig.  Optionally returns
 236         near "fuzzy" matches.
 237
 238         >>> sig = Unscrambler.compute_word_sig('sunepsapetuargiarin')
 239         >>> sig
 240         18491949645300288339
 241
 242         >>> u = Unscrambler()
 243         >>> u.lookup_by_sig(sig)
 244         {'pupigerous': False, 'pupigenous': False, 'unpurposing': False, 'superpurgation': False, 'unsupporting': False, 'superseptuaginarian': True, 'purpurogallin': False, 'scuppaug': False, 'purpurigenous': False, 'purpurogenous': False, 'proppage': False}
 245
 246         """
 247         ret = {}
 248         (exact, location) = list_utils.binary_search(self.sigs, sig)
 249         start = location - window_size
 250         if start < 0:
 251             start = 0
 252         end = location + 1 + window_size
 253         if end > len(self.words):
 254             end = len(self.words)
 255
 256         for x in range(start, end):
 257             word = self.words[x]
 258             fsig = self.sigs[x]
 259             if window_size > 0 or (fsig == sig):
 260                 ret[word] = fsig == sig
 261         return ret
 262
 263
 264 #
 265 # To repopulate, change letter_sigs and then call Unscrambler.repopulate.
 266 # See notes above.  See also ~/bin/unscramble.py --populate_destructively.
 267 #
 268
 269
 270 if __name__ == "__main__":
 271     import doctest
 272
 273     doctest.testmod()