Levenshtein距离algorithm优于O（n * m）？
我一直在寻找先进的levenshtein距离algorithm， 到目前为止我发现的最好的是O（n * m），其中n和m是两个string的长度。 algorithm在这个尺度上的原因是由于空间而不是时间，因为创build了两个string的matrix，例如这个：
是否有一个比O（n * m）更好的公开可用的levenshteinalgorithm？ 我不是不想看先进的计算机科学论文和研究，但一直没能find任何东西。 我find了一家公司，Exorbyte，据说它已经build立了一个超级先进和超快的Levenshteinalgorithm，但当然这是一个商业秘密。 我正在构build一个iPhone应用程序，我想使用Levenshtein距离计算。 有一个客观的C实现可用 ，但与iPod和iPhone的有限的内存量，我想find一个更好的algorithm，如果可能的话。
您是否有兴趣减less时间复杂性或空间复杂性？ 平均时间复杂度可以减lessO（n + d ^ 2），其中n是长串的长度，d是编辑距离。 如果您只对编辑距离感兴趣而对重新构build编辑序列不感兴趣，则只需将matrix的最后两行保留在内存中，这样就是order（n）。
如果你能够近似，则有多对数近似。
对于O（n + d ^ 2）algorithm寻找Ukkonen的优化或者增强的Ukkonen 。 我知道的最好的近似是Andoni，Krauthgamer，Onak
如果只需要阈值函数（例如，testing距离是否低于某个阈值），则只需计算arrays中主对angular线两侧的n值，即可减less时间和空间的复杂性。 您也可以使用Levenshtein自动机在O（n）时间内针对单个基本单词评估许多单词 – 并且也可以在O（m）时间内完成自动机的构build。
看看维基 – 他们有一些想法来改善这个algorithm，以更好的空间复杂性：
维基链接：Levenshtein距离
引用：
我们可以调整algorithm使用更less的空间，O（m）而不是O（mn），因为它只需要在任何时候存储前一行和当前行。
我发现另一个声称是O（max（m，n））的优化：
http://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance#C
（第二个C实现）