最近想做前端js代码的增量下载，需要用到这个算法，看了一遍，为了加深理解，顺便翻译一下。

论文原文件下载： 链接（后边有的图我就忽略了，可以去pdf里边看）

以下为译文：

摘要

对于两个序列A、B，寻找其最长公共子序列的问题与寻找其最短编辑过程（从A到B）的问题一直被认为是一对对偶问题。本文证明了它们等价于在一个编辑图中找到最短/最长路径。基于这个观点，我们找到了一个简单的O(ND)时间与空间复杂度的算法，其中N为A与B的长度和，D为AB间最短编辑过程的长度。这个算法在差异较小（序列相似）的时候表现较好，故而在典型的应用中很快。在一个基本的随机模型中，该算法的期望时间表现为O(N+D2)。该算法的一个改进版本只需要O(N) 的空间复杂度，后缀树的使用使得时间复杂度达到O(NlgN+D2)。

1. 简介

计算两个符号序列的区别的问题已经被广泛研究过了 [1,8,11,13,16,19,20]。解决这个问题的算法有着广阔的应用场景，包括拼写纠正系统，文件比较工具，以及基因演变研究等 [4,5,17,18]。正式地，这个问题被描述为寻找一个最长公共子序列，或者等价的，寻找最小的编辑过程（由删除与插入符号组成），将一个序列转换为另一个。最早的算法之一由Wagner & Fischer [20] 为了解决一般化的字符串到字符串的纠正问题提出，需要O(N2 ) 的时间与空间复杂度。其后由Hirschberg [7]提出的改进只需线性空间计算出最长公共子序列。当算法基于任意的字符表，使用“相等-不等”的比较，并依据其输入的长度，看起来Ω(N2 )的时间复杂度是必须的[1]。有一个“四个俄罗斯人”的方法在任意或有限字符表时分别取得稍好的O(N2 lglgN/lgN) 或O(N2 /lgN)的时间复杂度[13]。一些别的更快的，使用其他比较格式的算法也是公开的。事实上，对于那些使用“小于-等于-大于”比较的算法来说， Ω(NlgN) 的时间是已知最好的下限[9]。

最近的工作通过着眼于问题的其他规模参数改进了基本的O(N2 ) 时间，任意字符表的算法。令输出参数L为最长公共子序列的长度，其对偶参数D D = 2(N−L)为最小编辑过程的长度。（在这个简介中我们假设两个字符串有相等的长度N）最好的两个输出敏感（output-sensitive）算法是由Hirschberg [8] 提出的，分别需要O(NL+NlgN) 及 O(DLlgN) 的时间。Hunt & Szymanski [11] 提出过一个O((R+N)lgN) 时间的算法（R为两个输入串匹配的有序位置对数）。注意若仅依据N衡量，所有这些算法都是Ω(N2 ) 或者更差。

在实际情况下，参数D常常很小。程序员希望知道他们如何修改了一个文本文件，生物学家希望知道一个DNA序列如何突变为另一个。在这些场景中，一个 O(ND) 时间的算法要比Hirschberg’s的算法更好，因为当D很小的时候，L 是 O(N) 的。此外Hunt and Szymanski [11]的方法基于R在实际中很小的假设。虽然大部分时候是这样的，但必须注意R与输入的长度或输出的长度并无相关，甚至在很多情况下可能是 O(N2 )的。例如，如果一个文件中有10% 的行是空白的，将其与自身比较，R要大于 .01N2 。对于 DNA 分子，字符表大小为4，这意味着当一个任意的分子与其自身或极其相似的另一个分子比较时，R至少为 .25N2 。

本论文提供了一个 O(ND) 时间的算法。算法很简单，且基于直观的编辑图的形式。与其他不同的是，它使用了“贪心”的设计范式，并揭露了最长公共子序列问题与单源最短路问题的联系。 还有另一个O(ND) 的算法也被提出[16]。不过，它使用了一个不一样的设计范式，并不具备以下的特性。我们的算法可以优化为使用线性空间，它的期望时间为O(N+D2 )。此外，这个方法有一个最坏为 O(NlgN+D2 ) 时间的变体，在D为o(N)的时候，它渐进优越于先前提到的算法 [8,16,20]。

除了最坏为O(NlgN+D2 ) 的变体，本文所提出的算法是实用的。基本的O(ND) 算法被用来作为UNIX diff程序的新的实现的基础[15]。这个版本一般比系统-5的实现快两到四倍，后者基于Hunt and Szymanski的算法[10]。不过，在D很大的情况下（比如那些完全不一样的文件, R=0，D=2N），他们的算法要更好。线性空间的改进版大致是基本的O(ND)速度的二分之一，不过仍具竞争力，因为它可以完成超出其他算法能力范围的大规模比对。比如两个1,500,000 byte的序列可以在两分钟内完成比较 (on a VAX 785 running 4.2BSD UNIX) ，即便有着超过500处的区别。

2. 编辑图

令A = a1 a2 . . . aN ，B = b1 b2 . . . bM 分别为长度N，M的序列。A与B的编辑图在网格(x,y)（x∈[0,N] 且y∈[0,M]）的每个点上有一个顶点。顶点之间通过水平、垂直以及对角线方向的边连接，形成一个有向无环图。水平边将每个顶点连向其右邻接点，例： (x−1,y)→(x,y) （ x∈[1,N] and y∈[0,M]）。垂直边将每个顶点连向其下方邻接点，例： (x,y−1)→(x,y) （x∈[0,N] and y∈[1,M]）。若ax = by 则有一条斜边（对角线方向）从顶点 (x−1,y−1) 指向顶点 (x,y)。点 (x,y)若满足ax = by ，则称为匹配点（ match points）。A与B间的匹配点总数即Hunt & Szymanski 的算法[11]中的参数R。它也是编辑图中斜边的数目，因为斜边与匹配点是一一对应的。 图1即序列A = abcabba 与序列B = cbabac的编辑图。

（这里是图1）

一个长度为L的轨迹（ trace）是由L个匹配点组成的的序列，(x1 ,y1 )(x2 ,y2 ) . . . (xL ,yL ), 其中对于相邻点(xi,yi) and (xi+1,yi+1), i∈[1,L−1]，xi

一个串的子序列（subsequence ）是通过从该串中删除0个或更多的符号得到的任一串。两个串的公共子序列（ common subsequence ）同时是此二者的子序列。每个轨迹给出A与B的一个公共子序列，反之亦然。明确地， ax1 ax2 . . . axL = by1 by2 . . . byL 是A与B的公共子序列，当且仅当 (x1 ,y1 )(x2 ,y2 ) . . . (xL ,yL ) 是A与B的一条轨迹。

A与B的一个编辑过程（edit script）是一个由插入与删除指令组成的集合，它将A转换为B。删除指令（delete command ）‘‘xD’’ 从A中删除符号ax。插入指令（insert command）‘‘x I b1 ,b2 , . . . bt’’ 向ax之后插入符号序列b1 . . . bt。编辑过程中的指令提到的位置是A中未进行任何转换时的位置。我们需要假设过程中的指令集都是同时执行的。一个编辑过程的长度是被插入或删除符号的数目。

每个轨迹唯一地对应一个编辑过程。记(x1 ,y1 )(x2 ,y2) . . . (xL ,yL ) 为一个轨迹，令y0 =0，yL+1 =M+1。其关联的编辑过程由以下指令组成：‘‘xD’’ 对于x∈/(不属于) {x1 ,x2 , . . . ,xL}, 以及‘‘xk I byk +1 , . . . ,byk+1 −1’’ 对于k，yk +1

公共子序列，编辑过程，轨迹，以及从 (0,0)到(N,M)的路径是同构的形式。依据对应的公共子序列及编辑过程，每个路径的边有着以下的直接解释。每条指向(x,y)的斜边给出了公共子序列中的一个符号ax (= by)；每条指向点(x,y)的水平边对应一条删除指令 ‘‘x D’’；一个从 (x,y) 到 (x,z) 的垂直边序列对应这样的一条插入指令：‘‘x I by+1 , . . . ,bz’’。那么一条路径中的垂直边与水平边的数目即其对应的编辑过程的长度，斜边的数目即其对应的子序列的长度，所有边的总数目为N+M−L。图1描述了这一结果。

寻找最长公共子序列 (LCS) 的问题与寻找一条从(0,0)到( N,M )，具有最大数量斜边的路径等价。寻找最短编辑距离(SES) 的问题与寻找一条从(0,0)到( N,M )，具有最小数量非斜边的的路径等价。它们是对偶问题，因为一条具有最大数量斜边的具有最小数量的非斜边(D+2L = M+N)。考虑为每一条边添加一个权重/费用。斜边为0，非斜边为1，那么LCS/SES 问题则与在有权值的编辑图上寻找从(0,0) 到 (N,M)的最小费用路径等价，及单源最短路问题的一个特例。

3. 一个O((M+N)D)的贪心算法

寻找最小编辑过程的问题可以被简化为寻找从(0,0)到(N,M)，具有最小数量水平或垂直边的路径。记为从(0,0)出发且包含D条非斜边的路径为一条D-路径。一个0-路径全部由斜边组成。不难发现，一条D-路径一定由一条(D-1)-路径接一条非斜边，以及一个可能为空的斜边序列（称为一条snake）组成。 为编辑图网格中的斜边编号，斜边k由满足 x−y = k的点(x,y)组成。通过这个定义，所有的斜边都被编上了从-M到N的号。注意一条起点在斜边k上的垂直（水平）边，其终点在斜边k−1 (k+1)上；一条snake 保持在其起点所在的斜边上。

定理1: 一条D-路径一定结束在斜边k上，k ∈ { −D, −D+2, . . . D−2, D }

证明:

一条0-路径完全由斜边组成，且从斜边0开始。因而它必定结束在斜边0上。采用归纳法，假定一条D-路径必定结束在斜边k上，k在{ −D, −D+2, . . . D−2, D }中。每一条(D+1)-路径由一个前缀的D-路径（结束在斜边k上），一条非斜边（终点在斜边k+1或k-1上），以及一条snake（也必须结束在斜边k+1或k-1上）组成。那么可以得出，每一条(D+1)-路径读不定结束在斜边{ (−D)±1 , (−D+2)±1, . . . (D−2)±1, (D)±1 } = { −D−1, −D+1, . . . D−1, D+1 }上。归纳得出结果。

这个定理意味着当D为奇数时，一条D-路径仅结束在奇数号斜边上；D为偶数时，它结束在偶数号斜边上。

当且仅当一条D-路径是所有结束在斜边k的D-路径中，结束点的行（列）值最大的路径之一，则称该D-路径在斜边k上是最远到达的（furthest reaching ）。通俗的说，在所有结束在斜边k上的D-路径中，它的结束点离原点(0,0)最远。下面的定理给出了最远到达D-路径的归纳描述，并包含了一个贪心原则：最远到达D-路径可以通过贪心地延长最远到达(D-1)-路径得到。

定理2: 一个最远到达0-路径结束在(x,x)，x为最小的( z−1 || az ≠bz or z>M or z>N)值。一条斜边k上最远到达的D-路径可以被不失一般性地分解为一条k-1斜边上的最远到达(D-1)-路径，一条水平边，以及一条尽可能长的snake，或分解为一条斜边k+1上的(D-1)-路径，一条垂直边，以及一条尽可能长的snake。

证明:

0-路径的基本结论是明显的。前面提到过，一条D-路径由一条(D-1)-路径，一条非斜边，以及一条snake组成，由此断定这条(D−1)-路径一定结束在斜边k±1上，取决于在最后的snake之前的是一条垂直边还是水平边。这个snake一定是最大长度的，因为如果它可以被延至更长，那么这个D-路径就不会是最远到达的。假设这条(D-1)-路径在它的斜边上并不是最远到达的，于是另一条更远到达的(D-1)-路径可以通过无须跨斜边的移动，与该D-路径最后的snake连接起来。故该D-路径总是可以按要求的那样被分解。

已知斜边k+1和k-1上的最远到达(D-1)-路径的结束点，分别记为(x’,y’)和( x",y" ) ，定理2给出了计算斜边k上的最远到达D-路径的结束点的步骤。也就是，取k上(x’,y’+1) 及(x"+1,y") 的更远到达，然后接上尽可能多的斜边，直到没有斜边可接或到达编辑图的边缘。此外，依据定理1，一条D-路径只可能结束在D+1条斜边上。这表明可以通过依次增加D的值，计算D-路径在其对应的D+1条斜边上的结束点，直到斜边N-M上的最远到达路径到达(N,M)

For D	0 to M+N Do
    For k −D to D in steps of 2 Do
        Find the endpoint of the furthest reaching D-path in diagonal k.
            If (N,M) is the endpoint Then
                The D-path is an optimal solution. Stop

上面的算法摘要在遇到最小的D，满足存在一条最远到达的D-路径到达点(N,M)时停止。这会在外循环结束前发生，因为D必定小于等于M+N。这样构造出来的路径，其中的非斜边数目一定是最小的，故而它是LCS/SES 问题的一个解法。

下方图2的算法细节展示中使用了许多简单的优化。一个数组，V，在元素V[−D], V[−D+2], . . . , V[D-2], V[D]中存放了最远到达D-路径的结束点。依据定理1，这些元素的集合与那些会在外循环的下一次迭代中存储(D+1)-路径的结束点的元素是分离的。故数组V可以同时存放D-路径的结束点，并从它们计算出(D+1)-路径的结束点。另外，在记录斜边k上的结束点(x,y)时只需记录x，因为y=x-k。因此，V是一个整型数组，V[k]记录了斜边k上的最远到达路径的结束点的行标。

（这里是图2）

在实际应用中算法搜索满足D≤MAX的D-路径，如果没有这样的路径到达(N,M)，它将报告任何从A到B的编辑过程的长度都要大于MAX（在14行）。将常量MAX设置为M+N，可以保证算法找出LCS/SES的长度。图3 展示了当算法被用于图1中的例子时，被搜索过的D-路径。注意一个虚构的结束点(0,−1),创建在算法第一行，是用来找到最远到达0-路径的结束点。同时注意在算法执行中D-路径扩展了编辑图的左边界及下边界。这种边界情况可以通过假设这个区域没有斜边存在得到正确处理。

（这里是图3）

这个贪心算法最多花费O((M+N)D)的时间。行1及行14花费O(1)的时间。内部的For循环(行3)最多被重复执行(D+1)(D+2)/2 次，因为外部的For循环(Line 2)被重复了D+1次，且在它的第k此迭代中，其内部循环最多被迭代k次。除While循环(行9)外，内部循环中的所有行花费常数时间。故执行行2-8及10-13需要花费O(D2) 的时间。While循环在遍历最远到达路径延长线上的每条斜边时迭代一次。不过最多O((M+N)D)条斜边会被遍历，因为所有的D-路径都在斜边-D与斜边D之间，而这个区间内最多有(2D+1)min(N,M) 个点。所以这个算法总共需要O((M+N)D)的时间。注意只有行9，对snake的遍历，是瓶颈。算法的其余部分是O(D2)的。此外在实际应用中，当阈值MAX的取值比M+N小得多时，这个算法永远不会花费超过O((M+N)MAX)的时间 。

贪心算法搜索跟踪D-路径中的最优者。但只有当前的最远到达路径的结束点被保存在V中。因此在行12只能给出SES/LCS的长度。要明确地生成一个结果路径，需要O(D2 )的空间在外循环的每次迭代完成后存储V的拷贝。记Vd 为第d次迭代后V的拷贝。为了列出从(0,0)到点Vd [k]的最优路径，首先确定它是不是在一个紧接从Vd−1 [k+1]出发的垂直边或从Vd−1 [k−1]出发的水平边其后的最长snake的末端。具体地说，假设是Vd−1 [k−1]。递归地列出从(0,0)到该点的最优路径，然后列出这条垂直边与到 Vd [k]的最长snake。递归在d=0的时候停止，这时候从(0,0) 到 (V0 [0],V0 [0])的snake已经列出了。所以通过将行12替换为对该递归过程的调用（以VD [N−M]作为初始点），使用额外的O(M+N)时间与O(D2 )空间，即可列出最优路径。在下一节中有一个改进，只需O(M+N)的空间开销。

正如在第二节中提到的，LCS/SES 问题可以被看成加权编辑图上的单源最短路问题的一个特例。这表明通过特化 Dijkstra’s算法[3]，可以得到一个有效的算法。一个基本的实现[2: 207-208]显示了该算法需要O(ElgV)的时间，E为图中边的数目，V为图中点的数目。对于一个编辑图，E < 3V，因为每个点的出度最大为3。此外，lgV来自维护优先队列的开销。在本问题中，优先级的值为[0,M+N]中的整数，因为边权重为0或1，而到任意点可能的最长路径长度为M+N。在这些前提下，这个优先队列的操作可以通过使用‘‘bucketing’’以及链表实现，花费常数时间。因此Dijkstra’s 算法可以被特化为相对编辑图中的点数目线性时间的表现，也就是O(MN)。最终的改进并无其他，只是所需的所有只是从源(0,0)到点(M,N)的最短路径。 Dijkstra’s算法得到了从源出发到顶点的最短路径，按升序排列，每次迭代一个顶点。依据定理1，最多存在 O((M+N)D)个距离(0,0)比(M,N)更近的点，而先前的改进将每次迭代的开销减少到O(1)。所以这个算法可以在确定了到(M,N)的最小距离时立即停止，只需 O((M+N)D)的时间。

可见特殊化的Dijkstra’s算法也对LCS/SES问题给出了O(ND) 时间复杂度的解。然而，这个结果算法涉及到一个相对复杂的离散优先队列，该队列可能包含O(ND)之多的条目，即便只需要计算LCS/SES的长度。也许有人会提出，进一步的改进会得出本文中的简单算法，这样的联系很牵强，故而在本节中用到的直接的、易激发的变体会更好。这里的讨论的目的在于揭示最短路与LCS/SES问题及其算法的紧密联系。

（目前就翻到这，后边就是讲这个算法的改进、变体的）