unscrambler.py

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