✨Bài toán chuỗi con chung dài nhất

nhỏ|So sánh hai bản sửa đổi của một tệp ví dụ, dựa trên dãy con chung dài nhất của chúng (màu đen) Vấn đề chuỗi con chung dài nhất (tiếng anh: Longest common subsequence - LCS) là vấn đề trong việc tìm kiếm một chuỗi con chung dài nhất cho tất cả các chuỗi trong một bộ chuỗi (thường chỉ hai chuỗi). Nó khác với vấn đề về xâu con chung dài nhất ở chỗ: không giống như các xâu con, các chuỗi con không bắt buộc phải chiếm các vị trí liên tiếp trong các chuỗi ban đầu. Bài toán chuỗi con chung dài nhất là một trong những bài toán khoa học máy tính cổ điển, là cơ sở của các chương trình so sánh dữ liệu như diff, và có các ứng dụng trong ngôn ngữ học tính toán và tin sinh học. Nó cũng được sử dụng rộng rãi bởi các hệ thống quản lý phiên bản như Git để điều chỉnh nhiều thay đổi được thực hiện cho một bộ sưu tập tệp được kiểm soát sửa đổi.

Ví dụ, hãy xem xét các chuỗi (ABCD) và (ACBAD). Chúng có 5 chuỗi con chung có độ dài bằng 2: (AB), (AC), (AD), (BD) và (CD); 2 chuỗi con chung có độ dài bằng 3: (ABD) và (ACD); và không còn chuỗi con chung nào khác có độ dài lớn hơn nữa. Vì vậy (ABD) và (ACD) là hai dãy con chung dài nhất của hai chuỗi ban đầu.

Độ phức tạp

Đối với trường hợp tổng quát với số lượng chuỗi trình tự đầu vào là tùy ý, vấn đề là NP-khó. Khi số lượng chuỗi trình tự không đổi, bài toán có thể giải được trong thời gian đa thức bằng quy hoạch động.

Thuật toán cho hai chuỗi

Bài toán LCS có một cấu trúc con tối ưu: Có nghĩa là bài toán có thể được chia thành các bài toán con nhỏ hơn và đơn giản hơn, và các chính bài toán con cũng được chia thành các bài toán con đơn giản hơn, và cứ thế, cho đến khi, cuối cùng, nghiệm của bài toán trở nên đơn giản và dễ nhận thấy. LCS nói riêng có các bài toán con chồng chéo: các nghiệm cho các bài toán con cấp cao sẽ sử dụng lại các nghiệm cho các bài toán con cấp thấp hơn. Các vấn đề với hai thuộc tính này có thể giải quyết được bằng quy hoạch động, trong đó các nghiệm của bài toán con sẽ được lưu lại để xử lý lúc sau.

Tiền tố

Ta định nghĩa tiền tố S_n của S là chuỗi chứa n ký tự đầu tiên của S. Ví dụ: các tiền tố của S = (AGCA) là

: S₀ = () : S₁ = (A) : S₂ = (AG) : S₃ = (AGC) : S₄ = (AGCA).

Gọi LCS(X, Y) là một hàm tính toán chuỗi con chung dài nhất cho X và Y. Một hàm như vậy có hai tính chất đặc biệt như sau:

Tính chất đầu tiên

LCS(X^A, Y^A) = LCS (X, Y)^A, cho tất cả các chuỗi X, Y và tất cả các ký hiệu A, trong đó dấu ^ biểu thị phép nối xâu. Điều này cho phép chúng ta đơn giản hóa việc tính toán LCS cho hai chuỗi kết thúc cùng một ký hiệu. Ví dụ: LCS ("BANANA", "ATANA") = LCS ("BANAN", "ATAN") ^ "A", Tiếp tục cho các ký hiệu chung còn lại, LCS ("BANANA", "ATANA") = LCS (" BAN "," AT ") ^" ANA".

Tính chất thứ hai

Nếu A và B là hai ký hiệu riêng biệt (A≠B), thì LCS (X^A, Y^B) là một trong hai xâu có độ dài cực đại trong tập {LCS(X^A, Y), LCS(X, Y^B)}, cho tất cả các xâu X và Y.

Ví dụ: LCS ("ABCDEFG", "BCDGK") là xâu dài hơn của LCS ("ABCDEFG", "BCDG") và LCS ("ABCDEF", "BCDGK"); nếu cả hai có độ dài bằng nhau, ta có thể chọn tùy ý một trong những chuỗi thỏa mãn.

Định nghĩa hàm LCS

Cho hai chuỗi được xác định như sau: $X=(x\_1\; x\_2\; \backslash cdots\; x\_m)$ và $Y=(y\_1\; y\_2\; \backslash cdots\; y$n). Các tiền tố của $X$ là $X${1,2,\dots,m}; tiền tố của $Y$ là $Y\_\{1,2,\backslash dots,n\}$. Gọi $\backslash mathit\{LCS\}(X\_i,Y\_j)$ là đại diện cho tập hợp các chuỗi con chung dài nhất cho các tiền tố của $X\_i$ và $Y\_j$. Tập hợp các chuỗi này được định nghĩa như sau.

: $\backslash mathit\{LCS\}(X\_i,Y$j)=\begin{cases} \empty & \mbox{if }i=0\mbox{ or }j=0 \ \mathit{LCS}(X{i-1},Y_{j-1}) \hat{} x_i & \mbox{if }i,j>0\mbox{ and }x_i=y_j \ \operatorname{\max}{\mathit{LCS}(Xi,Y{j-1}),\mathit{LCS}(X_{i-1},Y_j)} & \mbox{if }i,j>0\mbox{ and }x_i\ne y_j. \end{cases}

Làm việc với ví dụ

Để lấy ví dụ, ta sẽ tìm chuỗi con dài nhất chung cho hai xâu R = (GAC) và C = (AGCAT). Vì hàm LCS xét từ vị trí 0, nên để thuận tiện, ta sẽ xác định các tiền tố 0 là trống cho các chuỗi này: R₀ = Ø; và C₀ = Ø. Tất cả các tiền tố được đặt trong một bảng với C ở hàng đầu tiên và R ở cột đầu tiên:

Bảng này được sử dụng để lưu trữ trình tự tính LCS cho mỗi bước tính toán. Cột thứ hai và hàng thứ hai đã được điền bằng Ø, bởi vì khi một chuỗi trống được so sánh với một chuỗi không trống, chuỗi con chung dài nhất luôn là chuỗi trống.

LCS (R₁, C₁) được xác định bằng cách so sánh các phần tử đầu tiên trong mỗi chuỗi. G và A không giống nhau, vì vậy LCS này nhận (sử dụng tính chất thứ hai trên) chuỗi dài nhất trong hai chuỗi, LCS(R₁, C₀) và LCS (R₀, C₁). Theo bảng, cả hai đều trống, vì vậy LCS (R₁, C₁) cũng trống. Các mũi tên biểu thị chuỗi nhập vào: chuỗi đến từ ô ở trên, LCS (R₀, C₁) và chuỗi đến từ ô ở bên trái, LCS(R₁, C₀).

LCS (R₁, C₂) được xác định bằng cách so sánh G và G. Chúng khớp với nhau, nên G được nối vào chuỗi phía trên bên trái, LCS(R₀, C₁), là (Ø), cho (ØG), ta được (G).

Đối với LCS (R₁, C₃), G và C không khớp. Chuỗi trên trống; Chuỗi bên trái chứa một phần tử, (G). Chọn phần tử có độ dài dài nhất trong hai chuỗi này, ta được LCS (R₁, C₃) là (G). Mũi tên chỉ sang trái, vì đó là chuỗi dài nhất trong hai chuỗi.

Tương tự như vậy, LCS(R₁, C₄) và LCS(R₁, C₅) là (G).

Tương tự như vậy, ta hoàn thành hàng R₂

Bảng hoàn thiện cuối cùng là

Mã cho giải pháp quy hoạch động

Tính độ dài của LCS

Hàm bên dưới nhận như chuỗi đầu vào X[1..m] và Y[1..n], tính LCS giữa X[1..i] và Y[1..j] cho tất cả 1 ≤ i ≤ m và 1 ≤ j ≤ n, và lưu trữ nó trong C[i,j]. C[m,n] sẽ chứa độ dài LCS của X và Y 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]