最長公共子序列

最長公共子序列LCS)是一個在一個序列集合中(通常為兩個序列)用來尋找所有序列中最長子序列的問題。這與尋找最長公共子串的問題不同的地方是:子序列不需要在原序列中佔用連續的位置 。最長公共子序列問題是一個經典的電腦科學問題,也是數據比較英語data comparison程式,比如Diff工具,和生物資訊科學應用的基礎。它也被廣泛地應用在版本控制,比如Git用來調和檔案之間的改變。

定義

一個數列 ,如果分別是兩個或多個已知數列的子序列,且是所有符合此條件序列中最長的,則 稱為已知序列的最長公共子序列。

複雜度

對於一般性的LCS問題(即任意數量的序列)是屬於NP-hard。但當序列的數量確定時,問題可以使用動態規劃(Dynamic Programming)在多項式時間內解決。[1]

兩個序列的解法

最長公共子序列問題存在最佳子結構:這個問題可以分解成更小,更簡單的「子問題」,這個子問題可以分成更多的子問題,因此整個問題就變得簡單了。最長公共子序列問題的子問題的解是可以重複使用的,也就是說,更進階別的子問題通常會重用低階子問題的解。擁有這個兩個屬性的問題可以使用動態規劃演算法來解決,這樣子問題的解就可以被儲存起來,而不用重複計算。這個過程需要在一個表中儲存同一級別的子問題的解,因此這個解可以被更進階的子問題使用。

動態規劃的一個計算最長公共子序列的方法如下,以兩個序列  為例子:

設有二維陣列 表示  位和  位之前的最長公共子序列的長度,則有:

 
 

其中,  的第 位與 的第 位完全相同時為「1」,否則為「0」。

此時, 中最大的數便是  的最長公共子序列的長度,依據該陣列回溯,便可找出最長公共子序列。

演算法的空間、時間複雜度均為 ,經過最佳化後,空間複雜度可為 

計算LCS的長度

下面演算法計算了所有子問題的最長公共子序列長度C[i,j]

function LCSLength(X[1..m], Y[1..n])
    C = array(0..m, 0..n)
    for i := 0..m
       C[i,0] = 0
    for j := 0..n
       C[0,j] = 0
    for i := 1..m
        for j := 1..n
            if X[i] = Y[j]
                C[i,j] := C[i-1,j-1] + 1
            else
                C[i,j] := max(C[i,j-1], C[i-1,j])
    return C[m,n]

參見

參照

  1. ^ 屈, 婉玲. 算法设计与分析. 北京清華大學學研大廈A座: 清華大學出版社. 2011: 67. ISBN 978-7-302-24756-2. 

外部連結