李 明

（北京郵電大學(xué)網(wǎng)絡(luò)技術(shù)研究院，北京 100876）

文本文件差異對(duì)比算法研究

李 明

（北京郵電大學(xué)網(wǎng)絡(luò)技術(shù)研究院，北京 100876）

如今各種項(xiàng)目的規(guī)模越來(lái)越大，而一個(gè)人的能力和精力是有限的，因此通常需要有一個(gè)團(tuán)隊(duì)進(jìn)行協(xié)作開(kāi)發(fā)。在協(xié)作開(kāi)發(fā)時(shí)，不可避免的會(huì)產(chǎn)生工作交叉，甚至沖突。目前常見(jiàn)的多人協(xié)作工具如git、svn等，都提供了對(duì)不同版本的文件進(jìn)行差異對(duì)比，由此來(lái)為開(kāi)發(fā)人員提供幫助。在文本文件的差異對(duì)比算法中，它的核心是最長(zhǎng)公共子序列算法。因此在這篇論文中，我們首先將對(duì)常見(jiàn)的最長(zhǎng)公共子序列算法進(jìn)行探討，在之后將對(duì)一種優(yōu)化后的LCS算法進(jìn)行詳細(xì)分析。

文件差異比較；最長(zhǎng)公共子序列；最短編輯距離；NP算法

0 引言

文件間的差異對(duì)比是目前多人協(xié)作工具提供的一個(gè)重要功能，在一些軟件開(kāi)發(fā)工具中也有提供。主要目的是為了在多人協(xié)作的模式中，假設(shè)出現(xiàn)文件修改沖突，開(kāi)發(fā)人員可以通過(guò)文件對(duì)比找出沖突原因并進(jìn)行處理，從而降低開(kāi)發(fā)人員的工作量。因此提供一個(gè)優(yōu)秀的文本差異對(duì)比算法很有必要。

文件差異對(duì)比算法的本質(zhì)其實(shí)是最長(zhǎng)公共子序列算法，只不過(guò)文件差異對(duì)比可能會(huì)允許近似解。目前最長(zhǎng)公共子序列算法的時(shí)間復(fù)雜度為O(n^2)。普通的 DP方法，無(wú)論是時(shí)間還是空間上，復(fù)雜度都是 O(n^2)。假設(shè)文件的行數(shù)很多，那么算法的效率將非常低。因此我們?cè)趯?duì)傳統(tǒng)的最長(zhǎng)公共子序列算法進(jìn)行探討和分析后，會(huì)對(duì)一種優(yōu)化后的最長(zhǎng)公共子序列算法進(jìn)行分析，該算法的時(shí)間復(fù)雜度可以達(dá)到O(NP)，近似于O(ND)算法的兩倍，其中P為刪除距離，D為編輯距離。

1 LCS算法對(duì)比

文件差異對(duì)比算法的本質(zhì)其實(shí)是最長(zhǎng)公共子序列算法，在實(shí)際實(shí)現(xiàn)的過(guò)程中，我們會(huì)對(duì)文件進(jìn)行預(yù)處理，通常是以行為單位，為每一行數(shù)據(jù)通過(guò)哈希算法產(chǎn)生一個(gè)哈希值，從而將文件內(nèi)容轉(zhuǎn)化為了一個(gè)由每一行計(jì)算得來(lái)的哈希值組成的字符串，因此文件差異的比較轉(zhuǎn)化為了求解LCS問(wèn)題。

求解LCS問(wèn)題，不能使用暴力搜索方法。一個(gè)長(zhǎng)度為n的序列擁有 2的n次方個(gè)子序列，它的時(shí)間復(fù)雜度是指數(shù)級(jí)。因此解決LCS問(wèn)題，需要借助動(dòng)態(tài)規(guī)劃的思想。動(dòng)態(tài)規(guī)劃算法通常用于求解具有某種最優(yōu)性質(zhì)的問(wèn)題。在這類(lèi)問(wèn)題中，可能會(huì)有許多可行解。每一個(gè)解都對(duì)應(yīng)于一個(gè)值，我們希望找到具有最優(yōu)值的解。動(dòng)態(tài)規(guī)劃算法與分治法類(lèi)似，其基本思想也是將待求解問(wèn)題分解成若干個(gè)子問(wèn)題，先求解子問(wèn)題，然后從這些子問(wèn)題的解得到原問(wèn)題的解。與分治法不同的是，適合于用動(dòng)態(tài)規(guī)劃求解的問(wèn)題，經(jīng)分解得到子問(wèn)題往往不是互相獨(dú)立的，從而會(huì)出現(xiàn)大量的重復(fù)計(jì)算。因此我們可以用一個(gè)表來(lái)記錄所有已解的子問(wèn)題的答案，從而避免重復(fù)計(jì)算這就是動(dòng)態(tài)規(guī)劃法的基本思路。

1.1 普通的動(dòng)態(tài)規(guī)劃求LCS

解決LCS問(wèn)題，需要把原問(wèn)題分解成若干個(gè)子問(wèn)題，所以需要刻畫(huà)LCS的特征。

設(shè) A=“x0,x1,…,xm”，B=“y0,y1,…,yn”，且 Z=“z0,z1,…,zk”為它們的最長(zhǎng)公共子序列。不難證明有以下性質(zhì)：

如果 xm=yn，則 zk=xm=yn，且“z0,z1,…,z(k-1)”是“x0,x1,…,x(m-1)”和“y0,y1,…,y(n-1)”的一個(gè)最長(zhǎng)公共子序列；

如果xm!=yn，則若zk!=xm，蘊(yùn)涵“z0，z1，…，zk”是“x0,x1,…,x(m-1)”和“y0,y1,…,yn”的一個(gè)最長(zhǎng)公共子序列；

如果xm!=yn，則若zk!=yn，蘊(yùn)涵“z0,z1,…,zk”是“x0,x1,…,xm”和“y0,y1,…,y(n-1)”的一個(gè)最長(zhǎng)公共子序列。

因此算法的遞推公式為：

該算法的求解過(guò)程如圖1所示：

圖1 普通DP求解過(guò)程Fig.1 The general solving process of DP

在普通的動(dòng)態(tài)規(guī)劃求解LCS的過(guò)程中，并沒(méi)有考慮到通常情況下，文件在進(jìn)行比較時(shí)，兩個(gè)文件的相似度應(yīng)該是很高的，總是以最壞情況進(jìn)行考慮，會(huì)將圖1中的所有空白處填滿，仍然增加了許多額外的計(jì)算過(guò)程，它的時(shí)間復(fù)雜度和空間復(fù)雜度均為O(N^2)。

1.2 O(ND)比較算法

O(ND)比較算法也是一種動(dòng)態(tài)規(guī)劃算法，它是由Myers提出的。與前面提到的動(dòng)態(tài)規(guī)劃算法的區(qū)別在于它考慮到了兩個(gè)文件的相似度很高，從而采用了貪心設(shè)計(jì)的方式進(jìn)行實(shí)現(xiàn)。

O(ND)比較算法采用了編輯圖的形式。設(shè)兩個(gè)序列分別為 A=“a1,a2,…,an”，B=“b1,b2,…,bm”，其中A和B的長(zhǎng)度分別為N和M。因此我們可以得到一個(gè)和圖2相似的編輯圖，編輯圖的頂點(diǎn)通過(guò)水平、垂直和對(duì)角有向邊連接，形成有向無(wú)環(huán)圖。水平邊將每個(gè)頂點(diǎn)連接到它的右鄰點(diǎn)，即（x-1,y）→（x,y），垂直邊將每個(gè)頂點(diǎn)連接到它下面的相鄰點(diǎn)，即（x,y-1）→（x,y），而對(duì)角有向邊連接的（x-1,y-1）→（x,y）表示點(diǎn)（x,y）為匹配點(diǎn)，即 ax=by。一系列由xi＜ xi+l并且yi＜ yi+l的這些匹配點(diǎn)構(gòu)成的序列即為最長(zhǎng)公共子序列，而在連接過(guò)程中所經(jīng)過(guò)的水平邊和垂直邊的和即為最短編輯距離。

圖 2 序列 A=‘a(chǎn) c b d e a c b e d’和序列 B=‘a(chǎn) c e b d a b b a b e d’的編輯圖Fig.2 Edit graph for A=’a c b d e a c b e d’ and B=’a c e b d a b b a b e d’

在O(ND)算法中，將問(wèn)題進(jìn)一步轉(zhuǎn)化為了在兩個(gè)序列中尋找最短編輯距離問(wèn)題。即是尋找從（0, 0）到（n,m）的最少的非對(duì)角邊。定義對(duì)角邊k為包含點(diǎn)（x,y）并且 x-y=k，因此 k的范圍為[-M,N]。這里可以得到一個(gè)結(jié)論：一個(gè)編輯距離為D的編輯圖中，它一定是在對(duì)角邊 k上結(jié)束，其中 k∈{-D,-D+2,…,D-2,D}。這個(gè)結(jié)論可以通過(guò)歸納法進(jìn)行證明：首先一個(gè)編輯距離為0的編輯圖，一定是由對(duì)角線構(gòu)成，即最終在對(duì)角邊0上結(jié)束。假設(shè)一個(gè)編輯距離為D的編輯圖，它是在對(duì)角邊k上結(jié)束，其中k∈{-D,-D+2,…,D-2,D}。那么在編輯距離為D+1的編輯圖中，它一定包含一個(gè)編輯距離為D的路徑前綴的編輯圖，即是說(shuō)會(huì)在對(duì)角邊k處結(jié)束，由編輯距離的定義來(lái)看，此時(shí)路徑只能是向右或是向下移動(dòng)一次，然后剩余路徑必須全是對(duì)角邊，因此最終會(huì)在對(duì)角邊k+1或者k-1結(jié)束。因此它滿足編輯距離為D+1的編輯圖最終將在對(duì)角邊k上結(jié)束，其中k∈{-D-1,-D+1…,D-1,D+1}。結(jié)論成立。

通過(guò)采用貪心原則：通過(guò)最大限度的延伸編輯距離為D-1的編輯圖可以得到編輯距離為D的編輯圖。編輯距離從0開(kāi)始到M+N結(jié)束，當(dāng)最終結(jié)束點(diǎn)為（N,M）時(shí)，算法結(jié)束。因此算法的偽代碼如下：

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

該算法的求解過(guò)程如圖3所示,其中虛斜線代表在當(dāng)前的編輯距離D下，算法的邊界條件k，即最終結(jié)束點(diǎn)的對(duì)角邊 k，因此該算法的計(jì)算區(qū)域?yàn)榫庉嬀嚯xD的虛線區(qū)域中。而由于之前的計(jì)算結(jié)果都在從0到D的過(guò)程中計(jì)算完成，每次都是從上次的結(jié)果中直接使用，從而降低了計(jì)算次數(shù)。該算法的時(shí)間復(fù)雜度為O((M+N)D)，最壞的的時(shí)間復(fù)雜度為O((M+N)^2),即D=M+N，也就是兩個(gè)序列完全不同。

圖3 O(ND)求解過(guò)程Fig.3 O (ND) solving process

1.3 O(NP)比較算法

O(NP)比較算法是在 O(ND)比較算法的基礎(chǔ)上進(jìn)行了優(yōu)化，假設(shè)D為編輯圖的編輯距離，則P= D/2- (N-M)/2，P表示編輯圖的刪除距離。該算法期望的時(shí)間復(fù)雜度為O(N + PD)，它的速度大概是O(ND)比較算法的兩倍。

假設(shè)兩個(gè)序列分別為 A=“a1, a2,…,an”，B=“b1,b2,…，bm”，其中A和B的長(zhǎng)度分別為N和M。因此我們也將得到一個(gè)和圖1相似的網(wǎng)格。在這個(gè)編輯圖中，水平邊代表對(duì)應(yīng)于插入，垂直邊對(duì)應(yīng)刪除，對(duì)角邊對(duì)應(yīng)匹配點(diǎn)。因此尋找一個(gè)LCS的問(wèn)題相當(dāng)于在編輯圖中找到一個(gè)最短的源到終點(diǎn)的路徑。即是從(0,0)到(M,N)的路徑。圖2顯示了對(duì)于序列 A=‘a(chǎn) c b d e a c b e d’和序列 B=‘a(chǎn) c e b d a b b a b e d’的編輯圖，其中D=6，P=2。

在該算法中，定義對(duì)角邊k為包含點(diǎn)（x,y）并且 y-x=k的對(duì)角邊，k的范圍為[-M,N]。同時(shí)定義Δ=N-M，將包含終點(diǎn)（N,M），在 O（ND）比較算法中，它的計(jì)算區(qū)域在對(duì)角邊-D到對(duì)角邊 D的區(qū)域中，如圖4中D-band所示。而改進(jìn)后的算法將計(jì)算區(qū)域縮小在對(duì)角邊-P到對(duì)角邊Δ+P的區(qū)域中，如圖4中P-band所示。

圖4 編輯圖的D-band和P-bandFig.4 D-band and P-band of an edit graph

定義V(x,y)為最短路徑到達(dá)（x,y）的垂直邊數(shù)，定義壓縮距離為從點(diǎn)(0,0)到對(duì)角邊所需的垂直邊數(shù)，因此壓縮距離的公式為：

與O（ND）比較算法一樣，該算法也集中于計(jì)算一組最遠(yuǎn)頂點(diǎn)的距離，直到到達(dá)終點(diǎn)為止。定義FP(p) = { (y-k,y) : y = fp(k,p) 并且-p≤k≤p+Δ},其中fp (k,p)=max{y : P(y-k,y) = p}，該算法每次從集合 FP(p-1)中計(jì)算集合 FP(p)，當(dāng) FP(p)中包含終點(diǎn)（M,N）時(shí)，算法結(jié)束。假設(shè)qk是在對(duì)角邊k上刪除距離為p-1的最遠(yuǎn)的點(diǎn)（例如點(diǎn)(y -k, y)，因此y =fp(k, p-1)）。令 gk是對(duì)角邊 k上刪除距離為 p的最遠(yuǎn)的點(diǎn)，假設(shè)FP(p-1) = {q-(p -1), q-(p -2),...,qΔ+(p-1)}已經(jīng)求出，該算法將首先按照 g-p, g-(p-1), ..., gΔ-1的順序求出g值，然后根據(jù)gk -1和qk +1求出 gk，最后由 gΔ-1和 gΔ+1 計(jì)算出 gΔ。定義 snake(k,y)表示在對(duì)角邊k上從點(diǎn)(y-k, y)出發(fā)能到達(dá)的最遠(yuǎn)的點(diǎn)，則snake(k, y) = max { z : ay +1-k ... az -k =by +1 ...bz },最后得到fp(k, p)的公式如下：

該算法最壞的時(shí)間復(fù)雜度為 O(NP)，期望的時(shí)間復(fù)雜度為O(N+PD)。

2 實(shí)驗(yàn)

本文將改進(jìn)后得到的 O(NP)算法進(jìn)行了實(shí)現(xiàn)，并與梅爾斯提出的O(ND)算法進(jìn)行了比較。實(shí)驗(yàn)環(huán)境為:Intel八核（單核主頻3.4 GHz）計(jì)算機(jī)，8 GB內(nèi)存，CentOS 6.5操作系統(tǒng)，用intellij idea采用java語(yǔ)言實(shí)現(xiàn)所有算法。通過(guò)在字母表上隨機(jī)生成長(zhǎng)度為4000和5000的字符串，并進(jìn)行連續(xù)100次的測(cè)試取平均值得到最終測(cè)試結(jié)果，最終測(cè)試結(jié)果如表1所示。正如在表中所看到的，當(dāng) a和b長(zhǎng)度不相同但非常相似時(shí)，提升是相當(dāng)大的。當(dāng) a近似為 b的子序列時(shí)，改進(jìn)后的算法是線性時(shí)間運(yùn)行的。

表1 實(shí)驗(yàn)結(jié)果Tab.1 Experimental results

3 結(jié)束語(yǔ)

本文對(duì)文本文件差異對(duì)比的核心算法LCS進(jìn)行了分析和對(duì)比,包括普通DP算法，改進(jìn)之后的O(ND)算法以及在 O(ND)算法的基礎(chǔ)上改進(jìn)得到的O(NP)算法。通過(guò)最終的實(shí)驗(yàn)結(jié)果可以看到，改進(jìn)之后得到的 O(NP)算法在比較次數(shù)和時(shí)間上均遠(yuǎn)低于 O（ND）算法。由于綜合考慮了兩個(gè)序列間的相似度應(yīng)該比較高，同時(shí)將原來(lái)計(jì)算的D-band區(qū)域縮小到了P-band區(qū)域，O(NP)算法可以大幅度降低計(jì)算量，提高運(yùn)行效率。因此，O(NP)算法具有更強(qiáng)的穩(wěn)定性和實(shí)用性。

[1] Myers E W. AnO(ND) difference algorithm and its variations[J]. Algorithmica, 1986, 1(1-4): 251-266.

[2] Hirschberg, Daniel S. Algorithms for the Longest Common Subsequence Problem[J]. Journal of the Acm, 1977, 24(4):664-675.

[3] Baker B S, Giancarlo R. Sparse Dynamic Programming for Longest Common Subsequence from Fragments ☆[J].Journal of Algorithms, 2002, 42(2): 231-254.

[4] Hunt J W, Szymanski T G. A fast algorithm for computing longest common subsequences[J]. Communications of the Acm, 1977, 20(5): 350-353.

[5] Bergroth L, Hakonen H, Raita T. A survey of longest common subsequence algorithms[C]// International Symposium on String Processing and Information Retrieval, 2000. Spire 2000. Proceedings. IEEE, 2002: 39-48.

[6] Jiang T, Li M. On the approximation of shortest common supersequences and longest common subsequences[J]. Siam Journal on Computing, 2006, 24(5): 191-202.

[7] Tsai Y T. The constrained longest common subsequence problem[J]. Information Processing Letters, 2003, 88(4):173-176.

[8] Wu S, Manber U, Myers G, et al. An O( NP ) sequence comparison algorithm[J]. Information Processing Letters,1990, 35(6): 317-323.

[9] Hsu W J, Du M W. Computing a longest common subsequence for a set of strings[J]. Bit Numerical Mathematics,1984, 24(1): 45-59.

[10] Miller W, Myers E W. A file comparison program[J].Software Practice & Experience, 1985, 15(11): 1025-1040.

[11] Hunt J W, Mcillroy M D. An algorithm for differential file comparison[J]. Cstr Bell Telephone Laboratories, 1975.

[12] Fanberg V V. Computer file comparison method: US,US6236993[P]. 2001.

[13] Marcelais M R, Sullivan S T, Hilke J C. Hash-based file comparison: US, US 8543543 B2[P]. 2013.

[14] Fuchs C. File comparison of locally synched files: US,US7228319[P]. 2007.

Research on Text File Difference Contrast Algorithm

LI Ming
(Beijing University of Posts and Telecommunications, Institute of Network Technology, Beijing 100876)

Today, the scale of projects is growing, and a person's ability and energy is limited, so usually need to have a team for collaborative development.In collaborative development, there will inevitably be work cross and even conflict. At present, common multi person collaboration tools, such as GIT, SVN, etc., provide different versions of the document contrast, thus providing help for developers.In the text file difference contrast algorithm, its core is the longest common subsequence algorithm.Therefore, in this paper, we will first explore the common longest subsequence algorithm, and then an optimized LCS algorithm is analyzed in detail.

File difference comparison; Longest common subsequence; Shortest edit scrip; NP algorithm

TP312

A

10.3969/j.issn.1003-6970.2017.12.042

本文著錄格式：李明. 文本文件差異對(duì)比算法研究[J]. 軟件，2017，38（12）：216-219