我一直在寻找一种先进的编辑距离算法，并且迄今为止我发现的最好的 http://www.levenshtein.net/是 O(n*m)，其中 n 和 m 是两个字符串的长度。该算法之所以达到如此规模，是因为空间而不是时间，因为创建了两个字符串的矩阵，如下所示：
是否有比 O(n*m) 更好的公开可用的 levenshtein 算法？我并不反对查看先进的计算机科学论文和研究，但一直没能找到任何东西。我找到了一家公司，Exorbyte，据称该公司已经构建了一种超先进、超快速的 Levenshtein 算法，但这当然是一个商业秘密。我正在构建一个 iPhone 应用程序，我想使用 Levenshtein 距离计算。有一个可用的 Objective-C 实现 http://www.merriampark.com/ldobjc.htm，但由于 iPod 和 iPhone 上的内存量有限，如果可能的话，我想找到更好的算法。
您有兴趣降低时间复杂度还是空间复杂度？平均时间复杂度可以降低到O(n + d^2)，其中n是较长字符串的长度，d是编辑距离。如果您只对编辑距离感兴趣，而对重建编辑序列不感兴趣，则只需将矩阵的最后两行保留在内存中，因此将是 order(n)。
如果您能够进行近似，可以使用多对数近似。
对于 O(n +d^2) 算法，寻找 Ukkonen 的优化或其增强增强型乌科宁 http://www.berghel.net/publications/asm/asm.php。据我所知，最好的近似是这个安多尼、克劳斯加默、奥纳克 http://people.csail.mit.edu/konak/papers/approximating_edit_distance.html
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
