string - 检索接近 Levenshtein 距离的字符串的数据结构

Question

例如，从一组英语单词开始，是否有一种结构/算法允许使用单词“right”作为查询快速检索“light”和“tight”等字符串？即，我想检索到查询字符串的 Levenshtein 距离较小的字符串。

Answer 1

BK-tree数据结构在这里可能是合适的。它旨在有效地支持以下形式的查询“与查询词的编辑距离为 k 或更短的所有词是什么？” 它的性能保证相当不错，而且实施起来并不难。

希望这可以帮助！

Answer 2

由于计算 Levenshtein 距离是O(nm)针对长度为 n 和 m 的字符串，因此计算所有 Levenshtein 距离L(querystring, otherstring)的简单方法非常昂贵。

但是，如果您将 Levenshtein 算法可视化，它基本上会用编辑距离填充一个 n*m 表。但是对于以相同的几个字母（前缀）开头的单词，Levenshtein 表的前几行将是相同的。（当然，修复查询字符串。）

这建议使用trie（也称为前缀树）：读取查询字符串，然后构建 Levenshtein 行的 trie。之后，您可以轻松地遍历它以找到靠近查询字符串的字符串。

（这确实意味着您必须为新的查询字符串构建一个新的 trie。我认为所有对距离都没有类似的有趣结构。）

我想我最近看到了一篇关于这个的文章，里面有一个很好的 python 实现。如果我能找到它会添加一个链接。编辑： 在这里，在史蒂夫·汉诺夫的博客上。

Answer 3

我认为最快的方法是预先构建相似性的缓存，您可以在 O(1) 时间内索引和访问。诀窍是找到常见的拼写错误以添加到您的缓存中，这可能会变得非常大。

我想谷歌会使用他们广泛的统计查询搜索数据做类似的事情。