solution

Một chiến lược phục hồi lỗi mức cụm từ (phrase-level recovery) phổ biến trong trình biên dịch là tự động thay thế 1 token bị nghi sai chính tả bằng từ khoá hợp lệ gần nhất.

Cho tập $m$ từ khoá hợp lệ, phân biệt (chỉ gồm chữ cái thường). Với mỗi token nghi vấn $t$ (chỉ gồm chữ cái thường), tìm từ khoá $k$ trong tập sao cho khoảng cách chỉnh sửa Levenshtein $d(t,k)$ (số phép chèn/xoá/thay thế 1 ký tự tối thiểu để biến $t$ thành $k$) là nhỏ nhất. Nếu có nhiều từ khoá cùng đạt khoảng cách nhỏ nhất, chọn từ khoá nhỏ nhất theo thứ tự từ điển (so sánh chuỗi thông thường).

Gọi $d^*$ là khoảng cách nhỏ nhất tìm được và $L = \lfloor |t|/2 \rfloor$ (nửa độ dài $t$, làm tròn xuống).

• Nếu $d^* \le L$: token được "sửa" thành từ khoá đã chọn — in ra từ khoá đó.
• Ngược lại (không đủ gần bất kỳ từ khoá nào một cách an toàn): giữ nguyên, in ra chính token $t$.

Ví dụ: từ khoá $\{$int, for, while, return$\}$; token whille (độ dài 6, $L=3$): khoảng cách đến while là 1 (thừa 1 ký tự l) $\le 3$ $\Rightarrow$ sửa thành while. Token xyzxyz (độ dài 6, $L=3$): khoảng cách nhỏ nhất đến mọi từ khoá đều $> 3$ $\Rightarrow$ giữ nguyên xyzxyz.