App: spell checker với Trie và độ tương đồng

Giới thiệu

Bài này xây app sửa lỗi gõ sai. Gõ sai 1 chữ là máy gợi ý đúng ngay.

Kiến thức cần nhớ

Trie làm từ điển

• Trie lưu 100 nghìn từ, kiểm tra tồn tại tốn $O(m)$.
• Từ vắng trong Trie thì đánh dấu sai kèm vị trí.
• Ví dụ đời thường: dò từ điển xem từ này có thật không.
• Từ đúng hiếm có trong từ điển thì không báo sai.

Edit distance sinh ứng viên

• Edit distance đếm số lần sửa để biến từ sai thành đúng.
• 4 phép sửa: xóa, chèn, thay, hoán vị 2 chữ.
• 80% lỗi gõ cách đáp án đúng 1 edit nên tối ưu đường này trước.
• Ví dụ đời thường: komputer sửa 1 chữ thành computer.

Xếp hạng bằng khoảng cách và tần suất

• Điểm gồm khoảng cách nhỏ và tần suất cao.
• Từ hay dùng thắng khi nhiều ứng viên cùng khoảng cách.
• Giữ top-3 bằng heap cho rẻ.
• Người dùng chọn từ nào thì tăng tần suất từ đó.

Ví dụ

• Input: từ sai komputer. Output: gợi ý hạng 1 là computer.
• Giải thích: cách đúng 1 edit và tần suất rất cao.
• Input: văn bản 200 từ có 10 lỗi cài sẵn. Output: bắt đúng 10 vị trí, không báo oan từ đúng.
• Giải thích: Trie kiểm tra từng từ nên chỉ từ vắng mới bị gắn cờ.

💻 Bài tập

Ngôn ngữ: C++17 (hoặc Python). Dùng Trie ngày 35, edit distance ngày 77, spell-check ngày 36. Nộp vào day-146-spell/.

Bài 1: Kiểm tra chính tả văn bản

struct Misspelling { std::string word; size_t line, col; std::vector<std::string> suggestions; };
class SpellChecker {
 public:
  static SpellChecker fromFile(const std::string &dictPath);   // "từ<TAB>tần_suất"
  std::vector<Misspelling> check(const std::string &text, int topK = 3) const;
  void learn(const std::string &word);                          // người dùng chọn/thêm từ
};

"teh cat" -> teh ở (1,1), gợi ý [the, ten, tea]
"recieve" -> gợi ý đầu tiên "receive" (hoán vị ie -> ei)
"COVID https://x.com a@b.vn 2024" -> không báo lỗi

Bài 2: Sinh ứng viên nhanh

So 3 cách sinh ứng viên cho từ sai:

Từ điển 100.000 từ, 1000 từ sai. In thời gian trung bình mỗi từ và kiểm tra 3 cách cho cùng danh sách gợi ý.

Bài 3: Đánh giá và học (nâng cao)

1. Dùng bộ lỗi chính tả có đáp án (ví dụ Birkbeck spelling corpus, hoặc tự tạo 500 cặp bằng cách chèn lỗi ngẫu nhiên vào từ đúng). Tính accuracy@1 và accuracy@3.
2. Thêm mô hình lỗi bàn phím: thay thế giữa 2 phím kề nhau có chi phí 0.5. So lại accuracy.
3. learn(word) tăng tần suất. Chứng minh sau khi học, gợi ý thay đổi đúng.
4. CLI: spell check file.txt in lỗi dạng file.txt:3:15: "teh" -> the, ten, tea.

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

• Test mẫu pass, gồm hoán vị và các chuỗi bị bỏ qua.
• Bảng thời gian 3 cách, cùng kết quả.
• Bảng accuracy@1, @3 có và không có mô hình bàn phím.
• CLI in đúng định dạng.

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

• Trie kiểm tra từ tồn tại thế nào?
• 4 phép sửa trong edit distance là gì?
• Vì sao tối ưu đường 1-edit trước?
• Tần suất giúp chọn gợi ý ra sao?

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