Bài 24: Bàn phím điện thoại đoán chữ bạn định gõ như thế nào? Cây Trie và mô hình n-gram

Bạn gõ "hôm n…" và bàn phím đã gợi ý "hôm nay". Gõ "em đi" và nó đoán tiếp "học". Bàn phím điện thoại không đọc được suy nghĩ của bạn – nó dùng hai ý tưởng thuật toán rất đẹp: cây tiền tố để hoàn thành từ, và đếm xác suất để đoán từ tiếp theo.

Bài thứ hai mươi bốn của chuyên mục "Thuật toán trong đời sống": cây Trie, mô hình n-gram và bàn phím dự đoán.

1. Từ T9 đến bàn phím thông minh

Thời điện thoại bàn phím số, mỗi phím chứa 3–4 chữ cái. Hệ thống T9 do Martin King và Cliff Kushler phát triển (công ty Tegic Communications, thành lập năm 1995) cho phép bấm mỗi phím một lần, rồi máy tự đoán từ bạn muốn gõ. Thú vị là T9 bắt nguồn từ một thiết bị hỗ trợ giao tiếp cho người khuyết tật.

2. Hoàn thành từ: cây tiền tố (Trie)

Trie là cây mà mỗi nhánh là một chữ cái. Các từ có chung phần đầu (tiền tố) dùng chung nhánh: "hoc" và "hom" cùng đi qua h → o. Khi bạn gõ "h", ta chỉ cần đi xuống nút "h" rồi liệt kê các từ bên dưới, ưu tiên từ xuất hiện nhiều nhất. Việc tìm đến nút của tiền tố chỉ tốn số bước bằng độ dài tiền tố, dù kho từ lớn đến đâu.

3. Đoán từ tiếp theo: mô hình n-gram

Ý tưởng: đếm xem sau từ "em" thường là từ gì. Nếu trong dữ liệu, "em đi" xuất hiện 3 lần và "em học" 1 lần, thì sau "em" nên gợi ý "đi" trước. Đếm theo cặp 2 từ gọi là bigram; theo bộ n từ gọi là n-gram. Đây là mô hình ngôn ngữ kinh điển, được trình bày trong giáo trình "Speech and Language Processing" của Jurafsky và Martin (ĐH Stanford).

Gợi ý từ bằng Trie và bigram

#include <bits/stdc++.h>
using namespace std;
struct Node { map<char, int> next; int cnt = 0; };   // cnt > 0: kết thúc một từ
vector<Node> t(1);                                    // cây Trie, nút 0 là gốc
void add(const string& w){
    int u = 0;
    for(char c : w){
        if(!t[u].next.count(c)){ t[u].next[c] = t.size(); t.push_back(Node()); }
        u = t[u].next[c];
    }
    t[u].cnt++;
}
void collect(int u, string w, vector<pair<int,string>>& out){
    if(t[u].cnt) out.push_back({-t[u].cnt, w});
    for(auto& [c, v] : t[u].next) collect(v, w + c, out);
}
void suggest(const string& p){
    int u = 0;
    for(char c : p){ if(!t[u].next.count(c)) return; u = t[u].next[c]; }
    vector<pair<int,string>> out; collect(u, p, out); sort(out.begin(), out.end());
    cout << "Go '" << p << "' ->";
    for(int i = 0; i < (int)out.size() && i < 3; i++) cout << ' ' << out[i].second << '(' << -out[i].first << ')';
    cout << '\n';
}
int main(){
    vector<string> corpus = {"hom nay em di hoc", "hom nay troi dep", "em di choi cong vien",
                             "em di hoc lap trinh", "hoc lap trinh rat vui", "hom nay em hoc thuat toan"};
    map<string, map<string,int>> bigram;               // đếm cặp từ đi liền nhau
    for(auto& s : corpus){
        stringstream ss(s); vector<string> w; string x;
        while(ss >> x){ w.push_back(x); add(x); }
        for(int i = 0; i + 1 < (int)w.size(); i++) bigram[w[i]][w[i+1]]++;
    }
    suggest("h"); suggest("tr");
    for(string w : {"em", "di", "lap"}){
        vector<pair<int,string>> v;
        for(auto& [b, c] : bigram[w]) v.push_back({-c, b});
        sort(v.begin(), v.end());
        cout << "Sau '" << w << "' ->";
        for(int i = 0; i < (int)v.size() && i < 2; i++) cout << ' ' << v[i].second << '(' << -v[i].first << ')';
        cout << '\n';
    }
}

from collections import defaultdict, Counter

class Trie:
    def __init__(self):
        self.root = {}
    def add(self, word):
        node = self.root
        for ch in word:                       # mỗi ký tự là một nhánh của cây
            node = node.setdefault(ch, {})
        node["#"] = node.get("#", 0) + 1      # "#" đánh dấu hết từ, lưu số lần xuất hiện
    def suggest(self, prefix, k=3):
        node = self.root
        for ch in prefix:
            if ch not in node: return []
            node = node[ch]
        found, stack = [], [(node, prefix)]
        while stack:                          # duyệt mọi từ bắt đầu bằng prefix
            node, w = stack.pop()
            for ch, nxt in node.items():
                if ch == "#": found.append((nxt, w))
                else: stack.append((nxt, w + ch))
        return [f"{w}({c})" for c, w in sorted(found, key=lambda x: (-x[0], x[1]))[:k]]

corpus = ["hom nay em di hoc", "hom nay troi dep", "em di choi cong vien",
          "em di hoc lap trinh", "hoc lap trinh rat vui", "hom nay em hoc thuat toan"]
trie, bigram = Trie(), defaultdict(Counter)
for s in corpus:
    words = s.split()
    for w in words: trie.add(w)
    for a, b in zip(words, words[1:]): bigram[a][b] += 1    # đếm cặp từ đi liền nhau

print("Go 'h' ->", *trie.suggest("h"))
print("Go 'tr' ->", *trie.suggest("tr"))
for w in ["em", "di", "lap"]:
    print(f"Sau '{w}' ->", *[f"{x}({c})" for x, c in bigram[w].most_common(2)])

Kết quả chạy:

Go 'h' -> hoc(4) hom(3)
Go 'tr' -> trinh(2) troi(1)
Sau 'em' -> di(3) hoc(1)
Sau 'di' -> hoc(2) choi(1)
Sau 'lap' -> trinh(2)

Chỉ với 6 câu (viết không dấu cho đơn giản), chương trình đã biết gõ "h" thì gợi ý "hoc", sau "lap" thì gần như chắc chắn là "trinh". Bàn phím thật học từ lượng văn bản lớn hơn rất nhiều.

4. Bàn phím hiện đại: AI học ngay trên điện thoại

• Google Gboard: năm 2017, Google giới thiệu học liên kết (federated learning) và thử nghiệm trên Gboard. Mô hình được huấn luyện ngay trên điện thoại khi máy rảnh, đang sạc và dùng Wi-Fi; chỉ phần cập nhật mô hình được gửi đi, không gửi nội dung bạn gõ. Năm 2018, nhóm nghiên cứu của Google công bố dùng cách này để huấn luyện mạng nơ-ron đoán từ tiếp theo cho bàn phím.
• Apple: khi giới thiệu iOS 17 (6/2023), Apple cho biết tính năng tự sửa lỗi dùng mô hình ngôn ngữ transformer và gợi ý từ hiện ngay trong dòng đang gõ.

Dù là mạng nơ-ron hiện đại hay bảng đếm n-gram đơn giản, câu hỏi cốt lõi vẫn như nhau: "với những từ đã gõ, từ nào có xác suất xuất hiện tiếp theo cao nhất?"

5. Bạn học được gì từ đây?

• Trie là cấu trúc dữ liệu mạnh cho bài toán tiền tố, hay gặp trong đề thi.
• Đếm tần suất bằng map/dict đã đủ tạo ra một mô hình ngôn ngữ đơn giản.
• Dữ liệu càng nhiều, dự đoán càng chính xác – nhưng cũng cần bảo vệ quyền riêng tư của người dùng.

Bài tập luyện tập

• CSES – Word Combinations (Trie kết hợp quy hoạch động)
• Mở rộng code thành trigram: đoán từ tiếp theo dựa trên 2 từ trước đó.
• Viết lại với tiếng Việt có dấu và một đoạn văn bạn tự chọn.

📖 ĐỌC TIẾP: THUẬT TOÁN TRONG ĐỜI SỐNG

Bài 25: Robot hút bụi đi khắp nhà như thế nào? BFS và bài toán phủ kín

Đọc tiếp: robot hút bụi & BFS →

← Bài trước: Shazam & bảng bămXem tất cả 27 bài →

Nguồn tham khảo

• Gizmodo – How T9 predictive text input changed mobile phones
• PhoneArena – Co-inventor of T9 text entry dies at age 60
• Google Research Blog (06/04/2017) – Federated Learning: Collaborative Machine Learning without Centralized Training Data
• Hard et al. (2018) – Federated Learning for Mobile Keyboard Prediction (arXiv 1811.03604)
• Apple (05/06/2023) – iOS 17 makes iPhone more personal and intuitive (bản trên Business Wire)
• Jurafsky & Martin – Speech and Language Processing, Chương 3: N-gram Language Models
• Princeton COS 226 – Tries (Sedgewick & Wayne)