我有一个约 150'000 个单词和一个模式（任何单个单词）的数据库，我想从数据库中获取所有单词，它与模式之间的 Damerau-Levenshtein 距离小于给定数字。我需要做的非常快。你能建议什么算法？如果 Damerau-Levenshtein 距离没有好的算法，也欢迎 Levenshtin 距离。
感谢您的帮助。
PS 我不会使用 SOUNDEX。
问问题
4105 次
5 回答
2
我将从一个 SQL 函数开始计算 Levenshtein 距离（在 T-SQl 或 .Net 中）（是的，我是一名 MS 人员......），其中最大距离参数会导致提前退出。
然后可以使用此函数将您的输入与每个字符串进行比较，以检查距离，如果超出阈值则继续下一个。
我还想你可以，例如，将最大距离设置为 2，然后过滤长度大于 1 的所有单词，而第一个字母不同。使用索引可能会稍微快一些。
您还可以使用快捷方式恢复所有完美匹配的字符串（索引会加快速度），因为这些实际上需要更长的时间来计算 Levenshtein 距离为 0。
只是一些想法......
于 2010-01-20T08:55:09.243 回答
0
我不认为你可以在不实际枚举所有行的情况下计算这种函数。
所以解决方案是：
- 使其成为一个非常快速的枚举（但这并不能真正扩展）
- 以某种方式过滤初始变体（按字母索引，至少 x 个常见字母）
- 使用替代（可索引）算法，例如 N-Grams（但是我没有关于 ngrams 与 DL 距离的结果质量的详细信息）。
于 2010-01-20T08:35:35.123 回答
0
我想到的一个解决方案可能是将数据库存储在一个排序集中（例如，std::set在 C++ 中），因为在我看来，按字典顺序排序的字符串会比较好。要近似给定字符串在 中的位置，请在字符串上set使用std::upper_bound，然后从找到的位置在两个方向上向外迭代该集合，计算您前进的距离，并在低于某个阈值时停止。我有一种感觉，这个解决方案可能只会匹配具有相同起始字符的字符串，但如果您使用该算法进行拼写检查，那么这种限制很常见，或者至少不足为奇。
编辑：但是，如果您正在寻找算法本身的优化，那么这个答案是无关紧要的。
于 2010-01-20T08:42:23.503 回答
0
我已经使用 KNIME 进行字符串模糊匹配，并且得到了非常快的结果。在其中制作可视化工作流程也非常容易。只需从https://www.knime.org/安装 KNIME 免费版，然后使用“字符串距离”和“相似性搜索”节点即可获得结果。我在这里附上了一个小的模糊匹配小工作流程（在这种情况下，输入数据来自顶部，要搜索的模式来自底部）：
于 2014-10-10T13:32:44.700 回答
-1
我建议调查Ankiro。
我不确定它是否满足您对精度的要求，但它很快。
于 2010-01-20T08:35:10.667 回答