从数据库中快速获取模糊字符串匹配结果

Question

我有一个大约15万个单词的数据库和一个模式（任何单词），我想从数据库中获取所有与该模式的Damerau-Levenshtein距离小于给定数字的单词。我需要非常快速地完成它。您可以建议哪种算法？如果没有好的Damerau-Levenshtein距离算法，那么Levenshtin距离也可以。

谢谢您的帮助。

P.S. 我不打算使用SOUNDEX。

- StuffHappens

---

算法越快越好。我尝试使用标准算法（例如：http://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance）来计算距离，但发现需要更快的算法。 - StuffHappens

Answer 1

我会从编写一个SQL函数开始，用于计算Levenshtein距离（在T-SQL或.Net中）（是的，我是MS人...），并带有一个最大距离参数，如果达到该距离，则会提前退出。

然后可以使用此函数将输入与每个字符串进行比较，检查距离并在超过阈值时继续下一个。

我还考虑过，例如，将最大距离设置为2，然后筛选出所有长度相差1以上且第一个字母不同的单词。使用索引可能会稍微快一些。

您还可以快捷地返回所有完全匹配的字符串（索引将加速此操作），因为计算Levenshtein距离为0的实际上需要更长时间。

这只是一些想法...

- cjk

Answer 2

我认为你不能在不枚举所有行的情况下计算这种函数。

因此，解决方案如下：

1. 使其成为非常快速的枚举（但这并不真正可扩展）
2. 以某种方式过滤初始变量（按字母索引，至少x个常见字母）
3. 使用可替代的（可索引的）算法，例如N-Grams（但我没有关于ngrams与D-L距离结果质量的详细信息）。

- Andrey Shchekin

Answer 3

我脑海中的一个解决方案可能是将数据库存储在排序集合中（例如，在C++中使用std::set），因为按字典顺序排序的字符串似乎会有很好的比较效果。为了近似给定字符串在set中的位置，可以在字符串上使用std::upper_bound，然后从找到的位置向两个方向迭代集合，计算距离，并在距离低于某个阈值时停止。我有一种感觉，这个解决方案可能只匹配具有相同起始字符的字符串，但如果您正在使用该算法进行拼写检查，则该限制是常见的，或者至少不足为奇。

编辑：然而，如果您正在寻找算法本身的优化，则此答案无关紧要。

- Jon Purdy

Answer 4

我已经使用KNIME进行了字符串模糊匹配，并获得了非常快速的结果。在其中制作可视化工作流也非常容易。只需从https://www.knime.org/安装KNIME免费版，然后使用"String Distance"和"Similarity Search"节点即可获得您的结果。我在此附上一个小的模糊匹配示例工作流程(在这种情况下，输入数据来自顶部，要搜索的模式来自底部)：

- amircs

Answer 5

我建议你研究一下Ankiro。

我不确定它是否符合你对精度的要求，但它很快。

- LaustN

---

在那个网站上没有英文版...或者不可见。你应该用几句话解释并给出更具体的链接！ - Nikolay Ivanov