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"之间的顺序.该论文的评论是"如果D <= 1则B通过删除或插入最多一个符号从A获得"是不正确的,因为必须删除"A"并添加"B".

我在这里误解了什么？

Answer 1

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

从第4页开始:

设D路径是从(0,0)开始的具有正好D非对角线边缘的路径.0路径必须仅由对角线边缘组成.通过简单的归纳,D路径必须由(D-1)路径和非对角线边缘组成,然后是可能为空的对角线边缘序列,称为蛇

因此,在您的示例中,A ="A"且B ="B",最佳路径是2路径(一条水平路径和一条垂直路径),中间的蛇形路径是空字符串.我们从检查中知道LCS是一个空字符串,但是我们想展示算法来证明它.

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

算法伪代码有一些非显而易见的符号约定:

1. 如果n <m,则[m..n]是空字符串.
2. 在对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

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