3.9 Fuzzy search (3): làm cho nó nhanh

3.7 để lại một bài toán: tìm mọi term có khoảng cách ≤ k, không được quét cả dictionary. Có bốn cách, và chúng khác nhau ở chỗ chi phí nằm đâu — lúc index, lúc truy vấn, hay ở bộ nhớ.

1. BK-tree — dùng bất đẳng thức tam giác để cắt nhánh

Edit distance là một metric, nên nó thoả bất đẳng thức tam giác. Từ đó:

$$\bigl\lvert\, d(q, \text{node}) - d(\text{node}, \text{child}) \,\bigr\rvert \;\le\; d(q, \text{child})$$

Nghĩa là nếu đã biết d(q, node) = 3 và tìm với k = 1, thì mọi nhánh con có nhãn cạnh ngoài khoảng [2, 4] đều không thể chứa kết quả. Cắt luôn, không cần tính gì thêm.

Cây được dựng bằng cách: mỗi nút giữ một term, mỗi cạnh được gán nhãn bằng khoảng cách từ nút cha tới con.

        mat
       /   \
     1/     \2
    map     mua
      \
      2\
      bat

Truy vấn map, k = 1:

Nút thăm	d(q, nút)	≤ k?	Nhánh được đi tiếp
mat	1	✅ nhận	cạnh trong [0, 2] → cả map và mua
map	0	✅ nhận	cạnh trong [−1, 1] → bỏ nhánh cạnh 2 (bat)
mua	2	❌	cạnh trong [1, 3] → không có con

bat không bao giờ được tính khoảng cách. Trên dictionary thật, BK-tree thăm cỡ vài phần trăm số nút.

Điểm mạnh: chỉ cần bộ nhớ ~1× dictionary, k không giới hạn. Điểm yếu: cây sâu, nhiều lần nhảy con trỏ ngẫu nhiên — không thân thiện với cache, khó phân tán.

2. SymSpell — chỉ sinh phép xoá

Nhận xét: mọi lỗi (chèn/xoá/thay/đổi chỗ) đều có thể quy về so khớp sau khi xoá ở cả hai phía. Nên chỉ cần index các biến thể xoá — không cần sinh biến thể thay và chèn (vốn nhân với cỡ bảng chữ cái, tiếng Việt là ~90 ký tự có dấu).

Lúc index	Với mỗi term, sinh mọi biến thể xoá đến k ký tự → hash map biến thể → term gốc
Lúc truy vấn	Sinh biến thể xoá của truy vấn, tra hash. Trùng nhau → ứng viên

Chi phí bộ nhớ, tính bằng tay: term dài 10 ký tự, k = 2 → C(10,1) + C(10,2) = 10 + 45 = 55 biến thể cho một term. Với 500.000 term là ~27 triệu khoá. Đây là đánh đổi rất thẳng thắn: đổi RAM lấy latency, và latency đổi lại gần như O(1).

Đọc thêm

• [EN] SymSpell — spelling correction bằng delete-only index — delete-only index — đổi bộ nhớ lấy tốc độ
• [VI] Tự động sửa lỗi chính tả với SymSpell — Viblo — SymSpell bằng tiếng Việt, có ví dụ

3. Levenshtein automaton — cách Lucene/Elasticsearch làm

Với truy vấn q và k cho trước, dựng một automaton hữu hạn chấp nhận đúng tập chuỗi có khoảng cách ≤ k với q. Rồi giao automaton đó với FST của term dictionary (3.3).

Kết quả: đi một lượt song song hai cấu trúc, chỉ đi theo những nhánh tiền tố còn khả năng đúng. Không sinh ứng viên, không tính DP, không quét dictionary.

Đây là lý do fuzziness của Elasticsearch bị chặn cứng ở ≤ 2: kích thước automaton tăng theo k rất nhanh, và ở k = 3 phần thắng không còn bù được chi phí.

Đọc thêm

• [EN] Lucene’s FuzzyQuery nhanh gấp 100 lần (Levenshtein automaton) — Mike McCandless — Levenshtein automaton trong thực tế: nhanh gấp 100 lần
• [EN] Using finite state transducers in Lucene — Mike McCandless — FST làm nền cho automaton intersection

4. Chuẩn hoá trước — cách rẻ nhất, hay bị bỏ qua

Nếu lỗi có cấu trúc (mất dấu, teencode, viết tắt) thì nó không phải “lỗi ngẫu nhiên” và không nên chữa bằng fuzzy. Chữa bằng một hàm chuẩn hoá áp cho cả index và query — chi phí truy vấn bằng không. Với tiếng Việt đây thường là món đúng: 3.10.

Bảng chọn

Cách	Chi phí index	Chi phí truy vấn	RAM	k tối đa	Chọn khi
Quét toàn bộ + DP	0	rất cao	0	∞	dictionary < ~10k term, hoặc chạy offline
Trigram (3.8)	trung bình	thấp	trung bình	∞ (theo ngưỡng)	đã có Postgres — pg_trgm là lựa chọn mặc định
BK-tree	trung bình	trung bình	thấp	∞	cần k lớn, một máy, dictionary vừa
SymSpell	cao	rất thấp	cao	2–3	autocomplete/typeahead, latency là ràng buộc cứng
Levenshtein automaton	thấp	thấp	thấp	2	đã dùng Elasticsearch/Lucene — có sẵn, dùng luôn
Chuẩn hoá trước	~0	0	0	—	lỗi có cấu trúc (mất dấu, teencode) — thử cách này trước

Nên áp dụng vào AI Agent

Thứ tự thử, từ rẻ đến đắt: (1) chuẩn hoá + bỏ dấu → (2) fuzzy chỉ khi truy vấn trả về 0 kết quả (fallback, không phải mặc định) → (3) trigram/automaton trên field ngắn → (4) embedding, vốn xử lý sai chính tả nhẹ khá tốt mà không cần cấu hình gì (Tầng 1).

Bật fuzzy làm mặc định cho mọi truy vấn là cách nhanh nhất để vừa mất precision vừa mất p95.