javascript - 对于字符串距离，是否有比 Levenshtein 更快（不太精确）的算法？

Question

我想运行 Levenshtein，但要快得多，因为它是我正在构建的实时应用程序。一旦距离大于 10 就可以终止。

Answer 1

从评论来看，人们似乎对Sift3很满意。

http://sift.codeplex.com

Answer 2

如果要比较 UTF-8 内容，请使用sift4：

https://siderite.dev/blog/super-fast-and-accurate-string-distance.html

我还准备了一个 jsPerf，它显示了这些库之间的性能差异：http: //jsperf.com/levenshtein-perf

Answer 3

Levenshtein 距离度量允许添加、删除或替换操作。如果您正在寻找更快但不太精确的度量，您可以使用最长的公共子序列（仅允许添加和删除）甚至是汉明距离（仅允许替换）。

但是，我建议您尝试优化 Levenshtein 距离算法，因为它可以提供最佳结果。