一、基本概念

????????LCS是最長公共子序列（Longest common subsequence problem）的縮寫。LCS問題是在一組序列（通常只有兩個序列）中找到所有序列共有的最長子序列的問題。它與最長公共子串問題不同：與子串不同，子序列不需要占據原始序列中的連續位置。最長公共子序列問題是經典的計算機科學問題，是 diff 實用程序等數據比較程序的基礎，在計算語言學和生物信息學中有應用。它還被 Git 等版本控制系統廣泛用于協調對受版本控制的文件集合所做的多項更改。

????????例如，考慮序列 (ABCD) 和 (ACBAD)。它們有 5 個長度為 2 的公共子序列：(AB)、(AC)、(AD)、(BD) 和 (CD)； 2個長度為3的公共子序列：（ABD）和（ACD）；并且不再有更長的公共子序列。所以 (ABD) 和 (ACD) 是它們最長的公共子序列。

• 復雜度：

????????對于任意數量的輸入序列的一般情況，問題是 NP-hard。[1]當序列數不變時，該問題可通過動態規劃在多項式時間內求解。

二、兩個序列的解決方案

????????LCS 問題有一個最優子結構：問題可以分解為更小、更簡單的子問題，而這些子問題又可以分解為更簡單的子問題，依此類推，直到最終解決方案變得微不足道。 LCS 尤其具有重疊的子問題：高級子問題的解決方案通常重用低級子問題的解決方案。具有這兩個屬性的問題適用于動態規劃方法，其中子問題解決方案被記憶，即子問題的解決方案被保存以供重用。

S的前綴定義為S的前n個字符[5]例如，S = (AGCA) 的前綴是

假設 LCS(X, Y) 是一個計算 X 和 Y 共有的最長子序列的函數。這樣的函數有兩個有趣的屬性。

2.1 第一個屬性

• 兩個字符串具有相同尾序，那么同時去掉兩者的尾序，不影響它們的距離

LCS(X^A,Y^A) = LCS(X,Y)^A，對于所有字符串 X、Y 和所有符號 A，其中 ^ 表示字符串連接。這允許簡化以相同符號結尾的兩個序列的 LCS 計算。例如，LCS("BANANA","ATANA") = LCS("BANAN","ATAN")^"A"，繼續其余常用符號，LCS("BANANA","ATANA") = LCS("BAN","AT")^"ANA"。

2.2 第二個屬性

• 如果 A 和 B 是不同的符號 (A≠B)，則 LCS(X^A,Y^B) 是以下兩者的最大者：LCS(X^A,Y), LCS(X,Y ^B) }，適用于所有字符串 X、Y。

例如，LCS("ABCDEFG","BCDGK") 是 LCS("ABCDEFG","BCDG") 和 LCS("ABCDEF","BCDGK") 中最長的字符串；如果兩者碰巧長度相等，則可以任意選擇其中之一。

????????證明，分兩種情況：

• 如果 以 結尾，那么最后的不能在 LCS 中，因此 。

• 如果 不以 結尾，則最后的 不能在 LCS 中，因此。

2.3 LCS 函數的定義

????????讓兩個序列定義如下：和 。 的前綴是; 的前綴是。令?表示最長的集合前綴 和 ?的公共子序列。這組序列由以下給出。

????????要找到?? 和 的 ，請比較 和 。如果它們相等，則序列
由擴展成?。如果它們不相等，則下面兩個序列中最長的被保留， 和 。 （如果它們的長度相同，則保留兩者。）

三、兩個序列的應用實例

?????????示例：找到 R = (GAC) 和 C = (AGCAT) 共有的最長子序列。因為 LCS 函數使用“第零”元素，所以為這些序列定義空的零前綴很方便：R0 = ?;和 C0 = ?。所有前綴都放在一個表中，第一行是 C（使其成為列標題），第一列是 R（使其成為行標題）。

????????該表用于存儲每個計算步驟的 LCS 序列。第二列和第二行已經用?填充了，因為當一個空序列與一個非空序列進行比較時，最長的公共子序列總是一個空序列。

????????LCS(R1, C1) 通過比較每個序列中的第一個元素來確定。 G 和 A 不相同，所以這個 LCS 獲得（使用“第二個屬性”）兩個序列中最長的一個，LCS(R1, C0) 和 LCS(R0, C1)。根據表格，這兩個都是空的，所以 LCS(R1, C1) 也是空的，如下表所示。箭頭表示序列來自上方的單元格 LCS(R0, C1) 和左側的單元格 LCS(R1, C0)。

????????LCS(R1,C2)是通過比較G和G來確定的。它們匹配，所以將G附加到左上序列，LCS(R0,C1)，即(?)，給出(?G)，即(G) .

????????對于 LCS(R1, C3)，G 和 C 不匹配。上面的序列是空的；左邊的一個包含一個元素，G。選擇其中最長的一個，LCS（R1，C3）是（G）。箭頭指向左側，因為這是兩個序列中最長的。

LCS(R1,?C4), likewise, is (G).

LCS(R1,?C5), likewise, is (G).

????????對于 LCS(R2, C1)，將 A 與 A 進行比較。兩個元素匹配，因此將 A 附加到 ?，得到 (A)。

????????對于LCS(R2,C2)，A和G不匹配，所以使用LCS(R1,C2)中最長的(G)和LCS(R2,C1)中最長的(A)。在這種情況下，它們每個都包含一個元素，因此這個 LCS 有兩個子序列：(A) 和 (G)。

????????對于 LCS(R2, C3)，A 與 C 不匹配。 LCS(R2, C2) 包含序列 (A) 和 (G)； LCS(R1, C3) 是 (G)，它已經包含在 LCS(R2, C2) 中。結果是 LCS(R2, C3) 還包含兩個子序列 (A) 和 (G)。

????????對于 LCS(R2, C4)，A 匹配附加到左上角單元格的 A，給出 (GA)。

????????對于LCS(R2,C5)，A不匹配T。比較(GA)和(G)這兩個序列，最長的是(GA)，所以LCS(R2,C5)就是(GA)。

對于 LCS(R3, C1)，C 和 A 不匹配，因此 LCS(R3, C1) 獲得兩個序列中最長的 (A)。

對于 LCS(R3, C2)，C 和 G 不匹配。 LCS(R3, C1) 和 LCS(R2, C2) 都有一個元素。結果是 LCS(R3, C2) 包含兩個子序列，(A) 和 (G)。

對于 LCS(R3, C3)，C 和 C 匹配，因此 C 被附加到 LCS(R2, C2) 中，其中包含 (A) 和 (G) 兩個子序列，得到 (AC) 和 (GC)。

對于 LCS(R3, C4)，C 和 A 不匹配。將包含 (AC) 和 (GC) 的 LCS(R3, C3) 和包含 (GA) 的 LCS(R2, C4) 組合起來，總共得到三個序列：(AC)、(GC) 和 (GA) ）。

最后，對于 LCS(R3, C5)，C 和 T 不匹配。結果是 LCS(R3, C5) 還包含三個序列，(AC)、(GC) 和 (GA)。

????????最終的結果是最后一個單元格包含了（AGCAT）和（GAC）共有的所有最長子序列；它們是 (AC)、(GC) 和 (GA)。該表還顯示了每對可能的前綴的最長公共子序列。例如，對于 (AGC) 和 (GA)，最長的公共子序列是 (A) 和 (G)。

四、追溯方法

????????計算LCS表中一行的LCS只需要當前行和上一行的解。盡管如此，對于長序列，這些序列可能會變得很多而且很長，需要大量的存儲空間。存儲空間可以通過保存的不是實際的子序列，而是子序列的長度和箭頭的方向來節省，如下表所示。

?

?????????實際的子序列在“追溯”過程中推導出來，該過程從表中的最后一個單元格開始，沿著箭頭向后。當長度減小時，這些序列必須有一個共同的元素。當一個單元格中顯示兩個箭頭時，可能有多個路徑。下表是此類分析的表格，其中長度即將減少的單元格中帶有顏色的數字。粗體數字描繪了序列，（GA）。

總結

以上是生活随笔為你收集整理的编辑距离：最长公共子序列-LCS问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。