algorithm - 性能问题，大字符串的编辑距离 LCP vs Levenshtein vs SIFT

Question

所以我试图计算两个大字符串之间的距离(大约 20-100)。 障碍是性能，我需要运行 20k 距离的比较。 (需要几个小时)

经过调查，我遇到了几种算法，但我很难决定选择哪个。 (基于性能VS准确率)

https://github.com/tdebatty/java-string-similarity - 每种算法的性能列表。

** 已编辑 **

1. SIFT4 算法经过充分验证/可靠吗？
2. SIFT4 是适合该任务的算法吗？
3. 为什么它比基于 LCP/Levenshtein 算法快这么多？
4. SIFT 也用于图像处理吗？或者是另一回事？ AMH 回答

谢谢。

Answer 1

据我所知，尺度不变特征变换(SIFT)是计算机视觉中的一种算法，检测和描述图像中的局部特征。

此外，如果您想找到相似的图像，您必须通过计算图像的距离来比较图像的局部特征，这可能会实现您想要做的事情。但据我记得，局部特征是数字向量。它使用暴力匹配器:Feature Matching - OpenCV Library - SIFT

请在此处阅读有关 SIFT 的信息:http://docs.opencv.org/3.1.0/da/df5/tutorial_py_sift_intro.html

您提供的链接中提到的 SIFT4 是完全不同的东西。