在 Python 中进行模糊键查找的最佳方法？

Question

我有一个问题，我需要在哈希映射中进行模糊查找，即 return 对应于与查询最相似的键的值，在我的例子中是用 Levenshtein 距离测量的。

我目前的方法是使用一种特殊的查找方法对 dict 进行子类化，该方法计算针对所有键的 Levenshtein 距离，然后 returns 具有最低分数的键的值。基本上是这样的：

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 距 [=] 的所有字符串的集合21=]w最多为n.

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

Jule Jacob 的博客 post Levenshtein automata can be simple and fast is a good starting point and Nick Johnsonz's Damn Cool Algorithms: Levenshtein Automata 是一个更深入的介绍。

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

在 Python 中进行模糊键查找的最佳方法？

Best way to do a fuzzy key lookup in Python?

python

data-structures

hashmap

hashtable

python-collections