3.7 Fuzzy search (1): edit distance tính bằng tay

Người dùng gõ sai. Không phải ngoại lệ — là mặc định: gõ trên điện thoại, gõ thiếu dấu, gõ teencode, gõ tên riêng theo tai. Hệ thống chỉ khớp chuỗi chính xác sẽ trả về rỗng, và rỗng là loại lỗi tệ nhất vì người dùng không biết mình đã gõ sai hay hệ thống không có dữ liệu.

Fuzzy search trả lời câu hỏi: hai chuỗi này khác nhau bao nhiêu?

Levenshtein distance

Số phép sửa ít nhất để biến chuỗi này thành chuỗi kia, với ba phép giá 1:

Phép	Ví dụ
Chèn (insert)	`khu` → `khau`
Xoá (delete)	`khaau` → `khau`
Thay (substitute)	`khao` → `khau`

Tính bằng quy hoạch động: D[i][j] = khoảng cách giữa i ký tự đầu của chuỗi A và j ký tự đầu của chuỗi B.

D[i][0] = i                     (xoá hết i ký tự)
D[0][j] = j                     (chèn j ký tự)
D[i][j] = D[i-1][j-1]                                   nếu A[i] == B[j]
        = 1 + min( D[i-1][j],      ← xoá
                   D[i][j-1],      ← chèn
                   D[i-1][j-1] )   ← thay

Bảng đầy đủ: `khau` → `khoa`

		k	h	o	a
	0	1	2	3	4
k	1	0	1	2	3
h	2	1	0	1	2
a	3	2	1	1	1
u	4	3	2	2	2

Đáp số ở góc dưới phải: khoảng cách = 2. Đường đi: khau → khou (a→o) → khoa (u→a). Hai phép thay.

Tự tay điền lại bảng này một lần. Nó là nền của mọi thứ trong ba mục tiếp theo.

Damerau: thêm phép đổi chỗ

Lỗi gõ thật hay là đổi chỗ hai ký tự liền nhau (mật → mtậ). Levenshtein thuần tính lỗi đó là 2 (một xoá + một chèn), trong khi cảm nhận của người dùng là “một lỗi”. Damerau–Levenshtein thêm phép transposition giá 1:

D[i][j] = min( …, D[i-2][j-2] + 1 )   nếu A[i]==B[j-1] và A[i-1]==B[j]

Đa số thư viện thực tế dùng biến thể này. Elasticsearch fuzziness mặc định có tính transposition (transpositions: true).

Vấn đề khiến mục 3.8 và 3.9 phải tồn tại

Tính khoảng cách giữa hai chuỗi là O(n·m) — rẻ. Nhưng truy vấn thật là:

tìm mọi term trong dictionary có khoảng cách ≤ 2 với mat khau

Nếu làm ngây thơ: chạy DP với từng term trong dictionary. Với 500.000 term × ~64 ô mỗi bảng = 32 triệu phép tính cho một truy vấn. Ở p95 dưới 100 ms thì việc này không có chỗ đứng.

Nên mọi hệ fuzzy thực tế đều tách làm hai bước:

Bước	Việc	Yêu cầu
1. Sinh ứng viên	thu hẹp từ 500.000 term xuống ~vài chục	phải nhanh, được phép lọt ứng viên sai
2. Kiểm chứng	chạy DP chính xác trên các ứng viên	phải đúng, không được bỏ sót

Bước 2 luôn là bảng ở trên. Ba cách làm bước 1:

n-gram / trigram — 3.8
BK-tree, SymSpell, Levenshtein automaton — 3.9
Chuẩn hoá trước (bỏ dấu, sửa teencode) — 3.10, và với tiếng Việt đây thường là cách hiệu quả nhất

Một cảnh báo phải đọc trước khi bật fuzzy

E2003 và E2004 có khoảng cách 1. sk_live_a1 và sk_live_a2 cũng vậy. Fuzzy search trên mã định danh không phải tính năng — nó là lỗi trả về sai đáp án với vẻ ngoài rất tự tin.

Quy tắc: fuzzy chỉ áp cho field ngôn ngữ tự nhiên. Field định danh (mã lỗi, SKU, số phiên bản, endpoint) phải khớp chính xác, luôn luôn.

Phần 3 — Nền tảng kỹ thuật