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(word: str, 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 = pair[1]
 137                 if count > 3:
 138                     count = 3
 139                 shift = fprint_feature_bit[letter]
 140                 s = count << shift
 141                 fp |= s
 142         return fp << letters_bits
 143
 144     # 32 bits
 145     @staticmethod
 146     def _compute_word_letter_sig(
 147         letter_sigs: Mapping[str, int],
 148         word: str,
 149         population: Mapping[str, int],
 150     ) -> int:
 151         sig = 0
 152         for pair in sorted(population.items(), key=lambda x: x[1], reverse=True):
 153             letter = pair[0]
 154             if letter not in letter_sigs:
 155                 continue
 156             s = letter_sigs[letter]
 157             count = pair[1]
 158             if count > 1:
 159                 s <<= count
 160                 s |= count
 161             s &= letters_mask
 162             sig ^= s
 163         length = len(word)
 164         if length > 31:
 165             length = 31
 166         sig ^= length << 8
 167         sig &= letters_mask
 168         return sig
 169
 170     # 52 + 32 bits
 171     @staticmethod
 172     @decorator_utils.memoized
 173     def compute_word_sig(word: str) -> int:
 174         """Given a word, compute its signature for subsequent lookup
 175         operations.  Signatures are computed based on the letters in
 176         the word and their frequencies.  We try to cluster "similar"
 177         words close to each other in the signature space.
 178
 179         >>> train = Unscrambler.compute_word_sig('train')
 180         >>> train
 181         23178969883741
 182
 183         >>> retain = Unscrambler.compute_word_sig('retrain')
 184         >>> retain
 185         24282502197479
 186
 187         >>> retain - train
 188         1103532313738
 189
 190         """
 191         population = list_utils.population_counts(word)
 192         fprint = Unscrambler._compute_word_fingerprint(word, population)
 193         letter_sig = Unscrambler._compute_word_letter_sig(letter_sigs, word, population)
 194         assert fprint & letter_sig == 0
 195         sig = fprint | letter_sig
 196         return sig
 197
 198     @staticmethod
 199     def repopulate(
 200         letter_sigs: Dict[str, int],
 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(letter_sigs, 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] += ",%s" % 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         (exact, location) = list_utils.binary_search(self.sigs, sig)
 256         start = location - window_size
 257         if start < 0:
 258             start = 0
 259         end = location + 1 + window_size
 260         if end > len(self.words):
 261             end = len(self.words)
 262
 263         for x in range(start, end):
 264             word = self.words[x]
 265             fsig = self.sigs[x]
 266             if window_size > 0 or (fsig == sig):
 267                 ret[word] = fsig == sig
 268         return ret
 269
 270
 271 #
 272 # To repopulate, change letter_sigs and then call Unscrambler.repopulate.
 273 # See notes above.  See also ~/bin/unscramble.py --populate_destructively.
 274 #
 275
 276
 277 if __name__ == "__main__":
 278     import doctest
 279
 280     doctest.testmod()