unscrambler.py

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