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

Question

我有一个包含 50K 到 100K 字符串的字典(最多可以包含 50 个以上的字符)，我正在尝试查找给定字符串是否在具有“编辑”距离公差的字典中。 (例如 Levenshtein)。在进行搜索之前，我可以预先计算任何类型的数据结构。

我的目标是尽快针对该字典运行数千个字符串并返回最近的邻居。如果有一个明显更快的算法，我会得到一个 bool 值来说明给定的是否在字典中

为此，我首先尝试计算所有 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) } }
<Benchmark::Tms:0x007fa59bad8908 @label="", @real=0.010889, @cstime=0.0, @cutime=0.0, @stime=0.0, @utime=0.00999999999999801, @total=0.00999999999999801> 

*编辑距离为 2，速度变慢了很多 *

Benchmark.measure { 10.times { dictionary.search(random_word, 2) } }
<Benchmark::Tms:0x007fa58c9ca778 @label="", @real=3.404604, @cstime=0.0, @cutime=0.0, @stime=0.020000000000000018, @utime=3.3900000000000006, @total=3.4100000000000006>

它从那里走下坡路，并且对于大于 2 的编辑距离变得非常慢。(每个测试字符串平均 1+ 秒)。

我想知道如何/是否可以显着加快速度。如果已经在ruby/gems中实现了现有的解决方案，我也不想重新发明轮子...

编辑 1:在我的例子中，我希望与字典匹配的大部分字符串不在其中。因此，如果有任何算法可以快速丢弃字符串，那将非常有帮助。

谢谢， 尼古拉斯

Answer 1

我写了一对 gem ，fuzzily和 blurrily它进行基于三元组的模糊匹配。 考虑到您的(低)数据量，Fuzzily 将更容易集成并且速度差不多，在现代硬件上您可以在 5-10 毫秒内获得答案。

鉴于两者都是基于三元组(可索引)，而不是基于编辑距离(这不是)，您可能必须分两次执行此操作:

• 首先向其中一个 gem 询问一组最佳匹配的 trigrams-wise
• 然后使用 Levenstein 将结果与您的输入字符串进行比较
• 并返回该度量的最小值。

在 Ruby 中(如您所问)，使用 Fuzzily + Text gem ，获取具有编辑距离阈值的记录如下所示:

MyRecords.find_by_fuzzy_name(input_string).select { |result|
  Text::Levenshtein.distance(input_string, result.name)] < my_distance_threshold
}

这相当于一些优化良好的数据库查询和一些

注意事项:

• 如果您要寻找的“最小”编辑距离很高，您仍然需要进行大量 Levenshteins。
• 使用 trigrams 假设您的输入文本是拉丁文本或接近(基本上是欧洲语言)。
• 可能存在边缘情况，因为没有任何东西可以保证“匹配的三字母组数”是“编辑距离”的一个很好的一般近似值。