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     def __init__(self, indexfile: Optional[str] = None):
 108         """
 109         Constructs an unscrambler.
 110
 111         Args:
 112             indexfile: overrides the default indexfile location if provided
 113         """
 114
 115         # Cached index per instance.
 116         self.sigs = []
 117         self.words = []
 118
 119         filename = Unscrambler.get_indexfile(indexfile)
 120         with open(filename, 'r') as rf:
 121             lines = rf.readlines()
 122         for line in lines:
 123             line = line[:-1]
 124             (fsig, word) = line.split('+')
 125             isig = int(fsig, 16)
 126             self.sigs.append(isig)
 127             self.words.append(word)
 128
 129     @staticmethod
 130     def get_indexfile(indexfile: Optional[str]) -> str:
 131         """Returns the current indexfile location."""
 132         if indexfile is None:
 133             if 'unscrambler_default_indexfile' in config.config:
 134                 indexfile = config.config['unscrambler_default_indexfile']
 135             else:
 136                 indexfile = "/usr/share/dict/sparse_index"
 137         else:
 138             assert file_utils.file_is_readable(indexfile), f"Can't read {indexfile}"
 139         return indexfile
 140
 141     # 52 bits
 142     @staticmethod
 143     def _compute_word_fingerprint(population: Mapping[str, int]) -> int:
 144         fp = 0
 145         for pair in sorted(population.items(), key=lambda x: x[1], reverse=True):
 146             letter = pair[0]
 147             if letter in fprint_feature_bit:
 148                 count = min(pair[1], 3)
 149                 shift = fprint_feature_bit[letter]
 150                 s = count << shift
 151                 fp |= s
 152         return fp << letters_bits
 153
 154     # 32 bits
 155     @staticmethod
 156     def _compute_word_letter_sig(
 157         lsigs: Mapping[str, int],
 158         word: str,
 159         population: Mapping[str, int],
 160     ) -> int:
 161         sig = 0
 162         for pair in sorted(population.items(), key=lambda x: x[1], reverse=True):
 163             letter = pair[0]
 164             if letter not in lsigs:
 165                 continue
 166             s = lsigs[letter]
 167             count = pair[1]
 168             if count > 1:
 169                 s <<= count
 170                 s |= count
 171             s &= letters_mask
 172             sig ^= s
 173         length = min(len(word), 31)
 174         sig ^= length << 8
 175         sig &= letters_mask
 176         return sig
 177
 178     # 52 + 32 bits
 179     @staticmethod
 180     @decorator_utils.memoized
 181     def compute_word_sig(word: str) -> int:
 182         """Given a word, compute its signature for subsequent lookup
 183         operations.  Signatures are computed based on the letters in
 184         the word and their frequencies.  We try to cluster "similar"
 185         words close to each other in the signature space.
 186
 187         Args:
 188             word: the word to compute a signature for
 189
 190         Returns:
 191             The word's signature.
 192
 193         >>> train = Unscrambler.compute_word_sig('train')
 194         >>> train
 195         23178969883741
 196
 197         >>> retain = Unscrambler.compute_word_sig('retrain')
 198         >>> retain
 199         24282502197479
 200
 201         >>> retain - train
 202         1103532313738
 203
 204         """
 205         population = list_utils.population_counts(word)
 206         fprint = Unscrambler._compute_word_fingerprint(population)
 207         letter_sig = Unscrambler._compute_word_letter_sig(letter_sigs, word, population)
 208         assert fprint & letter_sig == 0
 209         sig = fprint | letter_sig
 210         return sig
 211
 212     @staticmethod
 213     def repopulate(
 214         dictfile: str = '/usr/share/dict/words',
 215         indexfile: str = '/usr/share/dict/sparse_index',
 216     ) -> None:
 217         """
 218         Repopulates the indexfile.
 219
 220         .. warning::
 221
 222             Before calling this method, change letter_sigs from the
 223             default above unless you want to populate the same exact
 224             files.
 225         """
 226         words_by_sigs: Dict[int, str] = {}
 227         seen = set()
 228         with open(dictfile, "r") as f:
 229             for word in f:
 230                 word = word.replace('\n', '')
 231                 word = word.lower()
 232                 sig = Unscrambler.compute_word_sig(word)
 233                 logger.debug("%s => 0x%x", word, sig)
 234                 if word in seen:
 235                     continue
 236                 seen.add(word)
 237                 if sig in words_by_sigs:
 238                     words_by_sigs[sig] += f",{word}"
 239                 else:
 240                     words_by_sigs[sig] = word
 241         with open(indexfile, 'w') as f:
 242             for sig in sorted(words_by_sigs.keys()):
 243                 word = words_by_sigs[sig]
 244                 print(f'0x{sig:x}+{word}', file=f)
 245
 246     def lookup(self, word: str, *, window_size: int = 5) -> Dict[str, bool]:
 247         """Looks up a potentially scrambled word optionally including near
 248         "fuzzy" matches.
 249
 250         Args:
 251             word: the word to lookup
 252             window_size: the number of nearby fuzzy matches to return
 253
 254         Returns:
 255             A dict of word -> bool containing unscrambled words with (close
 256             to or precisely) the same letters as the input word.  The bool
 257             values in this dict indicate whether the key word is an exact
 258             or near match.  The count of entries in this dict is controlled
 259             by the window_size param.
 260
 261         >>> u = Unscrambler()
 262         >>> u.lookup('eanycleocipd', window_size=0)
 263         {'encyclopedia': True}
 264         """
 265         sig = Unscrambler.compute_word_sig(word)
 266         return self.lookup_by_sig(sig, window_size=window_size)
 267
 268     def lookup_by_sig(self, sig: int, *, window_size: int = 5) -> Dict[str, bool]:
 269         """Looks up a word that has already been translated into a signature by
 270         a previous call to Unscrambler.compute_word_sig.  Optionally returns
 271         near "fuzzy" matches.
 272
 273         Args:
 274             sig: the signature of the word to lookup (see :meth:`compute_word_sig`
 275                 to generate these signatures).
 276             window_size: the number of nearby fuzzy matches to return
 277
 278         Returns:
 279             A dict of word -> bool containing unscrambled words with (close
 280             to or precisely) the same letters as the input word.  The bool
 281             values in this dict indicate whether the key word is an exact
 282             or near match.  The count of entries in this dict is controlled
 283             by the window_size param.
 284
 285         >>> sig = Unscrambler.compute_word_sig('sunepsapetuargiarin')
 286         >>> sig
 287         18491949645300288339
 288
 289         >>> u = Unscrambler()
 290         >>> u.lookup_by_sig(sig)
 291         {'pupigerous': False, 'pupigenous': False, 'unpurposing': False, 'superpurgation': False, 'unsupporting': False, 'superseptuaginarian': True, 'purpurogallin': False, 'scuppaug': False, 'purpurigenous': False, 'purpurogenous': False, 'proppage': False}
 292         """
 293         ret = {}
 294         (_, location) = list_utils.binary_search(self.sigs, sig)
 295         start = location - window_size
 296         start = max(start, 0)
 297         end = location + 1 + window_size
 298         end = min(end, len(self.words))
 299
 300         for x in range(start, end):
 301             word = self.words[x]
 302             fsig = self.sigs[x]
 303             if window_size > 0 or (fsig == sig):
 304                 ret[word] = fsig == sig
 305         return ret
 306
 307
 308 #
 309 # To repopulate, change letter_sigs and then call Unscrambler.repopulate.
 310 # See notes above.  See also ~/bin/unscramble.py --populate_destructively.
 311 #
 312
 313
 314 if __name__ == "__main__":
 315     import doctest
 316
 317     doctest.testmod()