3.8 Fuzzy search (2): n-gram và độ tương đồng tập hợp

Ý tưởng: quên chuỗi đi, coi mỗi từ là một tập hợp các đoạn ngắn. Hai từ giống nhau thì hai tập giao nhau nhiều. Đo giao tập là phép tra index — nhanh hơn DP hàng bậc độ lớn.

Cắt trigram (có đệm)

Thêm đệm ở hai đầu để ký tự đầu/cuối cũng được ghi nhận (cách pg_trgm làm):

"khau"  ->  { "  k", " kh", "kha", "hau", "au " }     5 trigram
"khao"  ->  { "  k", " kh", "kha", "hao", "ao " }     5 trigram

Jaccard / similarity

$$\mathrm{similarity}(A,B) = \frac{\lvert A \cap B\rvert}{\lvert A \cup B\rvert}$$

Ví dụ 1 — khau vs khao (một lỗi thay ký tự cuối):

Giao	" k", " kh", "kha" → 3
Hợp	5 + 5 − 3 → 7
similarity	3/7 = 0,429

Ngưỡng mặc định của pg_trgm là 0,3 → khớp. ✅

Ví dụ 2 — khau vs khoa (hai lỗi, đã tính ở 3.7 là distance 2):

Giao	" k", " kh" → 2
Hợp	5 + 5 − 2 → 8
similarity	2/8 = 0,25

Dưới ngưỡng 0,3 → không khớp. ❌

Hai ví dụ này cho thấy điều quan trọng nhất của mục này:

n-gram similarity và edit distance là hai thước đo khác nhau, không thay thế nhau. khau/khoa có distance 2 (đủ gần theo Levenshtein) nhưng similarity 0,25 (quá xa theo trigram). Chọn thước đo là chọn hành vi sản phẩm, không phải chọn cách hiện thực.

Quy luật chung: n-gram phạt nặng lỗi ở đầu chuỗi (phá nhiều trigram cùng lúc) và phạt nhẹ lỗi ở giữa chuỗi dài. Edit distance thì không quan tâm lỗi ở đâu — và ngược lại, nó phạt chuỗi ngắn rất nặng (ba → be là distance 1, tức 50% chuỗi bị đổi).

Vì sao nó nhanh: n-gram là một inverted index

Đảo chiều đúng thủ thuật của 3.2, nhưng ở mức ký tự:

"  k"  ->  { khau, khao, khoa, khong, ... }
" kh"  ->  { khau, khao, khoa, khong, ... }
"kha"  ->  { khau, khao, khai, ... }

Truy vấn khau → tra 5 trigram → hợp các danh sách → đếm số lần mỗi term xuất hiện → đó chính là |A ∩ B|, có được mà không hề so sánh chuỗi. Chỉ những term qua ngưỡng mới đi tiếp sang bước kiểm chứng.

Đây cũng chính là index đã dùng cho substring ở 3.6 — một cấu trúc, hai chức năng.

Đọc thêm

• [EN] IR Book §3.2.2 — k-gram indexes for wildcard queries — k-gram index — nền của cách tiếp cận này
• [VI] Simple Fuzzy Search — Viblo — fuzzy search bằng n-gram, có code
• [VI] Example Fuzzy Full Text Search — Viblo — ví dụ fuzzy full text search

Trong công cụ thật

Postgres — cách rẻ nhất để có fuzzy tử tế:

CREATE EXTENSION pg_trgm;
CREATE INDEX ON docs USING gin (title gin_trgm_ops);

SELECT title, similarity(title, 'mat khau')  AS sim
FROM   docs
WHERE  title % 'mat khau'          -- % dùng ngưỡng pg_trgm.similarity_threshold
ORDER  BY sim DESC LIMIT 10;

Cùng index này còn tăng tốc LIKE '%mat kha%' — hai nhu cầu, một index.

Elasticsearch — có hai đường, và chúng khác nhau:

Cách	Cơ chế	Ghi chú
fuzziness: AUTO	Levenshtein automaton (3.9)	Giới hạn cứng ≤ 2 phép sửa. AUTO = 0 sửa với từ 1–2 ký tự, 1 với 3–5, 2 với >5
ngram / edge_ngram analyzer	index n-gram như term thường	Không giới hạn khoảng cách, nhưng index phình rất nhanh — đặt min_gram/max_gram cẩn thận

Đọc thêm

• [EN] PostgreSQL — pg_trgm (trigram similarity) — trigram similarity sẵn dùng, kèm index GIN/GiST

Ba cạm bẫy đo được

Bẫy	Chuyện gì xảy ra	Chữa
Ngưỡng quá thấp	mọi truy vấn khớp mọi thứ, precision sụp	Đo trên golden set, đừng đoán. 0,3 là điểm bắt đầu, không phải đáp án
n-gram trên field dài	tập trigram của một đoạn văn gần như phủ hết bảng chữ	Chỉ dùng n-gram cho field ngắn: tên, tiêu đề, từ khoá
Fuzzy trên cả truy vấn nhiều từ	"mật khẩu bị lỗi" với fuzzy từng từ → nổ tổ hợp ứng viên	Fuzzy chỉ term không tìm ra kết quả nào, giữ term khác khớp chính xác