string - 非常快速地从数据库中获取模糊字符串匹配

Question

我有一个大约 150'000 个单词和一个模式(任何单个单词)的数据库，我想得到 全部 数据库中的单词，它与模式之间的 Damerau-Levenshtein 距离小于给定数字。我需要做 极快 .你能推荐什么算法？如果 Damerau-Levenshtein 距离没有好的算法，也欢迎 Levenshtin 距离。

感谢您的帮助。

附言我不会使用 SOUNDEX。

Answer 1

我会从一个 SQL 函数开始计算 Levenshtein 距离(在 T-SQl 或 .Net 中)(是的，我是 MS 人......)，最大距离参数会导致提前退出。

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

我还想你可以，例如，将最大距离设置为 2，然后过滤所有长度超过 1 个不同而第一个字母不同的单词。使用索引，这可能会稍微快一些。

您还可以通过快捷方式恢复所有完美匹配的字符串(索引将加快速度)，因为这些实际上需要更长的时间来计算 0 的 Levenshtein 距离。

只是一些想法......