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