Tổng quan
Khoảng Cách Chỉnh Sửa, còn gọi là khoảng cách Levenshtein, đo độ khác nhau giữa hai chuỗi bằng số phép chèn, xóa và thay thế một ký tự tối thiểu cần để biến chuỗi này thành chuỗi kia. Đây là một trong những thuật toán quy hoạch động được dùng rộng rãi nhất trong xử lý văn bản.
Giống LCS, nó điền một bảng DP hai chiều mà dp[i][j] là khoảng cách chỉnh sửa giữa i ký tự đầu chuỗi này và j ký tự đầu chuỗi kia. Mỗi ô chọn phương án rẻ nhất trong ba bài toán con lân cận, nên toàn bộ khoảng cách được tính trong O(m·n).
Khoảng cách chỉnh sửa hoạt động thế nào?
- Dựng bảng DP (m+1)×(n+1); khởi tạo hàng 0 và cột 0 bằng 0,1,2,… — chi phí tạo một chuỗi từ đầu.
- Với mỗi cặp (i, j), so sánh ký tự i của chuỗi thứ nhất với ký tự j của chuỗi thứ hai.
- Nếu ký tự khớp, giữ nguyên giá trị đường chéo: dp[i][j] = dp[i-1][j-1] (không cần chỉnh sửa).
- Ngược lại lấy 1 + giá trị nhỏ nhất trong ba ô lân cận: xóa (dp[i-1][j]), chèn (dp[i][j-1]) hoặc thay thế (dp[i-1][j-1]).
- Ô dưới cùng bên phải là khoảng cách chỉnh sửa cuối cùng; bước truy vết cho ra chuỗi thao tác chính xác.
Khi nào nên dùng?
- Kiểm tra chính tả và tự động sửa, xếp hạng các từ ứng viên theo số chỉnh sửa cần thiết ít nhất.
- Tìm kiếm mờ và đối sánh bản ghi, khớp các tên hoặc mục gần trùng nhau.
- Căn chỉnh chuỗi trong tin sinh học, khi phép chèn và xóa mô hình hóa đột biến.
- Các độ đo trong xử lý ngôn ngữ tự nhiên như tỷ lệ lỗi từ (WER) trong nhận dạng giọng nói.
Phân tích độ phức tạp
Tính mọi ô của bảng (m+1)×(n+1) tốn O(m·n) thời gian và O(m·n) bộ nhớ. Vì mỗi ô chỉ phụ thuộc hàng hiện tại và hàng trước, có thể giảm bộ nhớ xuống O(min(m,n)) bằng cách giữ hai hàng — đủ để lấy khoảng cách, dù việc khôi phục chuỗi thao tác khi đó cần thêm công sức.
Câu hỏi thường gặp
Ba phép thao tác được phép là gì?
Chèn, xóa và thay thế, mỗi phép tốn 1 trong khoảng cách Levenshtein chuẩn. Một số biến thể thêm hoán vị (đổi chỗ hai ký tự liền kề) làm phép thứ tư.
Khoảng cách chỉnh sửa liên hệ thế nào với chuỗi con chung dài nhất?
Cả hai đều điền bảng DP (m+1)×(n+1) trên hai chuỗi với cùng dạng công thức truy hồi. Khi chỉ cho phép chèn và xóa (không thay thế), khoảng cách chỉnh sửa bằng m + n − 2·LCS.
Có thể dùng chi phí tùy chỉnh cho từng phép không?
Có. Khoảng cách chỉnh sửa có trọng số gán chi phí khác nhau cho chèn, xóa và thay thế (thậm chí theo từng cặp ký tự); cùng công thức truy hồi DP vẫn dùng được, chỉ thay chi phí cố định 1 bằng trọng số tương ứng.