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

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à
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: formula_1 và formula_2. Các tiền tố của formula_3 là formula_4; tiền tố của formula_5 là formula_6. Gọi formula_7 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 formula_8 và formula_9. Tập hợp các chuỗi này được định nghĩa như sau.
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"0 = Ø; và "C"0 = Ø. 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"1, "C"1) đượ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"1, "C"0) và "LCS" ("R"0, "C"1). Theo bảng, cả hai đều trống, vì vậy "LCS" ("R"1, "C"1) 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"0, "C"1) và chuỗi đến từ ô ở bên trái, "LCS"("R"1, "C"0).
"LCS" ("R"1, "C"2) đượ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"0, "C"1), là (Ø), cho (ØG), ta được (G).
Đối với "LCS" ("R"1, "C"3), 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"1, "C"3) 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"1, "C"4) và "LCS"("R"1, "C"5) là (G).
Tương tự như vậy, ta hoàn thành hàng "R""2"
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 codice_1 và codice_2, tính LCS giữa codice_3 và codice_4 cho tất cả codice_5 và codice_6, và lưu trữ nó trong codice_7. codice_8 sẽ chứa độ dài LCS của codice_9 và codice_10
 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]