Radix trie nén cạnh và ứng dụng autocomplete, spell-check

Giới thiệu

Bài này học radix trie nén trie thường cho gọn bộ nhớ. Cây gọn này giúp gợi ý từ cực nhanh.

Kiến thức cần nhớ

Nén cạnh đơn

• Nhánh chỉ có một con thì nén thành một cạnh dài.
• Nhãn cạnh là chuỗi, không còn là một ký tự.
• Ví dụ đời thường: gộp 3 chặng đường thẳng thành một chặng.
• Càng nhiều hậu tố riêng thì nén càng tiết kiệm.

Chèn phải tách cạnh

• Tìm: so phần còn lại của khóa với nhãn cạnh.
• Khớp hết nhãn thì đi tiếp, khớp một phần thì không có.
• Chèn gặp khớp một phần thì tách cạnh làm đôi.
• Ví dụ đời thường: cây có anthem, chèn ant thì tách tại ant.

Autocomplete hai bước

• Bước 1: đi theo tiền tố tới nút tương ứng.
• Bước 2: duyệt cây con liệt kê mọi từ bên dưới.
• Chi phí không phụ thuộc kích thước từ điển.
• Ví dụ đời thường: gõ một chữ hiện ngay gợi ý.

Ví dụ

• Input: radix trie một từ duy nhất -> Output: một cạnh từ gốc tới lá.
• Câu này cho thấy nén gom cả từ vào một cạnh.
• Input: gõ tiền tố không tồn tại -> Output: danh sách gợi ý rỗng.
• Câu này cho thấy dừng ngay sau đúng độ dài tiền tố.

💻 Bài tập

Ngôn ngữ: C++. Nộp vào day-036/.

Bài 1: Radix trie

struct RNode { std::map<char, std::pair<std::string, RNode*>> edges; bool isEnd = false; };
class RadixTrie {
 public:
  void insert(const std::string &w);
  bool search(const std::string &w) const;
  bool remove(const std::string &w);     // gộp lại cạnh khi nút chỉ còn 1 con và không phải cuối từ
  size_t nodeCount() const;
};

Mỗi cạnh được đánh chỉ mục bằng ký tự đầu của nhãn, nên tối đa 1 cạnh mỗi ký tự đầu.

insert "romane"                   -> 1 cạnh "romane"
insert "romanus"                  -> tách: "roman" -> {"e", "us"}
insert "romulus"                  -> tách: "rom" -> {"an" -> {"e","us"}, "ulus"}
insert "rom"                      -> nút "rom" đánh dấu isEnd
search("roma") -> false; search("rom") -> true
remove("romanus")                 -> "an" -> "e" gộp lại thành "ane"

Bài 2: Autocomplete

std::vector<std::string> complete(const std::string &prefix, int limit). Tiền tố có thể kết thúc giữa một nhãn cạnh (ví dụ "roma" nằm giữa cạnh "an").

complete("ro", 10)    -> [rom, romane, romulus, ...]
complete("roma", 10)  -> [romane]
complete("x", 10)     -> []

Nạp 100.000 từ. So số nút và thời gian complete với trie ngày 35.

Bài 3: Spell-check đơn giản (nâng cao)

std::vector<std::string> suggestFix(const std::string &w, int maxDist): trả các từ trong trie có khoảng cách Levenshtein với w không quá maxDist.

Không tính khoảng cách với từng từ trong từ điển. Duyệt trie và giữ một hàng của bảng DP cho mỗi nút, cắt nhánh khi giá trị nhỏ nhất của hàng vượt maxDist.

từ điển có "hello", "help", "shell"; suggestFix("helo", 1) -> [hello, help]

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

• Test tách cạnh và gộp cạnh pass.
• complete đúng khi tiền tố dừng giữa nhãn.
• Bảng so sánh số nút với trie thường có số thật.
• Bài 3 cắt nhánh đúng, nhanh hơn rõ so với duyệt hết từ điển.

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

• Radix trie nén cạnh đơn thế nào?
• Tách cạnh xảy ra khi nào khi chèn?
• Autocomplete gồm 2 bước nào?
• Vì sao gợi ý nhanh dù từ điển lớn?

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