莱文斯坦距离算法优于O（N * M）？ [英] Levenshtein Distance Algorithm better than O(n*m)?

问题描述

我一直在寻找一种先进的Levenshtein距离算法，并最好的，我已经发现迄今是O（N * M）其中n和m是两个字符串的长度。之所以算法是在这个规模，因为空间，而不是时间，与创建两个字符串像这样的矩阵：

I have been looking for an advanced levenshtein distance algorithm, and the best I have found so far is O(n*m) where n and m are the lengths of the two strings. The reason why the algorithm is at this scale is because of space, not time, with the creation of a matrix of the two strings such as this one:

是否有一个公开提供的Levenshtein算法比O（N * M）更好我不反对看先进的计算机科学论文和放大器？;研究，但一直没能找到任何东西。我已经找到一家公司，Exorbyte，据称已经建成了超先进的超快速Levenshtein算法，当然那不过是一个商业秘密。我建立一个iPhone应用程序，我想用Levenshtein距离计算。 有一个Objective-C的实施提供，但随着内存的iPod和iPhone手机数量有限，我想找到一个更好的算法，如果可能的话。

Is there a publicly-available levenshtein algorithm which is better than O(n*m)? I am not averse to looking at advanced computer science papers & research, but haven't been able to find anything. I have found one company, Exorbyte, which supposedly has built a super-advanced and super-fast Levenshtein algorithm but of course that is a trade secret. I am building an iPhone app which I would like to use the Levenshtein distance calculation. There is an objective-c implementation available, but with the limited amount of memory on iPods and iPhones, I'd like to find a better algorithm if possible.

推荐答案

您是否有兴趣在减少时间复杂度和空间复杂度？的平均时间复杂性可以降低为O（n + D ^ 2），其中n是较长的字符串的长度，d是编辑距离。如果你只在重建编辑序列感兴趣的编辑距离和不感兴趣，你只需要保持最后两行的矩阵在内存中，因此这将是为了（N）。

Are you interested in reducing the time complexity or the space complexity ? The average time complexity can be reduced O(n + d^2), where n is the length of the longer string and d is the edit distance. If you are only interested in the edit distance and not interested in reconstructing the edit sequence, you only need to keep the last two rows of the matrix in memory, so that will be order(n).

如果你能负担得起近似，有聚对数近似。

If you can afford to approximate, there are poly-logarithmic approximations.

有关的O（N + D ^ 2）算法寻找Ukkonen的优化或其增强增强Ukkonen 。我所知道的最好的近似值是这个由安多尼，Krauthgamer，Onak

For the O(n +d^2) algorithm look for Ukkonen's optimization or its enhancement Enhanced Ukkonen. The best approximation that I know of is this one by Andoni, Krauthgamer, Onak

这篇关于莱文斯坦距离算法优于O（N * M）？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！