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

Question

我一直在寻找一种先进的编辑距离算法，到目前为止我发现的最好的算法是 O(n*m)，其中 n 和 m 是两个字符串的长度。该算法之所以达到如此规模，是因为空间而不是时间，因为创建了两个字符串的矩阵，如下所示：

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

Answer 1

您有兴趣降低时间复杂度还是空间复杂度？平均时间复杂度可以降低到O(n + d^2)，其中n是较长字符串的长度，d是编辑距离。如果您只对编辑距离感兴趣，而对重建编辑序列不感兴趣，则只需将矩阵的最后两行保留在内存中，这样就是 order(n)。

如果您能够进行近似，可以使用多对数近似。

对于 O(n +d^2) 算法，请寻找 Ukkonen 的优化或其增强版

Enhanced Ukkonen。据我所知，最好的近似是 Andoni、Krauthgamer、Onak 的这个

Answer 2

如果您只需要阈值函数 - 例如，测试距离是否低于某个阈值 - 您可以通过仅计算数组中主对角线两侧的 n 值来降低时间和空间复杂度。您还可以使用

Levenshtein Automata 在 O(n) 时间内针对单个基本单词评估多个单词 - 并且自动机的构建也可以在 O(m) 时间内完成。

Answer 3

查看 Wiki - 他们有一些想法来改进该算法以提高空间复杂度：

维基链接：编辑距离

引用：

我们可以调整算法以使用更少的空间，O(m) 而不是 O(mn)，因为它只要求在任意时间存储前一行和当前行。

Answer 4

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

（从此页修改）

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()];
}

Answer 5

我发现了另一种优化，号称是 O(max(m, n))：

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

（第二个C实现）