X-Git-Url: https://wannabe.guru.org/gitweb/?a=blobdiff_plain;f=unscrambler.py;h=3abb6d817a633147382d0ac82fea37cf4450e816;hb=36fea7f15ed17150691b5b3ead75450e575229ef;hp=e53ec2a51dc91d095c697d8176127c94b4c5dc49;hpb=2f87b9d503cd98a79042d0070cde4131952cf102;p=python_utils.git diff --git a/unscrambler.py b/unscrambler.py index e53ec2a..3abb6d8 100644 --- a/unscrambler.py +++ b/unscrambler.py @@ -1,7 +1,7 @@ #!/usr/bin/env python3 import logging -from typing import Dict +from typing import Dict, Mapping import config import decorator_utils @@ -85,17 +85,49 @@ letter_sigs = { 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] @@ -108,9 +140,15 @@ class Unscrambler(object): # 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 @@ -151,7 +189,9 @@ class Unscrambler(object): """ 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 @@ -163,8 +203,9 @@ class Unscrambler(object): 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: @@ -185,22 +226,25 @@ class Unscrambler(object): 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. @@ -209,38 +253,23 @@ class Unscrambler(object): >>> 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