Bài 6: Từ sửa lỗi chính tả đến giải mã DNA: khoảng cách chỉnh sửa và quy hoạch động

Bạn gõ nhầm "algoritm", điện thoại gợi ý ngay "algorithm". Lập trình viên gõ git diff để xem mình đã sửa dòng code nào. Các nhà sinh học so sánh gen của người và chuột. Ba việc tưởng chẳng liên quan này dùng chung một ý tưởng: đo "khoảng cách" giữa hai chuỗi bằng quy hoạch động.

Bài thứ sáu của chuyên mục "Thuật toán trong đời sống". Nếu bạn đã học quy hoạch động (QHĐ) trong chương trình chuyên Tin, bài này sẽ cho bạn thấy nó "đáng giá" đến mức nào ngoài đời thực.

1. Khoảng cách Levenshtein: hai từ "xa" nhau bao nhiêu?

Năm 1965, nhà toán học Liên Xô Vladimir Levenshtein định nghĩa khoảng cách giữa hai chuỗi là số phép biến đổi ít nhất – chèn, xóa hoặc thay một ký tự – để biến chuỗi này thành chuỗi kia. Ví dụ: "algoritm" → "algorithm" chỉ cần 1 phép chèn chữ h.

Trước đó, năm 1964, Fred Damerau đã đề xuất kỹ thuật phát hiện và sửa lỗi chính tả trên máy tính, xử lý các lỗi gõ sai một chữ, thiếu một chữ, thừa một chữ, hoặc đảo vị trí hai chữ cạnh nhau.

Công thức quy hoạch động

Gọi f[i][j] là khoảng cách giữa i ký tự đầu của chuỗi a và j ký tự đầu của chuỗi b:

f[i][j] = min( f[i−1][j] + 1 (xóa a[i]), f[i][j−1] + 1 (chèn b[j]), f[i−1][j−1] + (a[i] ≠ b[j]) (thay hoặc giữ nguyên) ), với f[i][0] = i và f[0][j] = j.

Bảng QHĐ cho cặp từ "saturday" và "sunday" (đáp án ở ô cuối: 3):

	∅	s	u	n	d	a	y
∅	0	1	2	3	4	5	6
s	1	0	1	2	3	4	5
a	2	1	1	2	3	3	4
t	3	2	2	2	3	4	4
u	4	3	2	3	3	4	5
r	5	4	3	3	4	4	5
d	6	5	4	4	3	4	5
a	7	6	5	5	4	3	4
y	8	7	6	6	5	4	3

Độ phức tạp O(n × m) – bài toán mà Viện Tiêu chuẩn và Công nghệ Mỹ (NIST) mô tả là giải bằng quy hoạch động Θ(m × n).

Code: bộ gợi ý sửa lỗi chính tả mini

Code C++ và Python

#include <bits/stdc++.h>
using namespace std;
// Khoảng cách Levenshtein: số phép chèn / xóa / thay ít nhất để biến a thành b
int editDistance(const string& a, const string& b){
    int n = a.size(), m = b.size();
    vector<vector<int>> f(n + 1, vector<int>(m + 1));
    for(int i = 0; i <= n; i++) f[i][0] = i;
    for(int j = 0; j <= m; j++) f[0][j] = j;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            f[i][j] = min({ f[i-1][j] + 1,                       // xóa
                            f[i][j-1] + 1,                       // chèn
                            f[i-1][j-1] + (a[i-1] != b[j-1]) }); // thay (hoặc giữ)
    return f[n][m];
}
int main(){
    vector<string> dict = {"algorithm", "logarithm", "rhythm", "altruism"};
    string typed = "algoritm";
    for(auto& w : dict)
        cout << w << ": " << editDistance(typed, w) << "\n";
}

def edit_distance(a, b):
    n, m = len(a), len(b)
    f = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(n + 1): f[i][0] = i
    for j in range(m + 1): f[0][j] = j
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            f[i][j] = min(f[i-1][j] + 1,                      # xóa
                          f[i][j-1] + 1,                      # chèn
                          f[i-1][j-1] + (a[i-1] != b[j-1]))   # thay
    return f[n][m]

dictionary = ["algorithm", "logarithm", "rhythm", "altruism"]
typed = "algoritm"
print(sorted(dictionary, key=lambda w: edit_distance(typed, w)))
for w in dictionary:
    print(w, edit_distance(typed, w))

Với từ gõ sai "algoritm", chương trình tính khoảng cách đến từng từ trong từ điển: algorithm = 1, logarithm = 4, altruism = 4, rhythm = 7 – và gợi ý algorithm.

Bộ sửa chính tả thật hoạt động thế nào?

Trong bài luận nổi tiếng "How to Write a Spelling Corrector", Peter Norvig (từng là Giám đốc nghiên cứu của Google) viết một bộ sửa lỗi chính tả chỉ khoảng nửa trang code. Ý tưởng là chọn từ c có xác suất cao nhất, kết hợp hai yếu tố:

• Mô hình ngôn ngữ P(c): từ c phổ biến đến mức nào (đếm tần suất trong một kho văn bản lớn).
• Mô hình lỗi P(w|c): khả năng người dùng định gõ c nhưng lại gõ thành w – các từ có khoảng cách chỉnh sửa 1 được ưu tiên hơn khoảng cách 2.

Theo Norvig, chương trình đạt độ chính xác khoảng 75% trên tập phát triển. Bàn phím điện thoại còn kết hợp thêm vị trí các phím (gõ nhầm "s" thành "a" vì hai phím cạnh nhau) và ngữ cảnh câu.

Gợi ý từ khi đang gõ: cây Trie

Để gợi ý "thuật toán" ngay khi bạn mới gõ "thuậ", người ta dùng cây tiền tố (Trie) – mỗi cạnh là một ký tự, mỗi đường đi từ gốc là một tiền tố. Thời gian tìm kiếm chỉ phụ thuộc vào độ dài từ, không phụ thuộc số lượng từ trong từ điển. Theo Wikipedia, ý tưởng này được mô tả từ năm 1959 và được dùng phổ biến trong gõ tiên đoán và tự động hoàn thành.

2. git diff: dòng nào đã thay đổi?

Khi so sánh hai phiên bản code, ta muốn tìm dãy con chung dài nhất (LCS) của hai danh sách dòng: những dòng thuộc LCS là không đổi, phần còn lại là dòng bị xóa (−) hoặc thêm mới (+).

• Năm 1976, James Hunt và Douglas McIlroy ở Bell Labs mô tả chương trình diff của Unix, giải bài toán "dãy con chung dài nhất".
• Năm 1986, Eugene Myers công bố thuật toán O(ND) – với N là tổng độ dài và D là số khác biệt. Khi hai file gần giống nhau (D nhỏ), thuật toán chạy rất nhanh. Theo tài liệu chính thức của Git, Myers hiện là thuật toán diff mặc định của Git (ngoài ra còn các lựa chọn minimal, patience, histogram).

Gợi ý: bảng QHĐ của LCS gần như giống hệt bảng Levenshtein ở trên – chỉ khác công thức chuyển trạng thái. Đây là bài tập rất tốt để luyện QHĐ trên hai chuỗi.

3. Giải mã gen: so khớp chuỗi DNA

DNA là một chuỗi rất dài trên bảng chữ cái 4 ký tự A, C, G, T. So sánh gen giữa các loài giúp tìm ra chức năng của gen, nguồn gốc tiến hóa và nguyên nhân bệnh tật:

Năm	Thuật toán	Ý tưởng
1970	Needleman–Wunsch	Căn chỉnh toàn cục: QHĐ trên bảng 2 chiều có tính "phạt khoảng trống" – thực chất là một biến thể của khoảng cách chỉnh sửa. Bài báo gốc so sánh myoglobin của cá voi với hemoglobin của người.
1981	Smith–Waterman	Căn chỉnh cục bộ: tìm cặp đoạn giống nhau nhất trong hai chuỗi dài, bằng cách cho giá trị QHĐ không xuống dưới 0.
1990	BLAST	Heuristic: tìm các "từ" ngắn khớp nhau rồi mở rộng ra hai phía; theo bài báo gốc, nhanh hơn các công cụ cùng thời "một bậc độ lớn" với độ nhạy tương đương.

Lý do cần BLAST: QHĐ O(n × m) là quá chậm khi so một đoạn gen với cả cơ sở dữ liệu hàng tỷ ký tự. Đây là bài học quen thuộc: khi thuật toán chính xác quá chậm, ta đổi một chút độ chính xác lấy tốc độ.

4. Bạn học được gì từ đây?

• QHĐ trên hai chuỗi (edit distance, LCS) là một trong những dạng QHĐ quan trọng nhất – xuất hiện trong bàn phím điện thoại, Git và cả sinh học.
• Trie là cấu trúc dữ liệu thực tế cho bài toán tiền tố.
• Khi dữ liệu quá lớn, thuật toán thực tế thường là QHĐ + heuristic (như BLAST, Myers).

Bài tập luyện tập

• CSES – Edit Distance
• AtCoder DP Contest F – LCS (dãy con chung dài nhất, có truy vết)

Thử thách: hãy tự tính khoảng cách chỉnh sửa giữa "kitten" và "sitting" bằng tay, rồi chạy code để kiểm tra. Đáp án bao nhiêu? Chia sẻ trong phần bình luận nhé!

📖 ĐỌC TIẾP: THUẬT TOÁN TRONG ĐỜI SỐNG

Bài 7: Shipper đi đường nào để giao hàng nhanh nhất? Bài toán người du lịch (TSP) trong đời sống

Đọc tiếp: giao hàng & bài toán TSP →

← Bài trước: ngân hàng & RSAXem tất cả 27 bài →

Nguồn tham khảo

• NIST – Levenshtein distance
• Math-Net.Ru – Levenshtein (1965), bài báo gốc
• CACM – Damerau (1964), A technique for computer detection and correction of spelling errors
• Peter Norvig – How to Write a Spelling Corrector
• Wikipedia – Trie
• Hunt & McIlroy (1976) – An Algorithm for Differential File Comparison
• Myers (1986) – An O(ND) Difference Algorithm and Its Variations
• Git – tài liệu tùy chọn --diff-algorithm
• Needleman & Wunsch (1970)
• Smith & Waterman (1981)
• Altschul et al. (1990) – Basic Local Alignment Search Tool