App: mini search engine với Trie, ranking và Bloom

Giới thiệu

Bài này xây máy tìm kiếm mini cho văn bản. Gõ từ khóa là ra tài liệu đúng nhất.

Kiến thức cần nhớ

Index ngược là gì

• Index ngược ánh xạ từ từ tới danh sách tài liệu chứa nó.
• Thay vì quét hết N tài liệu, chỉ tra vài posting list.
• Ví dụ đời thường: mục lục sách chỉ trang nào có từ cần tìm.
• Trie lưu từ, mỗi từ giữ danh sách doc-id và tần suất.

TF-IDF chấm điểm

• TF cao nghĩa là từ xuất hiện nhiều trong tài liệu đó.
• IDF cao nghĩa là từ hiếm trong toàn tập nên quý.
• Điểm = TF nhân IDF, tài liệu điểm cao xếp trước.
• Ví dụ đời thường: từ lạ xuất hiện nhiều trong 1 bài thì bài đó rất liên quan.

Bloom chặn từ rác

• Bloom nhớ toàn bộ từ vựng đã index.
• Từ chưa từng thấy bị chặn ngay, khỏi tra Trie.
• Ví dụ đời thường: bảo vệ chặn khách không có tên trong danh sách.
• Bloom không bao giờ bỏ sót từ có thật, chỉ nhầm nhẹ từ rác.

Ví dụ

• Input: query "trie". Output: tài liệu nhắc "trie" nhiều lần xếp trên nhắc 1 lần.
• Giải thích: TF cao hơn nên điểm TF-IDF cao hơn.
• Input: query "trie cache" kiểu AND. Output: chỉ tài liệu chứa cả 2 từ.
• Giải thích: giao 2 posting list giữ lại doc chung.

💻 Bài tập

Ngôn ngữ: Python 3 (hoặc C++). Dùng lại TF-IDF ngày 57, Bloom ngày 30, Trie ngày 35. Nộp vào day-127-search/.

Bài 1: Chỉ mục ngược

class SearchEngine:
    def add_document(self, doc_id: str, title: str, body: str): ...
    def build(self): ...                         # tính idf sau khi thêm hết
    def search(self, query: str, k: int = 10) -> list[tuple[str, float]]: ...
    def save(self, path); @classmethod def load(cls, path): ...

Tài liệu nhắc "trie" 5 lần xếp trên tài liệu nhắc 1 lần
Query có từ không tồn tại  -> bỏ qua từ đó, không lỗi
Query "\"binary search\"" -> chỉ trả tài liệu có 2 từ liền nhau

Bài 2: Bloom chặn từ lạ và gợi ý sửa

1. Bloom filter chứa toàn bộ từ vựng. Từ Bloom báo "không có" thì không tra chỉ mục.
2. Từ không có thì gợi ý "Có phải bạn muốn tìm" bằng spell-check ngày 36 (khoảng cách tối đa 2).
3. Đếm số lần Bloom tiết kiệm được lượt tra chỉ mục trên 10.000 truy vấn có 30% từ gõ sai.

Bài 3: Dữ liệu thật và đánh giá (nâng cao)

1. Index 10.000 bài Wikipedia tiếng Việt (hoặc tiếng Anh) rút gọn.
2. Đo thời gian build, kích thước chỉ mục trên đĩa, thời gian truy vấn p50/p99.
3. Tự gán nhãn 10 truy vấn với 3-5 tài liệu liên quan mỗi truy vấn. Tính precision@5 và MRR.
4. Thay TF-IDF bằng BM25 ($k_1 = 1.2$, $b = 0.75$). So precision@5 và MRR.

✅ Tiêu chí hoàn thành

• Test mẫu pass, gồm tìm cụm từ chính xác.
• save/load cho cùng kết quả tìm.
• Số liệu Bloom tiết kiệm lượt tra.
• Bảng TF-IDF vs BM25 có precision@5 và MRR.

❓ Câu hỏi ôn tập

• Index ngược biến quét toàn tập thành tra gì?
• TF và IDF mỗi cái đo điều gì?
• Bloom giúp bỏ qua query rác thế nào?
• AND và OR kết hợp posting list khác nhau ra sao?

🌕 Bạn đã hoàn thành ngày 127. Làm hết bài tập phía trên rồi sang ngày tiếp theo.