Khoảng cách chỉnh sửa (khoảng cách Levenshtein)
Bạn gõ recieve và điện thoại gợi ý receive. Nó biết bạn đã gần đúng vì hai từ chỉ cách nhau vài phép sửa. Đo độ gần đó, tức khoảng cách chỉnh sửa, là một bài toán kinh điển của quy hoạch động.
Bài toán
Một phép sửa thay đổi một từ đúng một chữ cái: chèn một chữ cái, xóa một chữ cái, hoặc thay một chữ cái bằng chữ cái khác. Khoảng cách chỉnh sửa giữa hai từ là số phép sửa ít nhất để biến từ này thành từ kia. Từ cat và cut cách nhau 1, cat và cast cách nhau 1, còn cat và act cách nhau 2. Nó còn được gọi là khoảng cách Levenshtein, theo tên nhà toán học Liên Xô Vladimir Levenshtein, người đã nghiên cứu nó vào năm 1965.
Bảng
Gọi d[i][j] là khoảng cách chỉnh sửa giữa i chữ cái đầu của một từ và j chữ cái đầu của từ kia. Biến một từ thành rỗng cần một phép xóa cho mỗi chữ cái, nên d[i][0] = i; dựng một từ từ chỗ trống cần một phép chèn cho mỗi chữ cái, nên d[0][j] = j. Nếu chữ cái thứ i bằng chữ cái thứ j thì d[i][j] = d[i − 1][j − 1]. Nếu không, d[i][j] = 1 + giá trị nhỏ nhất trong d[i − 1][j − 1] (thay thế), d[i − 1][j] (xóa) và d[i][j − 1] (chèn).
Một ví dụ
Với kitten và sitting, bảng có 7 hàng và 8 cột. Ô dưới cùng bên phải là 3, và đọc ngược từ đó ta được: thay k bằng s, giữ i, t và t, thay e bằng i, giữ n, và chèn g. Kitten, sitten, sittin, sitting: ba phép sửa, và bảng chứng minh rằng không có danh sách nào ngắn hơn.
Đọc ngược các phép sửa
Bắt đầu ở ô dưới cùng bên phải và hỏi giá trị của nó đến từ ô lân cận nào. Nếu hai chữ cái khớp và ô bằng ô lân cận phía trên bên trái, chữ cái được giữ: bước chéo. Nếu ô lớn hơn ô phía trên bên trái một đơn vị, đó là thay thế; lớn hơn ô phía trên một đơn vị là xóa; lớn hơn ô bên trái một đơn vị là chèn. Có thể có vài đường bằng nhau, và mỗi đường đều cho một danh sách phép sửa ngắn nhất.
Lịch sử và ứng dụng
Levenshtein đưa ra khoảng cách này vào năm 1965 khi nghiên cứu các mã sửa lỗi. Phương pháp dùng bảng được nhiều người công bố, nổi tiếng nhất là Robert Wagner và Michael Fischer vào năm 1974, nên nó thường được gọi là thuật toán Wagner–Fischer. Ngày nay, khoảng cách chỉnh sửa được dùng để xếp hạng gợi ý chính tả, khớp các tên bị gõ sai trong cơ sở dữ liệu, so sánh trình tự DNA và protein, và chấm điểm nhận dạng giọng nói.
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 ở tiêu đề hàng và cột; chữ cái giống nhau thì sao chép ô xanh lam phía trên bên trái, chữ cái khác nhau thì đọc cả ba ô lân cận màu xanh lam và cộng một vào giá trị nhỏ nhất. Cuối cùng, đường màu cam chạy ngược từ góc bảng, và các phép sửa hiện ra dưới bảng.
Câu hỏi thường gặp
Khoảng cách chỉnh sửa có phải là một metric không?
Có. Nó không bao giờ âm, chỉ bằng 0 khi hai từ giống nhau, như nhau theo cả hai chiều, và đi vòng qua một từ thứ ba không bao giờ làm nó ngắn hơn: d(a, c) ≤ d(a, b) + d(b, c). Nhờ vậy nó hữu ích khi tìm các kết quả gần khớp.
Khoảng cách Damerau–Levenshtein là gì?
Đó là khoảng cách chỉnh sửa có thêm một phép sửa: đổi chỗ hai chữ cái liền kề. Năm 1964, Frederick Damerau nhận thấy chèn, xóa, thay thế và đổi chỗ cộng lại chiếm hơn 80% lỗi chính tả. Khi cho phép đổi chỗ, recieve và receive cách nhau 1 thay vì 2.
Có thể tính khoảng cách chỉnh sửa nhanh hơn O(m·n) không?
Không nhanh hơn được bao nhiêu. Năm 2015, Arturs Backurs và Piotr Indyk chứng minh rằng một phương pháp mất thời gian O(n^(2 − ε)) với một ε > 0 nào đó sẽ phá vỡ giả thuyết thời gian mũ mạnh, điều mà hầu hết các nhà nghiên cứu tin là đúng. Tuy vậy, với các từ gần giống nhau, chỉ cần một dải hẹp quanh đường chéo của bảng.
Khoảng cách chỉnh sửa được dùng thế nào khi so sánh DNA?
Các nhà sinh học dùng cùng một bảng nhưng với điểm số thay vì số đếm: các vị trí khớp được cộng điểm, còn thay thế và khoảng trống bị trừ điểm tùy theo chữ cái. Đó là thuật toán Needleman–Wunsch năm 1970 cho toàn bộ trình tự, và thuật toán Smith–Waterman năm 1981 cho những đoạn khớp nhất.
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ử khoảng cách chỉnh sửa