最長公共子序列演算法

Table of content
上一頁
下一頁

最長公共子序列問題是尋找存在於兩個給定字串中的最長序列。

但在我們理解這個問題之前，讓我們先了解一下子序列的含義：

讓我們考慮一個序列S = <s1, s2, s3, s4, …,sn>。另一個序列Z = <z1, z2, z3, …,zm> 在S上被稱為S的子序列，當且僅當它可以透過刪除S中的一些元素得到。簡單來說，子序列由構成序列一部分的連續元素組成。

公共子序列

假設，X 和 Y 是在有限元素集上的兩個序列。如果Z 同時是X 和 Y 的子序列，那麼可以說Z 是X 和 Y 的公共子序列。

最長公共子序列

如果給定一組序列，最長公共子序列問題就是找到所有序列的公共子序列中長度最大的一個。

樸素方法

令X 為長度為m的序列，Y 為長度為n的序列。檢查X 的每個子序列是否也是Y 的子序列，並返回找到的最長公共子序列。

X 有2m 個子序列。測試序列是否為Y 的子序列需要O(n)時間。因此，樸素演算法的時間複雜度為O(n2m)。

最長公共子序列演算法

設X=<x1,x2,x3....,xm> 和 Y=<y1,y2,y3....,ym> 為序列。為了計算一個元素的長度，使用以下演算法。

步驟1 - 構造一個空的鄰接表，大小為n × m，其中n = 序列X 的大小，m = 序列Y 的大小。表中的行代表序列X中的元素，列代表序列Y中的元素。

步驟2 - 第零行和第零列必須填充為零。其餘值根據不同的情況填充，同時維護一個計數器值。

  • 情況1 - 如果計數器在X和Y序列中遇到公共元素，則計數器加1。

  • 情況2 - 如果計數器在T[i, j]處沒有在X和Y序列中遇到公共元素，則找到T[i-1, j]和T[i, j-1]之間的最大值來填充T[i, j]。

步驟3 - 表格填充完成後，從表格中的最後一個值回溯。這裡的回溯是透過追蹤計數器首次遞增的路徑來完成的。

步驟4 - 透過記錄追蹤路徑中的元素來獲得最長公共子序列。

虛擬碼

在這個過程中，表格C[m, n]以行優先順序計算，另一個表格B[m,n]用於構造最優解。

Algorithm: LCS-Length-Table-Formulation (X, Y)
m := length(X)
n := length(Y)
for i = 1 to m do
   C[i, 0] := 0
for j = 1 to n do
   C[0, j] := 0
for i = 1 to m do
   for j = 1 to n do
      if xi = yj
         C[i, j] := C[i - 1, j - 1] + 1
         B[i, j] := ‘D’
      else
         if C[i -1, j] ≥ C[i, j -1]
            C[i, j] := C[i - 1, j] + 1
            B[i, j] := ‘U’
         else
            C[i, j] := C[i, j - 1] + 1
            B[i, j] := ‘L’
return C and B

Algorithm: Print-LCS (B, X, i, j)
if i=0 and j=0
   return
if B[i, j] = ‘D’
   Print-LCS(B, X, i-1, j-1)
   Print(xi)
else if B[i, j] = ‘U’
   Print-LCS(B, X, i-1, j)
else
   Print-LCS(B, X, i, j-1)

此演算法將列印X和Y的最長公共子序列。

分析

為了填充表格，外層for迴圈迭代m次，內層for迴圈迭代n次。因此，演算法的複雜度為O(m,n)，其中m和n是兩個字串的長度。

示例

在這個例子中，我們有兩個字串X=BACDB 和 Y=BDCB，需要找到最長公共子序列。

根據演算法，我們需要計算表1和表2。

給定n = X的長度，m = Y的長度

X = BDCB, Y = BACDB

構造LCS表

在下表中，第零行和第零列填充為零。其餘值根據演算法遞增和選擇最大值來填充。

table1

值填充完成後，從T[4, 5]處的表中最後一個值回溯路徑。

table2

從追蹤的路徑中，透過選擇計數器首次遞增的值來找到最長公共子序列。

在這個例子中，最終計數是3，因此計數器在3個位置遞增，即B，C，B。因此，序列X和Y的最長公共子序列是BCB。

實現

以下是使用動態規劃方法查詢最長公共子序列的最終實現：

C C++ Java Python
#include <stdio.h>
#include <string.h>
int max(int a, int b);
int lcs(char* X, char* Y, int m, int n){
   int L[m + 1][n + 1];
   int i, j, index;
   for (i = 0; i <= m; i++) {
      for (j = 0; j <= n; j++) {
         if (i == 0 || j == 0)
            L[i][j] = 0;
         else if (X[i - 1] == Y[j - 1]) {
            L[i][j] = L[i - 1][j - 1] + 1;
         } else
            L[i][j] = max(L[i - 1][j], L[i][j - 1]);
      }
   }
   index = L[m][n];
   char LCS[index + 1];
   LCS[index] = '\0';
   i = m, j = n;
   while (i > 0 && j > 0) {
      if (X[i - 1] == Y[j - 1]) {
         LCS[index - 1] = X[i - 1];
         i--;
         j--;
         index--;
      } else if (L[i - 1][j] > L[i][j - 1])
         i--;
      else
         j--;
   }
   printf("LCS: %s\n", LCS);
   return L[m][n];
}
int max(int a, int b){
   return (a > b) ? a : b;
}
int main(){
   char X[] = "ABSDHS";
   char Y[] = "ABDHSP";
   int m = strlen(X);
   int n = strlen(Y);
   printf("Length of LCS is %d\n", lcs(X, Y, m, n));
   return 0;
}

輸出

LCS: ABDHS
Length of LCS is 5

#include <bits/stdc++.h>
using namespace std;
int max(int a, int b);
int lcs(char* X, char* Y, int m, int n){
   int L[m + 1][n + 1];
   int i, j, index;
   for (i = 0; i <= m; i++) {
      for (j = 0; j <= n; j++) {
         if (i == 0 || j == 0)
            L[i][j] = 0;
         else if (X[i - 1] == Y[j - 1]) {
            L[i][j] = L[i - 1][j - 1] + 1;
         } else
            L[i][j] = max(L[i - 1][j], L[i][j - 1]);
      }
   }
   index = L[m][n];
   char LCS[index + 1];
   LCS[index] = '\0';
   i = m, j = n;
   while (i > 0 && j > 0) {
      if (X[i - 1] == Y[j - 1]) {
         LCS[index - 1] = X[i - 1];
         i--;
         j--;
         index--;
      } else if (L[i - 1][j] > L[i][j - 1])
         i--;
      else
         j--;
   }
   printf("LCS: %s\n", LCS);
   return L[m][n];
}
int max(int a, int b){
   return (a > b) ? a : b;
}
int main(){
   char X[] = "ABSDHS";
   char Y[] = "ABDHSP";
   int m = strlen(X);
   int n = strlen(Y);
   printf("Length of LCS is %d\n", lcs(X, Y, m, n));
   return 0;
}

輸出

LCS: ABDHS
Length of LCS is 5

import java.util.*;
public class LCS_ALGO {
    public static int max(int a, int b){
        if( a > b){
            return a;
        }
        else{
            return b;
        }
    }
  static int lcs(char arr1[], char arr2[], int m, int n) {
    int[][] L = new int[m + 1][n + 1];
    // Building the mtrix in bottom-up way
    for (int i = 0; i <= m; i++) {
      for (int j = 0; j <= n; j++) {
        if (i == 0 || j == 0)
          L[i][j] = 0;
        else if (arr1[i - 1] == arr2[j - 1])
          L[i][j] = L[i - 1][j - 1] + 1;
        else
          L[i][j] = max(L[i - 1][j], L[i][j - 1]);
      }
    }

    int index = L[m][n];
    int temp = index;

    char[] lcs = new char[index + 1];
    lcs[index] = '\0';

    int i = m, j = n;
    while (i > 0 && j > 0) {
      if (arr1[i - 1] == arr2[j - 1]) {
        lcs[index - 1] = arr1[i - 1];

        i--;
        j--;
        index--;
      }
      else if (L[i - 1][j] > L[i][j - 1])
        i--;
      else
        j--;
    }
    System.out.print("LCS: ");
    for(i = 0; i<=temp; i++){
        System.out.print(lcs[i]);
    }
    System.out.println();
    return L[m][n];
  }

  public static void main(String[] args) {
    String S1 = "ABSDHS";
    String S2 = "ABDHSP";
    char ch1[] = S1.toCharArray();
    char ch2[] = S2.toCharArray();
    int m = ch1.length;
    int n = ch2.length;
    System.out.println("Length of LCS is: " + lcs(ch1, ch2, m, n));
  }
}

輸出

LCS: ABDHS
Length of LCS is: 5

def lcs(X, Y, m, n):
   L = [[None]*(n+1) for a in range(m+1)]
   for i in range(m+1):
      for j in range(n+1):
         if (i == 0 or j == 0):
            L[i][j] = 0
         elif (X[i - 1] == Y[j - 1]):
            L[i][j] = L[i - 1][j - 1] + 1
         else:
            L[i][j] = max(L[i - 1][j], L[i][j - 1])
   l = L[m][n]
   LCS = [None] * (l)
   a = m
   b = n
   while (a > 0 and b > 0):
      if (X[a - 1] == Y[b - 1]):
         LCS[l - 1] = X[a - 1]
         a = a - 1
         b = b - 1
         l = l - 1
      elif (L[a - 1][b] > L[a][b - 1]):
         a = a - 1
      else:
         b = b - 1;
   print("LCS is ")
   print(LCS)
   return L[m][n]

X = "ABSDHS"
Y = "ABDHSP"
m = len(X)
n = len(Y)
lc = lcs(X, Y, m, n)
print("Length of LCS is ")
print(lc)

輸出

LCS is 
['A', 'B', 'D', 'H', 'S']
Length of LCS is 
5

應用

最長公共子序列問題是一個經典的計算機科學問題，它是諸如diff實用程式之類的資料庫比較程式的基礎，並且在生物資訊學中也有應用。它也被廣泛用於版本控制系統（如SVN和Git）中，用於協調對版本控制的檔案集合所做的多個更改。

列印頁面
上一頁
下一頁
廣告
© . All rights reserved.