Tag: levenshtein 距离

Ruby中字符串字典中的快速模糊/近似搜索

我有一个50K到100K字符串的字典（最多可以有50多个字符），我试图找到给定字符串是否在字典中具有一些“编辑”距离容差。 （例如Levenshtein）。 在进行搜索之前，我很好地预先计​​算任何类型的数据结构。 我的目标是尽可能快地对该字典运行数千个字符串并返回最近的邻居。 我会很好的只是得到一个布尔值，说明一个给定是否在字典中，如果有一个明显更快的算法这样做 为此，我首先尝试计算所有Levenshtein距离并采取最小值，但显然非常慢。 所以我尝试在这篇文章的基础上实现Levenshtein Trie http://stevehanov.ca/blog/index.php?id=114 请参阅我的要点，重现基准： https ： //gist.github.com/nicolasmeunier/7493947 以下是我在机器上的一些基准测试： 编辑距离0（完美匹配） Benchmark.measure { 10.times { dictionary.search(random_word, 0) } } * 编辑距离2，变得慢很多* Benchmark.measure { 10.times { dictionary.search(random_word, 2) } } 它从那里走下坡路，并且编辑距离大于2时变得非常慢。（每个测试字符串的平均值超过1秒）。 我想知道如何/如果我可以显着加快这一点。 如果已经在ruby / gem中实现了现有解决方案，我也不想重新发明轮子…… 编辑1：在我的情况下，我希望我与字典匹配的大多数字符串不在那里。 因此，如果有任何算法可以快速丢弃字符串，那可能会有所帮助。 谢谢，尼古拉斯