我一直在寻找一种先进的 levenshtein 距离算法，到目前为止我发现的最好的是 O(n*m) 其中 n 和 m 是两个字符串的长度。算法之所以处于这种规模，是因为空间，而不是时间，创建了一个由两个字符串组成的矩阵，例如：
是否有比 O(n*m) 更好的公开可用的 levenshtein 算法？我不反对查看高级计算机科学论文和研究，但一直找不到任何东西。我找到了一家公司，Exorbyte，据说它已经建立了一个超级先进和超级快速的 Levenshtein 算法，但这当然是一个商业机密。我正在构建一个我想使用 Levenshtein 距离计算的 iPhone 应用程序。有一个objective-c 实现可用，但是由于iPod 和iPhone 上的内存量有限，如果可能的话，我想找到一个更好的算法。
您对降低时间复杂度或空间复杂度感兴趣吗？平均时间复杂度可以降低 O(n + d^2)，其中 n 是较长字符串的长度，d 是编辑距离。如果您只对编辑距离感兴趣而不对重建编辑序列感兴趣，则只需将矩阵的最后两行保留在内存中，即 order(n)。
如果您能负担得起近似值，则可以使用多对数近似值。
对于 O(n +d^2) 算法，请查找 Ukkonen 的优化或其增强增强 Ukkonen。我所知道的最好的近似值是 Andoni、Krauthgamer、Onak的这个
如果您只需要阈值函数 - 例如，测试距离是否低于某个阈值 - 您可以通过仅计算数组中主对角线两侧的 n 个值来降低时间和空间复杂度。您还可以使用Levenshtein Automata在 O(n) 时间内针对单个基本词评估多个单词 - 自动机的构建也可以在 O(m) 时间内完成。
查看 Wiki - 他们有一些想法来改进此算法以提高空间复杂度：
报价：
我们可以调整算法以使用更少的空间，O(m) 而不是 O(mn)，因为它只需要在任何时候存储前一行和当前行。
我发现了另一个声称为 O(max(m, n)) 的优化：
http://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance#C
（第二个 C 实现）