用于检索靠近Levenshtein距离的字符串的数据结构

例如，从英语单词集开始，是否有一种结构/算法允许使用快速检索字符串（如“light”和“tight”）的字符串单词“正确”作为查询？也就是说，我想检索与查询字符串具有较小Levenshtein距离的字符串。用于检索靠近Levenshtein距离的字符串的数据结构

2013-02-13 MaiaVictor

我在想最快的方法是预先构建一个可以在O（1）时间索引和访问的相似性缓存。诀窍是找到添加到缓存的常见拼写错误，这可能会相当大。

我想象谷歌会用各种各样的统计查询搜索数据做类似的事情。

2013-02-13 02:17:53 kufudo

好的方法，如果这实际上是拼写错误，不是非常有用，如果它是更多的理论应用Levenshtein距离。 – us2012 2013-02-13 02:19:04

你的意思是什么？如果这是我想象的内存使用会使它不切实际。 – MaiaVictor 2013-02-13 02:22:26

@ us2012这是目的。 – MaiaVictor 2013-02-13 02:27:21

由于对长度为n和m的琴弦计算Levenshtein距离为O(nm)，计算所有Levenshtein距离L(querystring, otherstring)的幼稚方法非常昂贵。

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

这建议使用trie (also called prefix tree)：读取查询字符串，然后建立一个Levenshtein行的树。之后，您可以轻松遍历它来查找接近查询字符串的字符串。

（这不意味着你必须建立一个新的查询字符串的新线索。我不认为这是对全对距离的同样耐人寻味的结构。）

我想我最近看到一篇关于这个的文章，它有一个很好的python实现。如果我能找到它，会添加一个链接。 编辑：Here it is, on Steve Hanov's blog.

2013-02-13 02:34:22 us2012

这里的BK-tree数据结构可能是适当的。它旨在有效地支持“查询单词中编辑距离小于等于k的所有单词都是什么”格式的查询？它的性能保证相当不错，而且实现起来并不困难。

希望这会有所帮助！

2013-02-13 09:11:25 templatetypedef

回答