Pythonでファジーキールックアップを行う最も良い方法は？

Question

私は、ハッシュマップでファジールックアップを行う必要がある、すなわち、私の場合、Levenshtein距離で測定されたクエリに最もよく似ているそのキーに対応する値を返す必要があるという問題があります。

私の現在のアプローチは、dictをすべてのキーに対してLevenshtein距離を計算する特別なルックアップ方法でサブクラス化し、次に最も低いスコアのキーの値を返します。基本的には

import Levenshtein 

class FuzzyLookupDict(dict): 

    def fuzzy_lookup(self, query): 
     levs = [(key, Levenshtein.ratio(query, key)) for key in self.keys()] 
     key, score = max(levs, key=lambda lev: lev[1]) 
     return self.get(key) 

これは良いアプローチですか、それとも私が考えていないより良い解決策ですか？

Answer 1

この問題は通常Levenshtein automataで解決されます。ワットストリングと数Nためのレーベンシュタインオートマトンは、レーベンシュタイン距離からワットN以下であるすべての文字列のセットを認識することができる有限状態オートマトンです。

このアルゴリズムは、ダイナミックプログラミングを使用して辞書語ごとにLevenshtein距離を別々に計算するよりもはるかに高速です。

ジュール・ジェイコブのブログ記事Levenshtein automata can be simple and fastは良い出発点であり、ニック・ジョンソンズのDamn Cool Algorithms: Levenshtein Automataは、より深いイントロです。

GithubでPythonの実装を見つけることができます。例えば、https://github.com/antoinewdg/pyffsです。