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