在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来解决。对于一个串w和一个数n的Levenshtein自动机是一个有限状态自动机，它能识别出Levenshtein到w的所有串的集合。在

该算法比用动态规划法分别计算每个字典词的Levenshtein距离要快得多。在

julejacob的博客文章Levenshtein automata can be simple and fast是一个很好的起点，Nick Johnsonz的Damn Cool Algorithms: Levenshtein Automata是一个更深入的介绍。在

您可以在Github上找到一些Python实现，例如https://github.com/antoinewdg/pyffs。在