文本文件差異對比算法研究

李 明

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

文本文件差異對比算法研究

李 明

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

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

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

0 引言

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

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

1 LCS算法對比

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

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

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

解決LCS問題，需要把原問題分解成若干個子問題，所以需要刻畫LCS的特征。

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

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

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

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

因此算法的遞推公式為：

該算法的求解過程如圖1所示：

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

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

1.2 O(ND)比較算法

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

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

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

通過采用貪心原則：通過最大限度的延伸編輯距離為D-1的編輯圖可以得到編輯距離為D的編輯圖。編輯距離從0開始到M+N結(jié)束，當(dāng)最終結(jié)束點為（N,M）時，算法結(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

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

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

1.3 O(NP)比較算法

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

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

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

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

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

與O（ND）比較算法一樣，該算法也集中于計算一組最遠(yuǎ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)中計算集合 FP(p)，當(dāng) FP(p)中包含終點（M,N）時，算法結(jié)束。假設(shè)qk是在對角邊k上刪除距離為p-1的最遠(yuǎn)的點（例如點(y -k, y)，因此y =fp(k, p-1)）。令 gk是對角邊 k上刪除距離為 p的最遠(yuǎ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 計算出 gΔ。定義 snake(k,y)表示在對角邊k上從點(y-k, y)出發(fā)能到達的最遠(yuǎn)的點，則snake(k, y) = max { z : ay +1-k ... az -k =by +1 ...bz },最后得到fp(k, p)的公式如下：

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

2 實驗

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

表1 實驗結(jié)果Tab.1 Experimental results

3 結(jié)束語

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

[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

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