Eugene Myers 的 Diff 算法：寻找 "A" 和 "B" 的最长公共子序列

Question

我一直在查看 Eugene Myers' Diff Algorithm Paper。这是在流行的 diff 程序中实现的算法。

在论文的第12页，给出了寻找A和B的最长公共子序列算法的伪代码：

LCS(A, N, B, M)
    If N > 0 and M > 0 Then
        Find the middle snake and the length of an optimal path for A and B.
        Suppose it is from (x, y) to (u, v).
        If D > 1 Then
            LCS(A[1..x], x, B[1..y], y)
            Output A[x+1..u]
            LCS(A[u+1..N], N-u, B[v+1..M], M-v)
        Else If M > N Then
            Output A[1..N].
        Else
            Output B[1..M].

假设 A = "A" 和 B = "B"。在这种情况下，N = 1 和 M = 1。中间的蛇将是 (x, y) = (0, 1) 和 (u, v) = (0, 1)，因为没有对角线。在这种情况下 D = 1，因为算法只进行了一步。

算法说在这个场景下唯一要做的就是Output B[1..M]，等于"B"，因为N > 0, M > 0, D = 1, M = N但这似乎是错误的，因为"A"和"B"之间没有共同的子序列。该论文的评论 "If D <= 1 then B is obtained from A by either deleting or inserting at most one symbol" 是不正确的，因为必须删除 "A" 并添加 "B"。

我在这里误解了什么？

Answer 1

你误解了 D-path 和 snake 的定义。

从第 4 页开始：

Let a D-path be a path starting at (0,0) that has exactly D non-diagonal edges. A 0-path must consist solely of diagonal edges. By a simple induction, it follows that a D-path must consist of a (D − 1)-path followed by a non-diagonal edge and then a possibly empty sequence of diagonal edges called a snake

因此，在您的示例中，A = "A" 和 B = "B"，最佳路径是 2 条路径（一条水平和一条垂直），中间的蛇是空的细绳。通过检查我们知道 LCS 是一个空字符串，但我们想展示算法来证明它。

首先我们需要找到中间的蛇。如果你按照第 11 页的算法找到中间的蛇，你会看到最短编辑脚本的长度是 2 并且 (x,y) = (u,v) = (1,0) or (0,1 ).换句话说，它是一条空蛇在路径中间。

算法伪代码有一些不明显的符号约定：

如果 n < m.
在对LCS的递归调用中，第一次调用使用ceiling(D/2)作为D，第二次调用使用floor(D/2)。这在第 12 页算法上方的文本中更加清楚。

所以，在这个例子中，假设第一次调用 LCS 找到了一条中间的蛇，其中 (x,y) = (u,v) = (1,0)，那么由于 D=2，结果是扩展：

LCS(A[1..1], 1, B[1..0], 0)  // Output nothing since M = 0
Output A[2..1]               // Output nothing since it is an empty string.
LCS(A[2..1], 0, B[1..1], 1)  // Output nothing since N = 0

这是正确的，因为这些字符串没有共同的子序列。

Eugene Myers 的 Diff 算法：寻找 "A" 和 "B" 的最长公共子序列

Eugene Myers' Diff Algorithm: Finding the Longest Common Subsequence of "A" and "B"

algorithm

diff