Bài tập 01 — Xây một hệ thống Inverted Index
PYTHON · 4–8 GIỜ · LÀM MỘT MÌNH · KHÔNG DÙNG THƯ VIỆN SEARCH
Tự xây một máy tìm kiếm hoàn chỉnh từ số không: bộ dữ liệu, index ngược, lưu trữ, và xếp hạng top-k. Mục tiêu không phải “chạy được” — mục tiêu là hiểu vì sao nó chạy được.
Bài tập này cố tình không cho code mẫu và không chỉ cách làm. Mọi quyết định thiết kế là của bạn; phần bị đánh giá là lý do bạn chọn như vậy, không phải việc bạn chọn giống ai.
Mục tiêu học
Phần tiêu đề “Mục tiêu học”Làm xong bài này, bạn phải tự trả lời được ba câu — bằng số đo trên dữ liệu của chính bạn:
- Vì sao index ngược nhanh hơn quét tuần tự — chứng minh bằng số, không bằng lý thuyết.
- Tokenizer quyết định cái gì tìm được và cái gì vĩnh viễn không tìm ra.
- “Có chứa từ khoá” và “liên quan” là hai chuyện khác nhau — khác ở đâu.
Phạm vi
Phần tiêu đề “Phạm vi”| Trong phạm vi | Ngoài phạm vi — đừng làm |
|---|---|
| Corpus tự tạo · tokenizer · inverted index · lưu trữ bền · xếp hạng · truy vấn top-k | Embedding / vector search · ANN · reranker · LLM · web UI · Docker · deploy |
Đề bài — yêu cầu bắt buộc
Phần tiêu đề “Đề bài — yêu cầu bắt buộc”R1 · Bộ corpus: 10–100 tài liệu
Phần tiêu đề “R1 · Bộ corpus: 10–100 tài liệu”- Tiếng Việt có dấu, nội dung tự chọn (FAQ sản phẩm, ghi chú, tin tức…).
- Mỗi tài liệu tối thiểu có
id,title,text. - Bắt buộc: ít nhất 5 tài liệu chứa định danh — mã lỗi, số phiên bản, tên endpoint, số hiệu, giá tiền, hoặc ngày tháng. Lý do sẽ tự lộ ra khi bạn làm R2.
- Lưu ra file (JSON / JSONL / CSV). Không hard-code corpus trong code.
R2 · Tokenizer
Phần tiêu đề “R2 · Tokenizer”- Một hàm: chuỗi văn bản → danh sách token.
- Bạn phải quyết định và ghi lại lý do cho từng thứ: chữ hoa/thường, dấu tiếng Việt, dấu câu, chữ số, và token có dấu gạch ngang / gạch dưới / dấu chấm / gạch chéo.
- Phải tự kiểm: tokenizer của bạn giữ được các định danh ở R1, hay nghiền mất chúng?
R3 · Inverted index
Phần tiêu đề “R3 · Inverted index”- Cấu trúc:
từ khoá → danh sách tài liệu chứa nó. - Posting list phải mang đủ thông tin để xếp hạng, không chỉ để trả lời có/không.
- Phải lưu được cả thống kê toàn cục mà việc xếp hạng cần.
R4 · Hệ thống lưu trữ
Phần tiêu đề “R4 · Hệ thống lưu trữ”- Index phải tồn tại sau khi tắt chương trình.
- Dựng index một lần, truy vấn nhiều lần mà không dựng lại.
- Tự chọn cách lưu (JSON, pickle, SQLite, định dạng tự định nghĩa…) — nhưng phải giải thích vì sao chọn và nó đánh đổi gì.
R5 · Truy vấn
Phần tiêu đề “R5 · Truy vấn”- Nhận
query(chuỗi) vàk(số nguyên), trả về top-k tài liệu kèm điểm. - Chỉ được chạm vào những tài liệu có ít nhất một token của truy vấn. Không quét toàn bộ corpus — và bạn phải chứng minh được bằng số.
- Trả về đúng
kkết quả, hoặc ít hơn nếu không đủ tài liệu khớp.
R6 · Xếp hạng
Phần tiêu đề “R6 · Xếp hạng”- Phải có điểm số. Trả kết quả theo thứ tự
doc_idlà không đạt. - Tự chọn công thức, nhưng phải giải thích nó thưởng cái gì và phạt cái gì.
- Điểm bằng nhau phải xử lý xác định — chạy hai lần ra kết quả y hệt.
Ràng buộc
Phần tiêu đề “Ràng buộc”- Chỉ dùng thư viện chuẩn của Python. Cho phép thêm
numpynếu muốn. - Không dùng thư viện tìm kiếm sẵn có: Whoosh,
rank_bm25,TfidfVectorizer, Elasticsearch, Lucene, hay bất kỳ vector database nào. - Không nhờ LLM viết hộ phần lõi (tokenizer, index, xếp hạng). Hỏi để hiểu thì được; lấy code về dán thì mất trắng mục tiêu học của bài này.
Nghiệm thu — chín hành vi phải đúng
Phần tiêu đề “Nghiệm thu — chín hành vi phải đúng”Đây là hành vi cần đạt, không phải test có sẵn — bạn tự viết cách kiểm.
| Mã | Tình huống | Phải xảy ra |
|---|---|---|
| T1 | Truy vấn một từ phổ biến | Trả về nhiều tài liệu, có thứ tự theo điểm |
| T2 | Truy vấn đúng một định danh ở R1 | Tài liệu chứa nó phải ở vị trí 1 |
| T3 | Truy vấn từ không tồn tại trong corpus | Danh sách rỗng. Không crash |
| T4 | Truy vấn rỗng, hoặc chỉ có khoảng trắng | Không crash; hành vi được định nghĩa rõ trong tài liệu |
| T5 | k lớn hơn số tài liệu khớp | Trả về đúng số tài liệu khớp, không lỗi |
| T6 | k = 0 hoặc k âm | Hành vi được định nghĩa rõ — rỗng hay báo lỗi, bạn chọn |
| T7 | "MẬT KHẨU" so với "mật khẩu" | Cùng kết quả — hoặc khác, nếu đó là quyết định có chủ đích và đã ghi lại |
| T8 | Chạy cùng một truy vấn hai lần | Kết quả y hệt, kể cả khi có điểm bằng nhau |
| T9 | Tắt chương trình, mở lại, truy vấn ngay | Chạy được, không cần dựng lại index |
Phải đo và báo cáo
Phần tiêu đề “Phải đo và báo cáo”- Số tài liệu · số token duy nhất (kích thước từ vựng) · tổng số posting.
- Với 3 truy vấn khác nhau: số tài liệu thực sự được chạm vào / tổng số tài liệu. Đây là bằng chứng cho R5.
- Thời gian dựng index. Thời gian trung bình một truy vấn.
- So sánh với quét tuần tự (duyệt từng tài liệu, kiểm tra chuỗi con). Trên 50 tài liệu, rất có thể bạn chưa thấy index nhanh hơn — nếu vậy hãy giải thích vì sao, và ước lượng con số ở quy mô 1 triệu tài liệu.
- Kích thước file index so với kích thước corpus gốc.
Sáu câu phải trả lời được bằng chữ
Phần tiêu đề “Sáu câu phải trả lời được bằng chữ”Viết trong README. Trả lời bằng ví dụ thật từ corpus của bạn, không trả lời chung chung.
| Mã | Câu hỏi |
|---|---|
| Q1 | Nếu tokenizer bỏ hết chữ số, truy vấn nào trong corpus của bạn trở thành vĩnh viễn không tìm ra? Cho ví dụ cụ thể. |
| Q2 | tf và df khác nhau chỗ nào? Từ nào trong corpus của bạn có df cao nhất, và nó có ích gì cho việc xếp hạng không? |
| Q3 | Vì sao xếp hạng chỉ theo “số lần xuất hiện” là ý tưởng tồi? Tìm trong corpus của bạn một trường hợp nó cho kết quả sai. |
| Q4 | Tài liệu dài có lợi thế không công bằng không? Hệ của bạn xử lý thế nào — hay chưa xử lý? |
| Q5 | Truy vấn 3 từ. Tài liệu A chứa cả 3 từ, mỗi từ một lần. Tài liệu B chỉ chứa 1 từ nhưng lặp 10 lần. Cái nào nên đứng trước? Hệ của bạn thực tế chọn cái nào? |
| Q6 | Index chiếm bao nhiêu dung lượng so với corpus gốc? Vì sao lại là con số đó? |
Kỳ vọng — bốn mức đạt
Phần tiêu đề “Kỳ vọng — bốn mức đạt”| Mức | Nghĩa là | Dấu hiệu nhận biết |
|---|---|---|
| Chưa đạt | Chưa phải một hệ tìm kiếm | Quét tuần tự toàn corpus · không có điểm số · crash ở T3/T4 · index không lưu được |
| Đạt | Chạy đúng, và bạn biết mình đã làm gì | R1–R6 xong · T1–T9 qua hết · trả lời được Q1–Q6 · có bảng số đo |
| Tốt | Đã thấy được các đánh đổi | Có chuẩn hoá độ dài tài liệu · giải thích được vì sao chọn công thức đó · tokenizer giữ được định danh và nói rõ mình đánh đổi gì |
| Xuất sắc | Đã tự tìm thấy điều bài tập không dạy | Tự phát hiện một lỗi trong thiết kế ban đầu của mình và ghi lại · đo được điều gì ngược với dự đoán ban đầu · làm phần mở rộng và đo hiệu quả của nó |
Tiêu chí đánh giá
Phần tiêu đề “Tiêu chí đánh giá”| Hạng mục | Trọng số | Đạt điểm khi |
|---|---|---|
| Đúng chức năng R1–R6 | 35% | Sáu yêu cầu hoạt động thật, không phải chỉ có mặt trong code |
| Chín hành vi T1–T9 | 20% | Qua hết, có log hoặc output chứng minh |
| Tokenizer và lý do | 15% | Từng quyết định có lý do viết ra; định danh ở R1 được xử lý có ý thức |
| Không quét toàn corpus | 10% | Chứng minh bằng số tài liệu được chạm vào, không bằng lời |
| Lưu trữ bền | 10% | T9 chạy được thật |
| Ghi lại quyết định (README) | 10% | Trả lời Q1–Q6 bằng ví dụ thật; nêu cả những gì chưa làm và vì sao |
Sản phẩm phải giao
Phần tiêu đề “Sản phẩm phải giao”- Code (một hoặc nhiều file
.py), chạy được từ dòng lệnh - File corpus
- File index đã dựng — bằng chứng cho R4
-
README.md: quyết định thiết kế · trả lời Q1–Q6 · bảng số đo - Log hoặc output của T1–T9
Bẫy đã biết
Phần tiêu đề “Bẫy đã biết”Liệt kê ra đây để bạn nhận ra khi vấp phải, không phải để đi vòng. Cách xử lý là việc của bạn.
- Một token xuất hiện nhiều lần trong cùng một tài liệu — cấu trúc của bạn đếm đúng, hay ghi đè?
- Truy vấn có từ không nằm trong từ vựng → tra cứu trực tiếp vào dict sẽ nổ.
- Dấu tiếng Việt và chuẩn hoá Unicode: hai chuỗi trông giống hệt nhau trên màn hình có thể không bằng nhau trong Python. Chỗ này rất khó phát hiện.
- Tài liệu rỗng hoặc chỉ có dấu câu → chia cho 0 khi chuẩn hoá độ dài.
- Điểm bằng nhau → thứ tự phụ thuộc thứ tự lặp của dict → T8 sập không rõ nguyên nhân.
- Lưu index bằng JSON: key kiểu số bị biến thành chuỗi khi đọc lại. Im lặng, không báo lỗi.
- Đo thời gian trên 50 tài liệu: phần lớn thời gian là chi phí khởi động, không phải thuật toán.
Mở rộng — không bắt buộc
Phần tiêu đề “Mở rộng — không bắt buộc”- Đổi công thức xếp hạng sang BM25 với hai tham số
k1,b— rồi đổi giá trị và đo xem thứ hạng thay đổi thế nào. - Truy vấn cụm từ:
"mật khẩu"phải liền nhau mới tính. Cần lưu thêm gì vào posting list? - Truy vấn boolean: AND / OR / NOT.
- Nén posting list, rồi đo lại dung lượng.
- Tự làm golden set 10 truy vấn kèm đáp án, rồi đo
recall@kvànDCG@k. - Index tăng trưởng: thêm và xoá tài liệu mà không dựng lại toàn bộ.
Thứ tự đề nghị
Phần tiêu đề “Thứ tự đề nghị”- Corpus trước. Đừng viết code khi chưa có dữ liệu thật để nhìn.
- Tokenizer. In kết quả tách từ của vài tài liệu và đọc bằng mắt trước khi đi tiếp.
- Index trong bộ nhớ. Kiểm bằng tay trên 3 tài liệu nhỏ trước khi chạy cả corpus.
- Truy vấn và xếp hạng.
- Lưu trữ bền.
- T1–T9.
- Đo số liệu.
- README — viết cuối, nhưng ghi chú quyết định ngay khi bạn ra quyết định.
Làm trước, đọc sau. Cẩm nang đi kèm bao trọn phần lý thuyết của bài này — mục 1.6 dựng inverted index bằng tay, 1.7 tính BM25 bằng tay, 1.9 các thước đo. Đọc trước sẽ tiết kiệm thời gian nhưng làm mất phần lớn giá trị của bài tập: tự vấp mới nhớ. Dùng nó khi bí, hoặc để kiểm chứng sau khi đã tự làm xong.
Cẩm nang: mục 1.6 — Inverted index · 1.7 — BM25 bằng tay · 1.9 — “Tốt” nghĩa là gì · Tầng 0 — Vocabulary mismatch · Phần 2 — Metrics