例如，从英文单词集开始，是否有一种结构/算法可以快速检索与查询字符串“right”具有小Levenshtein距离的字符串，例如“light”和“tight”？换句话说，我想要检索与查询字符串相似的字符串。
3个回答
4
BK树数据结构可能很适合这里。它被设计用于高效地支持查询形式为“与查询词的编辑距离小于等于k的所有单词是什么？”其性能保证相当不错，而且实现起来也不太困难。
希望这可以帮助你！
- templatetypedef
1
由于计算Levenshtein距离对于长度为n和m的字符串是O(nm)，因此计算所有Levenshtein距离L(querystring, otherstring)的朴素方法非常昂贵。
然而，如果你将Levenshtein算法可视化，它基本上填充了一个n*m的表格，用于编辑距离。但对于以相同几个字母（前缀）开头的单词，Levenshtein表的前几行将是相同的。（当然，修正查询字符串。）
这表明可以使用trie（也称为前缀树）：读取查询字符串，然后构建一个Levenshtein行的trie。之后，您可以轻松遍历它以查找接近查询字符串的字符串。
（这确实意味着您必须为新的查询字符串构建一个新的trie。我不认为有一个类似有趣的结构适用于所有对距离。）
然而，如果你将Levenshtein算法可视化，它基本上填充了一个n*m的表格，用于编辑距离。但对于以相同几个字母（前缀）开头的单词，Levenshtein表的前几行将是相同的。（当然，修正查询字符串。）
这表明可以使用trie（也称为前缀树）：读取查询字符串，然后构建一个Levenshtein行的trie。之后，您可以轻松遍历它以查找接近查询字符串的字符串。
（这确实意味着您必须为新的查询字符串构建一个新的trie。我不认为有一个类似有趣的结构适用于所有对距离。）
我记得最近看到一篇关于这个的文章，有一个很不错的Python实现。如果我能找到链接，我会加上的。编辑：在Steve Hanov的博客上找到了这篇文章。
- us2012
0
我认为最快的方法是预先构建一个相似性缓存，您可以在O(1)时间内索引和访问。诀窍在于找到常见的拼写错误并将其添加到缓存中，这可能会变得非常大。
我想Google会使用他们广泛的统计查询搜索数据来做类似的事情。
- kufudo
3
1如果这是用于拼写错误的纠正，那么这是一个好方法；但如果是用于更理论化的Levenshtein距离应用，则不是很有用。 - us2012
你的意思是什么？如果是我想象的那样，内存使用会使它不切实际。 - MaiaVictor
@us2012 这是目的。 - MaiaVictor
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接