我希望能够运行Levenshtein算法，但速度要更快，因为我正在构建一个实时应用程序。一旦距离大于10，它可以终止。
有比Levenshtein算法更快（但不太精确）的字符串距离算法吗？
6
- Shamoon
2
3你正在用Javascript实现"实时"功能？我知道即时编译器可以做很多事情，但是写这种软件的人通常非常渴望知道确切运行的机器代码，以便他们可以最大程度地优化它。这并不完全是不合理的，即时编译器的性能可能是不可预测和变化巨大的，在特殊情况下他们只能击败静态编译手动调整的C代码。 - user395760
另一个支持使用服务器端Levenshtein的投票。如果你非常必须在JavaScript中实现它，请尝试使用Web Workers（http://ejohn.org/blog/web-workers/）。 - Miriam
3个回答
3
Levenshtein距离度量允许添加、删除或替换操作。如果您正在寻找更快但不太精确的指标，可以使用最长公共子序列（仅允许添加和删除）甚至是汉明距离（仅允许替换）。
然而，我建议您尝试优化Levenshtein距离算法，因为它能给出最好的结果。
- melhosseiny
2
如果您想比较UTF-8内容，请使用：
也可以参考我准备的jsPerf，以展示这些库之间的性能差异：http://jsperf.com/levenshtein-perf。
原文链接：https://siderite.dev/blog/super-fast-and-accurate-string-distance.html。
原文链接：https://siderite.dev/blog/super-fast-and-accurate-string-distance.html。
- Afshin Mehrabani
4
1有没有针对该算法的Python / Cython / C实现可供与Levenshtein方法进行比较？ - Gökhan Sever
@GökhanSever 是的，请查看链接页面。 - user2398029
2siderite.blogspot.com已经不存在了，这是一个存档链接http://web.archive.org/web/20190613223908/https://siderite.blogspot.com/2014/11/super-fast-and-accurate-string-distance.html - amirouche
我使用@amirouche提供的页面扫描了sift4的代码，并且该代码适用于“string”，AFAIK是utf-16而不是utf-8。 - Avi
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接