unscrambler.py

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