Levenshtein距离算法是否比O(n*m)更好？

Question

Levenshtein距离算法是否比O(n*m)更好？

51

我一直在寻找一种先进的莱文斯坦距离算法，到目前为止，我发现最好的算法是O(n*m)，其中n和m是两个字符串的长度。算法之所以处于这个级别，是因为空间而不是时间，需要创建一个类似于以下矩阵的两个字符串的矩阵：

alt text

是否有一种公开可用的编辑距离算法比O(n*m)更好？我不排斥查看高级计算机科学论文和研究，但尚未找到任何信息。我发现了一家名为Exorbyte的公司，据说已经构建了超级先进和超级快速的Levenshtein算法，但当然这是商业机密。我正在构建一个iPhone应用程序，希望使用Levenshtein距离计算。有一个Objective-C实现可用,但由于iPod和iPhone上的内存有限，如果可能的话，我想找到更好的算法。

- Jason

5个回答

14

如果你只需要阈值函数，例如测试距离是否小于某个阈值，你可以通过仅计算数组中主对角线两侧的n个值来减少时间和空间复杂度。你还可以使用Levenshtein自动机在O(n)时间内评估许多单词与单个基础单词的相似度，并且自动机的构建也可以在O(m)时间内完成。

- Nick Johnson

而且，仅凭一侧，您怎么可能知道另一侧没有更短的路径？这意味着只用一半计算最小距离。那么主对角线呢？如果字符串大小不同，则主对角线甚至无法到达矩阵的末尾。我想我不明白您在说什么。 - Vixxs

这篇博客非常适合理解这个概念 http://blog.notdot.net/2010/07/Damn-Cool-Algorithms-Levenshtein-Automata - A. Pine

3

请参考维基百科——他们提供了一些改进此算法以更好地减少空间复杂度的想法：

维基链接：Levenshtein距离

引用：

我们可以使算法适应更小的空间，即O(m)而不是O(mn)，因为它只需要在任何时候存储前一行和当前行。

- Dani

维基百科上解释了空间复杂度的问题，使用两行并不能为长度（s）>长度（t）的字符串提供正确的解决方案。假设将S = ab转换为T = abcd需要进行两次更改。该解决方案给出1作为答案。请检查一下。 - Abhishek Kaushik

0

鉴于被比较的两个字符串可能具有不同的长度，并且矩阵的方形部分几乎是对称的，您可以利用这种对称性通过计算矩阵的上三角部分或下三角部分来减少计算量。然而，当一个字符串中的字母与另一个字符串中的字母匹配但它们的索引不同时，对称性可能会偶尔出现偏差。在这种情况下，较大三角部分中的值是唯一可能影响最终结果的值。因此，只需要计算较大的三角部分。这是一个将时间复杂度降低到O(n^2)（其中n是较短字符串的长度）的Java实现：（修改自此页面）

public static int optimalStringAlignmentDistance(String s1, String s2) {
    if (s1.length() > s2.length()) {
        return optimalStringAlignmentDistance(s2, s1);
    }

    // Initialize the table
    int[][] dp = new int[s1.length()+1][s2.length()+1];

    for (int i = 0; i <= s1.length(); i++) {
        dp[i][0] = i;
    }
    for (int j = 0; j <= s2.length(); j++) {
        dp[0][j] = j;
    }

    // Populate the table using dynamic programming
    for (int i = 1; i <= s1.length(); i++) {
        for (int j = i; j <= s2.length(); j++) {
            if (s1.charAt(i-1) == s2.charAt(j-1)) {
                dp[i][j] = dp[i-1][j-1];
            } else {
                int topMin = Math.min(dp[i-1][j-1], dp[i-1][j]);
                if (j == i) {
                    // dp[i][j-1] is not in this triangular portion
                    dp[i][j] = 1 + topMin;
                } else {
                    dp[i][j] = 1 + Math.min(topMin, dp[i][j-1]);
                }
            }
        }
    }

    // Return the edit distance
    return dp[s1.length()][s2.length()];
}

- laseredface

-1

我发现另一种声称是O(max(m, n))的优化方法：

http://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance#C

（第二个C语言实现）

- nponeccop

2

OP在谈论时间复杂度，而不是内存。 - Antoine

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- srean · Accepted Answer

你是否对减少时间复杂度或空间复杂度感兴趣？平均时间复杂度可以降低到O(n + d^2)，其中n是较长字符串的长度，d是编辑距离。如果你只关心编辑距离而不关心重构编辑序列，则只需要保留矩阵的最后两行即可，这样的顺序为n。

如果你能够接受近似值，则有多项式对数逼近。

对于O(n + d^2)算法，请查找Ukkonen优化或其增强版本Enhanced Ukkonen。我所知道的最好的逼近方法是由Andoni，Krauthgamer，Onak提出的。