相关疑难解决方法(0)

我一直在寻找一种先进的levenshtein距离算法,到目前为止我发现的最好的是O(n*m),其中n和m是两个弦的长度.算法处于这种规模的原因是因为空间而不是时间,创建了两个字符串的矩阵,例如:

是否有一个公开的levenshtein算法,它比O(n*m)更好？我并不反对看高级计算机科学论文和研究,但却找不到任何东西.我找到了一家名为Exorbyte的公司,该公司据称已经建立了超级先进且超快的Levenshtein算法,但当然这是商业秘密.我正在构建一个iPhone应用程序,我想使用Levenshtein距离计算.有一个Objective-c实现可用,但由于iPod和iPhone上的内存有限,我想找到一个更好的算法,如果可能的话.