solution

Một kỹ thuật phục hồi lỗi mạnh — sửa lỗi khoảng cách tối thiểu (minimum-distance error correction) — tìm dãy phép chèn (insert), xóa (delete), thay thế (substitute) token với số phép ít nhất để biến dãy token thực tế mà lexer đọc được thành dãy token mà văn phạm/parser mong đợi. Đây chính là khoảng cách chỉnh sửa Levenshtein trên dãy token (mỗi phép chi phí 1).

Cho dãy token thực tế $A = a_1 \ldots a_n$ và dãy token kỳ vọng $B = b_1 \ldots b_m$. Gọi $dp[i][j]$ là khoảng cách sửa lỗi tối thiểu giữa $a_1\ldots a_i$ và $b_1 \ldots b_j$:

$dp[i][0]=i,\quad dp[0][j]=j$ $dp[i][j] = \begin{cases} dp[i-1][j-1] & \text{nếu } a_i = b_j \\ 1+\min(dp[i-1][j-1],\ dp[i-1][j],\ dp[i][j-1]) & \text{nếu } a_i \ne b_j\end{cases}$

Vì có thể có nhiều cách phân rã tối ưu khác nhau (cùng tổng chi phí nhưng khác số lượng insert/delete/substitute), để kết quả xác định duy nhất, quy ước dựng lại đường đi từ $(n,m)$ về $(0,0)$: tại mỗi ô, áp dụng lựa chọn khả thi đầu tiên theo đúng thứ tự ưu tiên sau:

1. Nếu $a_i = b_j$ và $dp[i][j]=dp[i-1][j-1]$: giữ nguyên (không tính là phép sửa), lùi về $(i-1,j-1)$.
2. Ngược lại, nếu $dp[i][j] = dp[i-1][j-1]+1$: tính là thay thế (substitute), lùi về $(i-1,j-1)$.
3. Ngược lại, nếu $dp[i][j] = dp[i-1][j]+1$: tính là xóa (delete, khỏi $A$), lùi về $(i-1,j)$.
4. Ngược lại (khi đó bắt buộc $dp[i][j]=dp[i][j-1]+1$): tính là chèn (insert, vào $A$ để khớp $B$), lùi về $(i,j-1)$.

Ví dụ: $A=$ a b c, $B=$ a x c. $dp[3][3]=1$ (thay b thành x). Kết quả: khoảng cách $1$, insert$=0$, delete$=0$, substitute$=1$.