App: autocomplete có Trie và cache LRU

Giới thiệu

Bài này xây app gợi ý từ khi gõ phím. Gõ vài chữ là thấy từ cần tìm ngay.

Kiến thức cần nhớ

Trie lưu từ điển

• Trie là cây chia sẻ tiền tố, tra prefix rất nhanh.
• Mỗi nút terminal lưu tần suất và từ đầy đủ.
• Ví dụ đời thường: mục lục từ điển nhóm chung chữ đầu.
• Tra prefix tốn $O(m)$ với m là độ dài prefix.

Heap xếp hạng top-K

• Thu thập ứng viên rồi giữ K từ tốt nhất bằng min-heap.
• Điểm = tần suất + thưởng khớp dài.
• Ví dụ đời thường: chọn 5 món ăn được gọi nhiều nhất.
• Heap giữ chi phí ở $O(R log K)$ thay vì sắp hết.

LRU cache cho prefix nóng

• LRU nhớ K prefix vừa hỏi, hỏi lại trả ngay $O(1)$.
• Khi tần suất từ đổi thì xóa cache liên quan.
• Ví dụ đời thường: để món hay gọi ở ngăn đầu tủ lạnh.
• Hit-rate mục tiêu trên 70% với 1024 prefix.

# Luồng gợi ý: cache trước, Trie sau
def suggest(prefix, k):
    if cache.has(prefix):  # trúng cache trả ngay
        return cache.get(prefix)
    node = trie.find(prefix)  # tìm nút prefix
    topk = ranker.topk(node, k)  # xếp hạng bằng heap
    cache.put(prefix, topk)  # lưu lại cho lần sau
    return topk

Ví dụ

• Input: prefix "ban", K=5. Output: 5 từ bắt đầu bằng "ban" xếp theo tần suất giảm dần.
• Giải thích: Trie tìm nhánh "ban", heap giữ 5 từ hot nhất.
• Input: gõ lại 100 prefix nóng 2 vòng. Output: vòng 2 hit-rate trên 70%, p95 giảm 30%.
• Giải thích: vòng 2 trúng cache nên không cần duyệt cây.

💻 Bài tập

Ngôn ngữ: C++17 (hoặc ngôn ngữ bạn chọn cho app). Đây là app hoàn chỉnh, dành 90 phút. Dùng lại Trie ngày 35, LRU ngày 39, heap ngày 26. Nộp vào day-126-autocomplete/.

Bài 1: Lõi gợi ý

class Autocomplete {
 public:
  void addWord(const std::string &w, uint64_t freq);        // có rồi thì cộng tần suất
  void recordSelection(const std::string &w);               // người dùng chọn từ: freq += 1
  std::vector<std::pair<std::string, uint64_t>> suggest(const std::string &prefix, int k);
  static Autocomplete fromFile(const std::string &path);    // mỗi dòng "từ<TAB>tần_suất"
};

Từ điển: "trie"(50), "tree"(80), "trick"(20), "try"(80)
suggest("tr", 3)  -> [(tree,80), (try,80), (trie,50)]
suggest("xyz", 3) -> []
recordSelection("trick") x 70 -> suggest("tri", 1) = [(trick, 90)]

Bài 2: Cache và tính nhất quán

1. Bọc suggest bằng LRU 1024 mục, khóa là (prefix, k).
2. recordSelection(w) phải xóa cache của mọi tiền tố của w (không xóa toàn bộ cache).
3. In hits, misses, hitRate.

Sinh 100.000 truy vấn theo phân bố Zipf trên 5000 tiền tố. Mục tiêu hit rate trên 70%.

Bài 3: Giao diện và đo hiệu năng (nâng cao)

1. CLI tương tác: gõ từng ký tự (hoặc cả tiền tố rồi Enter), in 5 gợi ý. Lệnh :pick <từ> gọi recordSelection. Lệnh :stats in hit rate.
2. Nạp từ điển 300.000 từ (có tần suất, ví dụ từ Wikipedia word frequency). In thời gian nạp và bộ nhớ.
3. Đo p50, p99 độ trễ suggest có và không có cache.

Mục tiêu: p99 < 1 ms có cache, < 5 ms không cache với 300.000 từ

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

• Test mẫu pass, gồm trường hợp hòa tần suất.
• Cache không trả kết quả cũ sau recordSelection (có test).
• Hit rate trên 70% với dữ liệu Zipf.
• Bảng p50/p99 và bộ nhớ có số thật. README.md có hướng dẫn chạy.

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

• Trie giúp tra prefix nhanh thế nào?
• Heap giữ top-K theo điểm gì?
• LRU cache tăng tốc prefix nóng ra sao?
• Khi nào phải xóa cache cũ?

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