#!/usr/bin/env python3
import logging
-from typing import Dict
+from typing import Dict, Mapping
import config
import decorator_utils
class Unscrambler(object):
- sigs = []
- words = []
+ """A class that unscrambles words quickly by computing a signature
+ (sig) for the word based on its position independent letter
+ population and then using a pregenerated index to look up known
+ words the same set of letters.
+
+ Note that each instance of Unscrambler caches its index to speed
+ up lookups number 2..N; careless reinstantiation will by slower.
+
+ Sigs are designed to cluster similar words near each other so both
+ lookup methods support a "fuzzy match" argument that can be set to
+ request similar words that do not match exactly in addition to any
+ exact matches.
+
+ """
def __init__(self):
- pass
+ # Cached index per instance.
+ self.sigs = []
+ self.words = []
+
+ if 'unscramble_indexfile' in config.config:
+ indexfile = config.config['unscramble_indexfile']
+ else:
+ indexfile = "/usr/share/dict/sparse_index"
+
+ with open(indexfile, 'r') as rf:
+ lines = rf.readlines()
+ for line in lines:
+ line = line[:-1]
+ (fsig, word) = line.split('+')
+ fsig = int(fsig, 16)
+ self.sigs.append(fsig)
+ self.words.append(word)
# 52 bits
@staticmethod
- def _compute_word_fingerprint(word: str, population) -> int:
+ def _compute_word_fingerprint(
+ word: str, population: Mapping[str, int]
+ ) -> int:
fp = 0
- for pair in sorted(population.items(), key=lambda x: x[1], reverse=True):
+ for pair in sorted(
+ population.items(), key=lambda x: x[1], reverse=True
+ ):
letter = pair[0]
if letter in fprint_feature_bit:
count = pair[1]
# 32 bits
@staticmethod
- def _compute_word_letter_sig(letter_sigs, word: str, population) -> int:
+ def _compute_word_letter_sig(
+ letter_sigs: Mapping[str, int],
+ word: str,
+ population: Mapping[str, int],
+ ) -> int:
sig = 0
- for pair in sorted(population.items(), key=lambda x: x[1], reverse=True):
+ for pair in sorted(
+ population.items(), key=lambda x: x[1], reverse=True
+ ):
letter = pair[0]
if letter not in letter_sigs:
continue
"""
population = list_utils.population_counts(word)
fprint = Unscrambler._compute_word_fingerprint(word, population)
- letter_sig = Unscrambler._compute_word_letter_sig(letter_sigs, word, population)
+ letter_sig = Unscrambler._compute_word_letter_sig(
+ letter_sigs, word, population
+ )
assert fprint & letter_sig == 0
sig = fprint | letter_sig
return sig
indexfile: str = '/usr/share/dict/sparse_index',
) -> None:
"""Before calling this method, change letter_sigs from the default above
- unless you want to populate the same exact files."""
+ unless you want to populate the same exact files.
+ """
words_by_sigs = {}
seen = set()
with open(dictfile, "r") as f:
word = words_by_sigs[sig]
print(f'0x{sig:x}+{word}', file=f)
- @staticmethod
- def lookup(word: str, *, include_fuzzy_matches=False) -> Dict[str, bool]:
+ def lookup(
+ self, word: str, *, include_fuzzy_matches: bool = False
+ ) -> Dict[str, bool]:
"""Looks up a potentially scrambled word optionally including near
"fuzzy" matches.
- >>> Unscrambler.lookup('eanycleocipd', include_fuzzy_matches=False)
+ >>> u = Unscrambler()
+ >>> u.lookup('eanycleocipd', include_fuzzy_matches=False)
{'encyclopedia': True}
"""
sig = Unscrambler.compute_word_sig(word)
- return Unscrambler.lookup_by_sig(
+ return self.lookup_by_sig(
sig, include_fuzzy_matches=include_fuzzy_matches
)
- @staticmethod
- def lookup_by_sig(sig, *, include_fuzzy_matches=False) -> Dict[str, bool]:
+ def lookup_by_sig(
+ self, sig: int, *, include_fuzzy_matches: bool = False
+ ) -> Dict[str, bool]:
"""Looks up a word that has already been translated into a signature by
a previous call to Unscrambler.compute_word_sig. Optionally returns
near "fuzzy" matches.
>>> sig
18491949645300288339
- >>> Unscrambler.lookup_by_sig(sig, include_fuzzy_matches=True)
+ >>> u = Unscrambler()
+ >>> u.lookup_by_sig(sig, include_fuzzy_matches=True)
{'pupigerous': False, 'pupigenous': False, 'unpurposing': False, 'superpurgation': False, 'unsupporting': False, 'superseptuaginarian': True, 'purpurogallin': False, 'scuppaug': False, 'purpurigenous': False, 'purpurogenous': False, 'proppage': False}
"""
- # Cache the index; it doesn't change and this may be called
- # more than once.
- if len(Unscrambler.sigs) == 0:
- if 'unscramble_indexfile' in config.config:
- indexfile = config.config['unscramble_indexfile']
- else:
- indexfile = "/usr/share/dict/sparse_index"
- with open(indexfile, 'r') as rf:
- lines = rf.readlines()
- for line in lines:
- line = line[:-1]
- (fsig, word) = line.split('+')
- fsig = int(fsig, 16)
- Unscrambler.sigs.append(fsig)
- Unscrambler.words.append(word)
-
ret = {}
- (exact, location) = list_utils.binary_search(Unscrambler.sigs, sig)
+ (exact, location) = list_utils.binary_search(self.sigs, sig)
start = location - 5
if start < 0:
start = 0
end = location + 6
- if end > len(Unscrambler.words):
- end = len(Unscrambler.words)
+ if end > len(self.words):
+ end = len(self.words)
for x in range(start, end):
- word = Unscrambler.words[x]
- fsig = Unscrambler.sigs[x]
+ word = self.words[x]
+ fsig = self.sigs[x]
if include_fuzzy_matches is True or (fsig == sig):
ret[word] = fsig == sig
return ret
projects / python_utils.git / blobdiff