Dãy con chung dài nhất (LCS)
Khi so sánh hai phiên bản của một tệp, những dòng không thay đổi là một dãy con chung của cả hai. Tìm ra dãy dài nhất cho bạn biết chính xác những gì đã được thêm vào và những gì đã bị xóa. Cùng ý tưởng đó giúp gióng hàng các chuỗi DNA và gợi ý sửa lỗi chính tả, và bài toán được giải bằng một trong những bảng thanh lịch nhất của khoa học máy tính.
Bài toán
Dãy con của một từ giữ lại một số chữ cái của nó theo đúng thứ tự ban đầu: ACE là dãy con của ABCDE, nhưng EA thì không. Dãy con chung của hai từ là dãy con của cả hai, và bài toán là tìm dãy dài nhất. Một từ dài n có 2ⁿ dãy con, nên thử hết tất cả là vô vọng khi từ dài hơn vài chữ cái.
Bảng
Gọi len[i][j] là độ dài dãy con chung dài nhất của i chữ cái đầu của một từ và j chữ cái đầu của từ kia. Một từ rỗng không có gì chung với từ nào, nên hàng và cột đầu tiên bằng 0. Nếu chữ thứ i bằng chữ thứ j thì len[i][j] = len[i − 1][j − 1] + 1: chỗ khớp này kéo dài phần đứng trước nó. Nếu không, len[i][j] là giá trị lớn hơn giữa len[i − 1][j] và len[i][j − 1]: bỏ một trong hai chữ cái và giữ kết quả tốt hơn.
Một ví dụ
So sánh ABCBDAB với BDCABA. Chữ cái đầu tiên của từ thứ hai, B, khớp với chữ B ở hàng 2; chữ C ở cột thứ ba khớp với hàng 3, và cứ thế tiếp tục, mỗi chỗ khớp cộng thêm một vào ô phía trên bên trái. Ô dưới cùng bên phải cuối cùng bằng 4. Đọc ngược từ đó cho BCBA, nhưng BCAB và BDAB cũng dài như vậy: dãy con chung dài nhất không nhất thiết là duy nhất.
Đọc ngược đáp án
Bắt đầu ở ô dưới cùng bên phải. Nếu chữ cái ở hàng và cột của ô khớp nhau, chữ đó thuộc đáp án: ghi lại rồi đi chéo lên phía trên bên trái. Nếu không, đi sang ô lân cận phía trên hoặc bên trái có giá trị lớn hơn, vì ô hiện tại lấy giá trị từ đó. Dừng lại ở hàng hoặc cột đầu tiên. Các chữ cái đã ghi, đảo ngược thứ tự, chính là dãy con.
Lịch sử và ứng dụng
Phương pháp bảng được nhiều người tìm ra độc lập vào khoảng năm 1970, trong đó có Robert Wagner và Michael Fischer, với bài báo năm 1974 giải bài toán khoảng cách chỉnh sửa có liên quan chặt chẽ. Năm 1975, Dan Hirschberg chỉ ra cách tìm dãy con với ít bộ nhớ hơn nhiều, và năm 1976, James Hunt và Douglas McIlroy xây dựng chương trình Unix diff dựa trên dãy con chung dài nhất của các dòng. Các nhà sinh học dùng cùng ý tưởng, có thêm điểm số, để gióng hàng các trình tự DNA và protein.
Tự khám phá
Mở ứng dụng và nhấn Bước. Hai chữ cái đang được so sánh sáng lên ở phần tiêu đề; khi khớp thì đọc ô xanh phía trên bên trái, khi không khớp thì đọc hai ô xanh phía trên và bên trái. Khi bảng đã đầy, đường màu cam leo ngược lên từ góc và các chữ cái của đáp án hiện ra bên dưới bảng.
Câu hỏi thường gặp
Thuật toán LCS cần bao nhiêu thời gian và bộ nhớ?
Thời gian O(m·n) với hai từ có độ dài m và n. Toàn bộ bảng cũng cần bộ nhớ O(m·n) để đọc ngược đáp án; năm 1975, Dan Hirschberg đã chỉ ra cách tìm chính dãy con chỉ với bộ nhớ O(min(m, n)).
diff dùng dãy con chung dài nhất như thế nào?
Nó coi mỗi dòng của tệp là một ký hiệu và tìm dãy con chung dài nhất giữa các dòng của hai tệp. Các dòng nằm trong dãy con đó không thay đổi; các dòng còn lại của tệp cũ đã bị xóa, còn các dòng còn lại của tệp mới đã được thêm vào.
Nếu có ba từ trở lên thì sao?
Bảng có thêm một chiều cho mỗi từ, nên ba từ dài n cần n³ ô. Với số lượng từ bất kỳ, bài toán là NP-khó.
LCS liên quan thế nào đến khoảng cách chỉnh sửa?
Nếu chỉ cho phép chèn và xóa, khoảng cách chỉnh sửa của hai từ bằng tổng độ dài của chúng trừ đi hai lần độ dài dãy con chung dài nhất. Nếu cho phép cả thay thế, ta được khoảng cách Levenshtein, được tính bằng một bảng rất giống.
Sẵn sàng thử chưa?
Mở PictorX trong trình duyệt — không cần cài đặt, không cần thẻ tín dụng để bắt đầu.
Thử dãy con chung dài nhất