Phần 3 — Nền tảng kỹ thuật: bên trong một search engine

Mười tám mục về cơ chế. Phần 1 trả lời search là gì; Phần 4 trả lời làm sao cho nó thông minh. Phần này trả lời câu ở giữa, câu mà đa số tài liệu về RAG bỏ qua: một search engine thật sự hoạt động thế nào, và mỗi lựa chọn tốn gì.

Đọc khi nào. Ngay sau Phần 1 nếu bạn muốn hiểu tận gốc. Hoặc tra cứu từng mục khi gặp nhu cầu cụ thể — mỗi mục đứng độc lập được. Nếu chỉ đọc được hai mục: 3.1 và 3.10 — đó là hai chỗ quyết định nhiều nhất mà tốn ít nhất. Cần con số cụ thể để cấu hình hôm nay: 3.15.

Các mục có ví dụ tính bằng tay: 3.2, 3.4, 3.4b, 3.7, 3.8, 3.9, 3.13, 6.1, 6.2. Tự tay tính lại.

Đọc thêm

• [EN] Manning et al. — Introduction to Information Retrieval (toàn văn miễn phí) — Phần 3 bám theo ch.1–ch.7 của sách này
• [EN] Stanford CS276 — Information Retrieval and Web Search (slide, handout) — slide đi kèm, nhiều hình hơn sách
• [EN] Elasticsearch from the bottom up — Elastic — bản engineering: những khái niệm đó nằm đâu trong Lucene

Nhóm 1 — Cơ chế cốt lõi

#	Mục	Nội dung
3.1	Tiền xử lý văn bản	Unicode, tokenize, bỏ dấu, stopword — và vì sao âm tiết ≠ từ
3.2	Boolean retrieval	Giao/hợp/trừ postings, thuật toán hai con trỏ, skip pointer
3.3	Postings và lưu trữ	Dictionary vs postings, nén gap, FST, ước lượng dung lượng
3.4	TF-IDF và vector space	Tính cosine đầy đủ bằng tay, và vì sao BM25 thay nó
3.4b	BM25: từ mô hình xác suất đến công thức	Eliteness & 2-Poisson, idf âm, tám biến thể, BM25F và bẫy cộng điểm field

Nhóm 2 — Khớp không chính xác

#	Mục	Nội dung
3.5	Positional index và cụm từ	Khớp "mật khẩu", proximity, giá của index vị trí
3.6	Prefix và wildcard	Trie, permuterm, k-gram — ba nhu cầu, ba cấu trúc
3.7	Fuzzy search (1): edit distance	Bảng Levenshtein tính bằng tay, Damerau, và một cảnh báo
3.8	Fuzzy search (2): n-gram	Trigram, Jaccard, pg_trgm — và vì sao nó ≠ edit distance
3.9	Fuzzy search (3): làm cho nhanh	BK-tree, SymSpell, Levenshtein automaton + bảng chọn
3.10	Lỗi chính tả tiếng Việt	Bốn loại lỗi, bốn cách chữa. Mất dấu không chữa được bằng fuzzy
3.11	Sửa lỗi và gợi ý	Autocomplete, “có phải bạn muốn tìm”, noisy channel

Nhóm 3 — Vận hành

#	Mục	Nội dung
3.12	Dựng, cập nhật, xoá index	SPIMI, segment bất biến, tombstone, reindex qua alias
3.13	Top-k và tối ưu truy vấn	Heap, WAND, Block-Max — và giá thật của track_total_hits
3.14	Bảng chọn cấu trúc dữ liệu	Nhu cầu → cấu trúc → công cụ (Postgres / ES / SQLite)
3.15	BM25 tiếng Việt: tham số và chunk size	Grid k1×b đo thật, chunk size, và vì sao b là băng dán cho chunking kém
6.1	Quantization cho vector	Scalar / PQ / binary tính bằng tay, ADC, vì sao binary cần nhiều chiều, TurboQuant từ trong ra ngoài
6.2	ANN đồ thị: từ small world tới HNSW	Bốn họ ANN mổ xẻ (LSH, Annoy, IVF + k-means, đồ thị) + bảng so; Kleinberg & NSW, 4 thuật toán HNSW, heuristic cắt tỉa, bẫy xoá, Vamana

Sợi chỉ xuyên suốt Phần 3

Mỗi mục đều quay về cùng một kết luận, từ một góc khác:

Quyết định về dữ liệu và tiền xử lý đắt hơn quyết định về thuật toán. Sửa tokenizer: +20,8%. Đổi TF-IDF sang BM25: +1,2%. Cùng một corpus, cùng golden set.

Và một quy tắc lặp lại đủ nhiều lần để đáng nhắc ở đây:

Fuzzy là fallback, không phải mặc định. Chuẩn hoá trước (rẻ, xác định, không tốn latency) → fuzzy chỉ khi trả về rỗng → và tuyệt đối không fuzzy trên mã định danh.