Bài toán Khoảng cách Chỉnh sửa¶

Khoảng cách chỉnh sửa (edit distance), còn được gọi là khoảng cách Levenshtein (Levenshtein distance), đề cập đến số lượng thao tác chỉnh sửa tối thiểu cần thiết để biến đổi một chuỗi này thành một chuỗi khác, thường được sử dụng trong truy xuất thông tin (information retrieval) và xử lý ngôn ngữ tự nhiên (natural language processing) để đo lường mức độ tương đồng giữa hai chuỗi ký tự.

Question

Cho hai chuỗi ký tự \(s\) và \(t\), hãy trả về số lượng thao tác chỉnh sửa tối thiểu cần thiết để biến đổi \(s\) thành \(t\).

Bạn có thể thực hiện ba loại thao tác chỉnh sửa trên chuỗi: chèn một ký tự, xóa một ký tự hoặc thay thế một ký tự bằng bất kỳ ký tự nào khác.

Như hình dưới đây, việc biến đổi kitten thành sitting cần 3 thao tác chỉnh sửa, bao gồm 2 lượt thay thế và 1 lượt chèn; biến đổi hello thành algo cần 3 bước, bao gồm 2 lượt thay thế và 1 lượt xóa.

Bài toán khoảng cách chỉnh sửa có thể được giải thích một cách tự nhiên bằng mô hình cây quyết định. Các chuỗi ký tự tương ứng với các nút trên cây, và mỗi thao tác chỉnh sửa tương ứng với một cạnh trên cây.

Như hình dưới đây, nếu không giới hạn các thao tác, mỗi nút có thể phân nhánh thành nhiều cạnh, mỗi cạnh tương ứng với một thao tác, điều này có nghĩa là có nhiều đường đi khả thi để biến đổi hello thành algo.

Từ góc độ của cây quyết định, mục tiêu của bài toán này là tìm đường đi ngắn nhất giữa nút hello và nút algo.

Hướng tiếp cận Quy hoạch động¶

Bước 1: Suy nghĩ về quyết định trong từng vòng, định nghĩa trạng thái, và từ đó có được bảng \(dp\)

Mỗi vòng quyết định liên quan đến việc thực hiện một thao tác chỉnh sửa trên chuỗi \(s\).

Chúng ta muốn kích thước của bài toán giảm dần trong quá trình chỉnh sửa để có thể xây dựng các bài toán con. Gọi độ dài của hai chuỗi \(s\) và \(t\) lần lượt là \(n\) và \(m\). Trước tiên chúng ta xem xét các ký tự đuôi của hai chuỗi là \(s[n-1]\) và \(t[m-1]\).

Nếu \(s[n-1]\) và \(t[m-1]\) giống nhau, chúng ta có thể bỏ qua chúng và xem xét trực tiếp \(s[n-2]\) và \(t[m-2]\).
Nếu \(s[n-1]\) và \(t[m-1]\) khác nhau, chúng ta cần thực hiện một thao tác chỉnh sửa trên \(s\) (chèn, xóa hoặc thay thế) để làm cho ký tự đuôi của hai chuỗi giống nhau, từ đó cho phép chúng ta bỏ qua chúng và xem xét bài toán có kích thước nhỏ hơn.

Nói cách khác, mỗi vòng quyết định (thao tác chỉnh sửa) chúng ta thực hiện trên chuỗi \(s\) sẽ thay đổi các ký tự còn lại cần khớp trong \(s\) và \(t\). Do đó, trạng thái là các ký tự thứ \(i\) và thứ \(j\) hiện đang được xem xét trong \(s\) và \(t\), ký hiệu là \([i, j]\).

Trạng thái \([i, j]\) tương ứng với bài toán con: số thao tác chỉnh sửa tối thiểu cần thiết để biến đổi \(i\) ký tự đầu tiên của \(s\) thành \(j\) ký tự đầu tiên của \(t\), ký hiệu là \(dp[i, j]\).

Từ đây, chúng ta có được bảng \(dp\) hai chiều kích thước \((i+1) \times (j+1)\).

Bước 2: Xác định cấu trúc con tối ưu, từ đó rút ra phương trình chuyển trạng thái

Xem xét bài toán con \(dp[i, j]\), trong đó các ký tự đuôi của hai chuỗi tương ứng là \(s[i-1]\) và \(t[j-1]\), có thể được chia thành ba trường hợp được hiển thị trong hình bên dưới dựa trên các thao tác chỉnh sửa khác nhau:

Chèn \(t[j-1]\) vào sau \(s[i-1]\), khi đó bài toán con còn lại là \(dp[i, j-1]\).
Xóa \(s[i-1]\), khi đó bài toán con còn lại là \(dp[i-1, j]\).
Thay thế \(s[i-1]\) bằng \(t[j-1]\), khi đó bài toán con còn lại là \(dp[i-1, j-1]\).

Dựa trên phân tích ở trên, chúng ta có được cấu trúc con tối ưu: số lượng chỉnh sửa tối thiểu cho \(dp[i, j]\) bằng giá trị nhỏ nhất của \(dp[i, j-1]\), \(dp[i-1, j]\) và \(dp[i-1, j-1]\), cộng với chi phí chỉnh sửa hiện tại là \(1\). Phương trình chuyển trạng thái tương ứng là:

\[ dp[i, j] = \min(dp[i, j-1], dp[i-1, j], dp[i-1, j-1]) + 1 \]

Vui lòng lưu ý rằng khi \(s[i-1]\) và \(t[j-1]\) giống nhau, không cần thao tác chỉnh sửa cho ký tự hiện tại, trong trường hợp này phương trình chuyển trạng thái là:

\[ dp[i, j] = dp[i-1, j-1] \]

Bước 3: Xác định điều kiện biên và thứ tự chuyển trạng thái

Khi cả hai chuỗi đều rỗng, số bước chỉnh sửa bằng \(0\), tức là \(dp[0, 0] = 0\). Khi \(s\) rỗng nhưng \(t\) không rỗng, số bước chỉnh sửa tối thiểu bằng độ dài của \(t\), tức là dòng đầu tiên \(dp[0, j] = j\). Khi \(s\) không rỗng nhưng \(t\) rỗng, số bước chỉnh sửa tối thiểu bằng độ dài của \(s\), tức là cột đầu tiên \(dp[i, 0] = i\).

Quan sát phương trình chuyển trạng thái, lời giải \(dp[i, j]\) phụ thuộc vào các lời giải bên trái, phía trên và phía trên bên trái, do đó toàn bộ bảng \(dp\) có thể được duyệt tuần tự qua hai vòng lặp lồng nhau.

Triển khai mã nguồn¶

[file]{edit_distance}-[class]{}-[func]{edit_distance_dp}

Như hình dưới đây, quy trình chuyển trạng thái cho bài toán khoảng cách chỉnh sửa rất giống với bài toán balo; cả hai đều có thể được xem như quá trình điền vào một lưới hai chiều.

Tối ưu hóa không gian¶

Vì \(dp[i, j]\) phụ thuộc vào trạng thái phía trên \(dp[i-1, j]\), bên trái \(dp[i, j-1]\) và phía trên bên trái \(dp[i-1, j-1]\), duyệt xuôi sẽ làm mất trạng thái phía trên bên trái \(dp[i-1, j-1]\), trong khi duyệt ngược không thể xây dựng trước \(dp[i, j-1]\), do đó cả hai thứ tự duyệt đều không phù hợp.

Vì lý do này, chúng ta có thể sử dụng một biến leftup để tạm thời lưu trữ lời giải phía trên bên trái \(dp[i-1, j-1]\), như vậy chúng ta chỉ cần xem xét các lời giải bên trái và phía trên. Tình huống này tương tự như trong bài toán balo vô hạn, do đó chúng ta có thể sử dụng duyệt xuôi. Mã nguồn như sau:

[file]{edit_distance}-[class]{}-[func]{edit_distance_dp_comp}