lcs算法詳解重點講義

1、程序員編程藝術第十一章：最長公共子序列(LCS)問題0、前言    程序員編程藝術系列重新開始創(chuàng)作了（前十章，請參考程序員編程藝術第一十章集錦與總結）。回顧之前的前十章，有些代碼是值得商榷的，因當時的代碼只顧闡述算法的原理或思想，所以，很多的與代碼規(guī)范相關的問題都未能做到完美。日后，會著力修繕之。    搜遍網(wǎng)上，講解這個LCS問題的文章不計其數(shù)，但大多給讀者一種并不友好的感覺，稍感晦澀，且代碼也不夠清晰。本文力圖避免此些情況。力保通俗，闡述詳盡。同時，經(jīng)典算法研究系列的第三章（三、dynamic programming）也論述了此L

2、CS問題。有任何問題，歡迎不吝賜教。第一節(jié)、問題描述    什么是最長公共子序列呢?好比一個數(shù)列 S，如果分別是兩個或多個已知數(shù)列的子序列，且是所有符合此條件序列中最長的，則S 稱為已知序列的最長公共子序列。    舉個例子，如：有兩條隨機序列，如 1 3 4 5 5 ，and 2 4 5 5 7 6，則它們的最長公共子序列便是：4 5 5。    注意最長公共子串（Longest CommonSubstring）和最長公共子序列（LongestCommon Subsequence,

3、LCS）的區(qū)別：子串（Substring）是串的一個連續(xù)的部分，子序列（Subsequence）則是從不改變序列的順序，而從序列中去掉任意的元素而獲得的新序列；更簡略地說，前者（子串）的字符的位置必須連續(xù)，后者（子序列LCS）則不必。比如字符串a(chǎn)cdfg同akdfc的最長公共子串為df，而他們的最長公共子序列是adf。LCS可以使用動態(tài)規(guī)劃法解決。下文具體描述。第二節(jié)、LCS問題的解決思路· 窮舉法       解最長公共子序列問題時最容易想到的算法是窮舉搜索法，即對X的每一個子序列，檢查它是否也是Y的子序列，從而確定它是否

4、為X和Y的公共子序列，并且在檢查過程中選出最長的公共子序列。X和Y的所有子序列都檢查過后即可求出X和Y的最長公共子序列。X的一個子序列相應于下標序列1, 2, , m的一個子序列，因此，X共有2m個不同子序列（Y亦如此，如為2n），從而窮舉搜索法需要指數(shù)時間（2m * 2n）。· 動態(tài)規(guī)劃算法    事實上，最長公共子序列問題也有最優(yōu)子結構性質。記:Xi=x1，xi即X序列的前i個字符 (1im)（前綴）Yj=y1，yj即Y序列的前j個字符 (1jn)（前綴）假定Z=z1，zkLCS(X , Y)。· 若xm=yn（最后一個字符相同），則不難用

5、反證法證明：該字符必是X與Y的任一最長公共子序列Z（設長度為k）的最后一個字符，即有zk = xm = yn 且顯然有Zk-1LCS(Xm-1 , Yn-1)即Z的前綴Zk-1是Xm-1與Yn-1的最長公共子序列。此時，問題化歸成求Xm-1與Yn-1的LCS（LCS(X , Y)的長度等于LCS(Xm-1 , Yn-1)的長度加1）。· 若xmyn，則亦不難用反證法證明：要么ZLCS(Xm-1, Y)，要么ZLCS(X , Yn-1)。由于zkxm與zkyn其中至少有一個必成立，若zkxm則有ZLCS(Xm-1 , Y)，類似的，若zkyn 則有ZLCS(X , Yn-1)。此時，問

6、題化歸成求Xm-1與Y的LCS及X與Yn-1的LCS。LCS(X , Y)的長度為：maxLCS(Xm-1 , Y)的長度, LCS(X , Yn-1)的長度。    由于上述當xmyn的情況中，求LCS(Xm-1 , Y)的長度與LCS(X , Yn-1)的長度，這兩個問題不是相互獨立的：兩者都需要求LCS(Xm-1，Yn-1)的長度。另外兩個序列的LCS中包含了兩個序列的前綴的LCS，故問題具有最優(yōu)子結構性質考慮用動態(tài)規(guī)劃法。    也就是說，解決這個LCS問題，你要求三個方面的東西：1、LCS（Xm-1，Yn-1）+1；2、LC

7、S（Xm-1，Y），LCS（X，Yn-1）；3、maxLCS（Xm-1，Y），LCS（X，Yn-1）。    行文至此，其實對這個LCS的動態(tài)規(guī)劃解法已敘述殆盡，不過，為了成書的某種必要性，下面，我試著再多加詳細闡述這個問題。第三節(jié)、動態(tài)規(guī)劃算法解LCS問題3.1、最長公共子序列的結構    最長公共子序列的結構有如下表示：    設序列X=<x1, x2, , xm>和Y=<y1, y2, , yn>的一個最長公共子序列Z=<z1, z2, , zk>，則：1. 若x

8、m=yn，則zk=xm=yn且Zk-1是Xm-1和Yn-1的最長公共子序列；2. 若xmyn且zkxm ，則Z是Xm-1和Y的最長公共子序列；3. 若xmyn且zkyn ，則Z是X和Yn-1的最長公共子序列。    其中Xm-1=<x1, x2, , xm-1>，Yn-1=<y1, y2, , yn-1>，Zk-1=<z1, z2, , zk-1>。3、2.子問題的遞歸結構    由最長公共子序列問題的最優(yōu)子結構性質可知，要找出X=<x1, x2, , xm>和Y=<y1

9、, y2, , yn>的最長公共子序列，可按以下方式遞歸地進行：當xm=yn時，找出Xm-1和Yn-1的最長公共子序列，然后在其尾部加上xm(=yn)即可得X和Y的一個最長公共子序列。當xmyn時，必須解兩個子問題，即找出Xm-1和Y的一個最長公共子序列及X和Yn-1的一個最長公共子序列。這兩個公共子序列中較長者即為X和Y的一個最長公共子序列。    由此遞歸結構容易看到最長公共子序列問題具有子問題重疊性質。例如，在計算X和Y的最長公共子序列時，可能要計算出X和Yn-1及Xm-1和Y的最長公共子序列。而這兩個子問題都包含一個公共子問題，即計算Xm-1和Yn-

10、1的最長公共子序列。    與矩陣連乘積最優(yōu)計算次序問題類似，我們來建立子問題的最優(yōu)值的遞歸關系。用ci,j記錄序列Xi和Yj的最長公共子序列的長度。其中Xi=<x1, x2, , xi>，Yj=<y1, y2, , yj>。當i=0或j=0時，空序列是Xi和Yj的最長公共子序列，故ci,j=0。其他情況下，由定理可建立遞歸關系如下：3、3.計算最優(yōu)值    直接利用上節(jié)節(jié)末的遞歸式，我們將很容易就能寫出一個計算ci,j的遞歸算法，但其計算時間是隨輸入長度指數(shù)增長的。由于在所考慮的子問題空間中，總共只有(m*n

11、)個不同的子問題，因此，用動態(tài)規(guī)劃算法自底向上地計算最優(yōu)值能提高算法的效率。    計算最長公共子序列長度的動態(tài)規(guī)劃算法LCS_LENGTH(X,Y)以序列X=<x1, x2, , xm>和Y=<y1, y2, , yn>作為輸入。輸出兩個數(shù)組c0.m ,0.n和b1.m ,1.n。其中ci,j存儲Xi與Yj的最長公共子序列的長度，bi,j記錄指示ci,j的值是由哪一個子問題的解達到的，這在構造最長公共子序列時要用到。最后，X和Y的最長公共子序列的長度記錄于cm,n中。1. Procedure LCS_LENGTH(X,Y);&#

12、160; 2. begin  3.   m:=lengthX;  4.   n:=lengthY;  5.   for i:=1 to m do ci,0:=0;  6.   for j:=1 to n do c0,j:=0;  7.   for i:=1 to

13、0;m do  8.     for j:=1 to n do  9.       if xi=yj then  10.         begin  11.          &

14、#160;ci,j:=ci-1,j-1+1;  12.           bi,j:=""  13.         end  14.       else if ci-1,jci,j-1 then  15.  

15、60;      begin  16.           ci,j:=ci-1,j;  17.           bi,j:=""  18.         end 

16、 19.       else  20.         begin  21.           ci,j:=ci,j-1;  22.           bi,j:="&quo

17、t;  23.         end;  24.   return(c,b);  25. end;       由算法LCS_LENGTH計算得到的數(shù)組b可用于快速構造序列X=<x1, x2, , xm>和Y=<y1, y2, , yn>的最長公共子序列。首先從bm,n開始，沿著其中的箭頭所指的方向在數(shù)組b中搜索。· 當bi,j中遇到&quo

18、t;"時（意味著xi=yi是LCS的一個元素），表示Xi與Yj的最長公共子序列是由Xi-1與Yj-1的最長公共子序列在尾部加上xi得到的子序列；· 當bi,j中遇到""時，表示Xi與Yj的最長公共子序列和Xi-1與Yj的最長公共子序列相同；· 當bi,j中遇到""時，表示Xi與Yj的最長公共子序列和Xi與Yj-1的最長公共子序列相同。    這種方法是按照反序來找LCS的每一個元素的。由于每個數(shù)組單元的計算耗費(1)時間，算法LCS_LENGTH耗時(mn)。3、4.構造最長公共子序列 

19、;   下面的算法LCS(b,X,i,j)實現(xiàn)根據(jù)b的內容打印出Xi與Yj的最長公共子序列。通過算法的調用LCS(b,X,lengthX,lengthY)，便可打印出序列X和Y的最長公共子序列。1. Procedure LCS(b,X,i,j);  2. begin  3.   if i=0 or j=0 then return;  4.   if bi,j="" then&#

20、160; 5.     begin  6.       LCS(b,X,i-1,j-1);  7.       print(xi); 打印xi  8.     end  9.   else if bi,j="" then 

21、;LCS(b,X,i-1,j)   10.                       else LCS(b,X,i,j-1);  11. end;   在算法LCS中，每一次的遞歸調用使i或j減1，因此算法的計算時間為O(m+n)。例如，設所給的兩個序列為X=<A，B，C，B，D，

22、A，B>和Y=<B，D，C，A，B，A>。由算法LCS_LENGTH和LCS計算出的結果如下圖所示：    我來說明下此圖（參考算法導論）。在序列X=A，B，C，B，D，A，B和 Y=B，D，C，A，B，A上，由LCS_LENGTH計算出的表c和b。第i行和第j列中的方塊包含了ci，j的值以及指向bi，j的箭頭。在c7,6的項4，表的右下角為X和Y的一個LCS<B，C，B，A>的長度。對于i，j>0，項ci，j僅依賴于是否有xi=yi，及項ci-1，j和ci，j-1的值，這幾個項都在ci，j之前計算。為了重構一個LCS

23、的元素，從右下角開始跟蹤bi，j的箭頭即可，這條路徑標示為陰影，這條路徑上的每一個“”對應于一個使xi=yi為一個LCS的成員的項（高亮標示）。    所以根據(jù)上述圖所示的結果，程序將最終輸出：“B C B A”。3、5.算法的改進    對于一個具體問題，按照一般的算法設計策略設計出的算法，往往在算法的時間和空間需求上還可以改進。這種改進，通常是利用具體問題的一些特殊性。    例如，在算法LCS_LENGTH和LCS中，可進一步將數(shù)組b省去。事實上，數(shù)組元素ci,j的值僅由ci-1,j-1，ci-1,

24、j和ci,j-1三個值之一確定，而數(shù)組元素bi,j也只是用來指示ci,j究竟由哪個值確定。因此，在算法LCS中，我們可以不借助于數(shù)組b而借助于數(shù)組c本身臨時判斷ci,j的值是由ci-1,j-1，ci-1,j和ci,j-1中哪一個數(shù)值元素所確定，代價是(1)時間。既然b對于算法LCS不是必要的，那么算法LCS_LENGTH便不必保存它。這一來，可節(jié)省(mn)的空間，而LCS_LENGTH和LCS所需要的時間分別仍然是(mn)和(m+n)。不過，由于數(shù)組c仍需要(mn)的空間，因此這里所作的改進，只是在空間復雜性的常數(shù)因子上的改進。    另外，如果只需要計算最長公共

25、子序列的長度，則算法的空間需求還可大大減少。事實上，在計算ci,j時，只用到數(shù)組c的第i行和第i-1行。因此，只要用2行的數(shù)組空間就可以計算出最長公共子序列的長度。更進一步的分析還可將空間需求減至min(m, n)。第四節(jié)、編碼實現(xiàn)LCS問題    動態(tài)規(guī)劃的一個計算最長公共子序列的方法如下，以兩個序列 X、Y 為例子：設有二維數(shù)組 fij 表示 X 的 i 位和 Y 的 j 位之前的最長公共子序列的長度，則有：f11 = same(1

26、,1)fij = maxfi  1j  1 +same(i,j), fi  1j ,fij  1其中，same(a,b)當 X 的第 a 位與 Y 的第 b 位完全相同時為“1”，否則為“0”。此時，fij中最大的數(shù)便是 X 和 Y 的最長公共子序列的長度，依據(jù)該數(shù)組回溯，便可找出最長公共子序列。該算法的空間、時間復雜度均為O(n2)，經(jīng)過優(yōu)化后，空間復雜度可為O(n)，時間復雜度為O(nlogn)。以下是

27、此算法的java代碼：1.    2. import java.util.Random;  3.    4. public class LCS  5.     public static void main(String args)  6.    7.        &

28、#160;/設置字符串長度  8.         int substringLength1 = 20;  9.         int substringLength2 = 20;  /具體大小可自行設置  10.    11.    &

29、#160;    / 隨機生成字符串  12.         String x = GetRandomStrings(substringLength1);  13.         String y = GetRandomStrings(substringLength2); &

30、#160;14.    15.         Long startTime = System.nanoTime();  16.         / 構造二維數(shù)組記錄子問題xi和yi的LCS的長度  17.         int opt&

31、#160;= new intsubstringLength1 + 1substringLength2 + 1;  18.    19.         / 動態(tài)規(guī)劃計算所有子問題  20.         for (int i = substringLengt

32、h1 - 1; i >= 0; i-)  21.             for (int j = substringLength2 - 1; j >= 0; j-)  22.        

33、60;        if (x.charAt(i) = y.charAt(j)  23.                     optij = opti + 1j + 1 + 1;

34、60;                                /參考上文我給的公式。  24.              

35、   else  25.                     optij = Math.max(opti + 1j, optij + 1);        /參考上文我給的公式。 

36、60;26.               27.           28.    29.         -  30.    31.      &#

37、160;  理解上段，參考上文我給的公式：  32.    33.         根據(jù)上述結論，可得到以下公式，  34.    35.         如果我們記字符串Xi和Yj的LCS的長度為ci,j，我們可以遞歸地求ci,j：  36.    37.  

38、;                 /      0                          

39、60;    if i<0 or j<0  38.         ci,j=          ci-1,j-1+1                

40、0;   if i,j>=0 and xi=xj  39.                  /       max(ci,j-1,ci-1,j           

41、;if i,j>=0 and xixj  40.    41.         -  42.    43.         System.out.println("substring1:"+x);  44.     

42、0;   System.out.println("substring2:"+y);  45.         System.out.print("LCS:");  46.    47.         int i = 0, j = 0;&#

43、160; 48.         while (i < substringLength1 && j < substringLength2)  49.             if (x.charAt(i) = y.charAt(j) 

44、; 50.                 System.out.print(x.charAt(i);  51.                 i+;  52.      

45、60;          j+;  53.              else if (opti + 1j >= optij + 1)  54.         &

46、#160;       i+;  55.             else  56.                 j+;  57.     

47、60;     58.         Long endTime = System.nanoTime();  59.         System.out.println(" Totle time is " + (endTime - sta

48、rtTime) + " ns");  60.       61.    62.     /取得定長隨機字符串  63.     public static String GetRandomStrings(int length)  64.    

49、60;    StringBuffer buffer = new StringBuffer("abcdefghijklmnopqrstuvwxyz");  65.         StringBuffer sb = new StringBuffer();  66.       &

50、#160; Random r = new Random();  67.         int range = buffer.length();  68.         for (int i = 0; i < length; i+)

51、  69.             sb.append(buffer.charAt(r.nextInt(range);  70.           71.         return sb.toString();  72. &

52、#160;     73.   第五節(jié)、改進的算法    下面咱們來了解一種不同于動態(tài)規(guī)劃法的一種新的求解最長公共子序列問題的方法,該算法主要是把求解公共字符串問題轉化為求解矩陣L(p,m)的問題，在利用定理求解矩陣的元素過程中（1）while(i<k),L(k,i)=null，                  （2）w

53、hile(L(k,i)=k),L(k,i+1)=L(k,i+2)=L(k,m)=k；    求出每列元素，一直到發(fā)現(xiàn)第p+1 行都為null 時退出循環(huán)，得出矩陣L(k,m)后，BL(1,m-p+1)BL(2,m-p+2)BL(p,m)即為A 和B 的LCS，其中p 為LCS 的長度。6.1 主要定義及定理· 定義 1 子序列(Subsequence)：給定字符串A=A1A2Am，(Ai是A 的第i 個字母，Ai字符集，l<= i<m = A ， A 表示字符串A 的長度)，字符串B 是A 的子序列是指B=A 1 i A 2 i A k i

54、,其中1 i < 2 i << k i 且k<=m.· 定義2 公共子序列(Common Subsequence)：給定字符串A、B、C，C 稱為A 和B 的公共子序列是指C 既是A 的子序列，又是B 的子序列。· 定義3 最長公共子序列(Longest Common Subsequence 簡稱LCS)：給定字符串A、B、C，C 稱為A 和B 的最長公共子序列是指C 是A 和B 的公共子序列，且對于A 和B 的任意公共子序列D，都有D <= C 。給定字符串A 和B，A =m，B =n，不妨設m<=n，LCS 問題就是要求出A 和B 的

55、LCS。· 定義4 給定字符串A=A1A2Am和字符串B=B1B2n，A( 1:i)表示A 的連續(xù)子序列A1A2Ai，同樣B(1:j)表示B 的連續(xù)子序列B1B2j。Li(k)表示所有與字符串A(1:i) 有長度為k 的LCS 的字符串B(l:j) 中j 的最小值。用公式表示就是Li(k)=Minj(LCS(A(1:i)，B(l:j)=k) 3。定理1 i1，m，有Li(l)<Li(2)<Li(3)<<Li(m) .定理2 il，m-1，kl，m，有i 1 L + (k)<= i L (k).定理3 il，m-1， kl，m-l，有i L (k)<

56、 i 1 L + (k+l).以上三個定理都不考慮Li(k)無定義的情況。定理43 i 1 L + (k)如果存在，那么它的取值必為: i 1 L + (k)=Min(j, i L (k)。這里j 是滿足以下條件的最小整數(shù):Ai+l=Bj且j> i L (k-1)。    矩陣中元素L(k，i)=Li(k)，這里(1<i<=m，1<k<=m)，null 表示L(k,i)不存在。當i<k 時，顯然L(k，i)不存在。    設p=Maxk(L(k ， m) null) ， 可以證明L 矩陣中L(p,m

57、) 所在的對角線,L(1,m-p+1),L(2,m-p+2)L(p-1,m-1),L(p,m) 所對應的子序列BL(1,m-p+1)BL(2,m-p+2)BL(p,m)即為A 和B 的LCS，p 為該LCS 的長度。這樣，LCS 問題的求解就轉化為對m m L × 矩陣的求解。6.2 算法思想    根據(jù)定理,第一步求出第一行元素,L(1,1),L(1,2),L(1,m),第二步求第二行,一直到發(fā)現(xiàn)第p+1 行都為null 為止。在計算過程中遇到i<k 時,L(k,i)=null, 及L(k,i)=k時,L(k,i+1)=L(k,i+2)=L(k,m)=k。這樣,計算每行的時間復雜度為O(n),則整個時間復雜度為O(pn)。在求L 矩陣的過程中不用存儲整個矩陣,只需存儲當前行和