Cây tiền tố Trie: thêm, tìm từ và đếm từ theo tiền tố

Trie lưu một từ bằng đường đi thế nào?

Giả sử thêm lần lượt an, anh, ai, rồi an lần nữa. Tất cả bắt đầu bằng a nên chia sẻ cạnh đầu tiên từ gốc. Hai từ an và anh còn chia sẻ cạnh n. Chỉ anh cần thêm cạnh h. Từ ai tách sang cạnh i ngay sau a. Bạn không lưu bốn bản sao hoàn toàn độc lập của phần tiền tố chung.

Mỗi cạnh mang một ký tự. Mỗi nút biểu diễn tiền tố tạo thành bởi đường từ gốc tới nút đó. Gốc biểu diễn tiền tố rỗng. Từ một nút, không có hai cạnh đi ra cùng ký tự; vì vậy một xâu truy vấn xác định duy nhất một đường, nếu đường đó tồn tại.

Vì sao cần phân biệt từ đầy đủ và tiền tố?

Sau khi thêm anh, đường a rồi n đã tồn tại. Nhưng nếu chưa thêm an thì tìm từ đầy đủ an vẫn phải trả false. Chỉ nhìn việc đi hết đường là chưa đủ. Ta cần đánh dấu ở nút cuối mỗi từ, thường bằng biến boolean hoặc số nguyên ends.

Ở ví dụ bốn lượt thêm, ends tại an bằng 2 vì từ an được thêm hai lần; ends tại anh và ai bằng 1. Nút a có ends bằng 0 dù pass bằng 4. Vì vậy đếm tiền tố a cho kết quả 4 nhưng kiểm tra từ đầy đủ a cho kết quả false. Đây là ca đơn giản để phát hiện nhầm hai yêu cầu.

Nếu đề chỉ lưu tập hợp từ phân biệt, thêm lại cùng một từ không nên tăng số đếm. Bạn có thể kiểm tồn tại trước hoặc thiết kế cách cập nhật khác. Code của bài cố ý giữ số lần xuất hiện, nên tổng số từ là số lượt thêm chứ không phải số khóa khác nhau.

Thêm từ và đếm tiền tố

Khi thêm s, bắt đầu ở gốc và tăng pass của gốc. Đọc từng ký tự, nếu cạnh cần đi chưa có thì tạo nút mới; đi theo cạnh rồi tăng pass tại nút đến. Đọc hết s thì tăng ends của nút cuối. Mỗi lượt thêm chỉ tăng các nút thuộc chính đường của từ đó.

Muốn đếm từ có tiền tố p, đi theo p từ gốc. Nếu thiếu một cạnh thì kết quả là 0. Nếu đi hết, trả pass tại nút đó. Muốn kiểm từ đầy đủ, cũng đi cùng đường nhưng trả ends > 0. Hai truy vấn dùng chung bước tìm nút, chỉ khác thông tin cần đọc khi tới đích.

Code C++ và Python

#include <array>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
struct Node{array<int,26> child;int pass=0,ends=0;Node(){child.fill(-1);}};
class Trie{
    vector<Node> t{Node()};
    int walk(const string&s)const{
        int v=0;
        for(char ch:s){int c=ch-'a';if(c<0||c>=26||t[v].child[c]<0)return -1;v=t[v].child[c];}
        return v;
    }
public:
    // Hợp đồng: các từ chỉ có chữ ASCII a..z.
    void add(const string&s){
        int v=0;++t[v].pass;
        for(char ch:s){int c=ch-'a';
            if(t[v].child[c]<0){t[v].child[c]=(int)t.size();t.emplace_back();}
            v=t[v].child[c];++t[v].pass;
        }
        ++t[v].ends;
    }
    bool has(const string&s)const{int v=walk(s);return v>=0&&t[v].ends>0;}
    int count_prefix(const string&s)const{int v=walk(s);return v<0?0:t[v].pass;}
};
int main(){
    int n,q;vector<string>words={"an","anh","ai","an"},queries={"a","an","anh","b"};
    if(cin>>n>>q){words.resize(n);queries.resize(q);for(auto&s:words)cin>>s;for(auto&s:queries)cin>>s;}
    Trie t;for(const auto&s:words)t.add(s);
    for(const auto&s:queries)cout<<t.count_prefix(s)<<' '<<t.has(s)<<'\n';
}

class Trie:
    def __init__(self):
        self.child=[{}]
        self.passed=[0]
        self.ends=[0]
    def add(self,s):
        v=0
        self.passed[v]+=1
        for ch in s:
            if ch not in self.child[v]:
                self.child[v][ch]=len(self.child)
                self.child.append({})
                self.passed.append(0)
                self.ends.append(0)
            v=self.child[v][ch]
            self.passed[v]+=1
        self.ends[v]+=1
    def walk(self,s):
        v=0
        for ch in s:
            if ch not in self.child[v]:
                return -1
            v=self.child[v][ch]
        return v
    def has(self,s):
        v=self.walk(s)
        return v>=0 and self.ends[v]>0
    def count_prefix(self,s):
        v=self.walk(s)
        return 0 if v<0 else self.passed[v]

if __name__=='__main__':
    import sys
    d=sys.stdin.read().split()
    if d:
        n,q=map(int,d[:2]);words=d[2:2+n];queries=d[2+n:2+n+q]
    else:
        words,queries=['an','anh','ai','an'],['a','an','anh','b']
    t=Trie()
    for s in words:t.add(s)
    for s in queries:print(t.count_prefix(s),int(t.has(s)))

Chạy không nhập gì sẽ in bốn dòng 4 0, 3 1, 1 1, 0 0, lần lượt cho a, an, anh, b. Cột đầu là số từ có tiền tố, cột sau là cờ tồn tại từ đầy đủ. Để nhập riêng, dòng đầu là n và q, tiếp theo n từ, rồi q truy vấn. Đầu vào của ví dụ giới hạn chữ ASCII thường a tới z và các từ nhập qua stdin không rỗng.

Bản C++ dùng mảng 26 chỉ số con, giá trị -1 đánh dấu chưa có cạnh. Các nút nằm trong vector; khi vector tăng dung lượng, địa chỉ nút có thể thay đổi, vì vậy code lưu chỉ số và không giữ tham chiếu tới một Node qua lệnh emplace_back. Bản Python dùng dict cho các cạnh thật sự xuất hiện tại mỗi nút.

Ở mức phương thức, tiền tố rỗng đi tới gốc và đếm tất cả lượt thêm. Nếu ứng dụng cho phép từ rỗng, cần xử lý ends tại gốc nhất quán. Phần nhập bằng toán tử đọc từ của C++ không biểu diễn từ rỗng, nên quy ước đầu vào và khả năng của lớp là hai chuyện riêng.

Thời gian và bộ nhớ theo tổng độ dài từ

Với mảng 26 con, thêm hoặc tìm một xâu dài L tốn O(L) thời gian, vì mỗi ký tự chỉ chọn một cạnh. Với dict Python, đây là chi phí kỳ vọng theo thao tác băm ký tự. Nếu cần liệt kê mọi từ khớp tiền tố, ngoài tìm nút đầu còn phải duyệt và xuất kết quả; không thể gọi cả thao tác liệt kê là O(L) khi có rất nhiều từ trả về.

Gọi S là tổng độ dài các từ được thêm. Số nút tối đa không vượt S+1, nhưng các từ chung tiền tố có thể dùng ít nút hơn. Mỗi nút C++ trong ví dụ cấp sẵn 26 ô con, nên tổng vùng con có cận O(26S), thường viết O(S) khi coi bảng chữ cái cố định. Dict tiết kiệm các ô cạnh vắng, đổi lại có chi phí đối tượng và bảng băm riêng.

Trie không luôn tiết kiệm bộ nhớ hơn một set từ. Với rất nhiều từ không chung tiền tố, các nút và con trỏ có thể tốn đáng kể. Nếu chỉ cần hỏi từ đầy đủ có tồn tại, set hoặc bảng băm thường đơn giản; Trie hữu ích hơn khi truy vấn theo tiền tố là yêu cầu chính.

Từ Trie ký tự sang Trie bit tìm XOR

Một số nguyên có thể xem là xâu bit cố định B vị trí. Mỗi nút khi đó chỉ có hai con 0 và 1. Muốn tìm số đã lưu làm XOR với x lớn nhất, đi từ bit cao xuống thấp, ưu tiên nhánh có bit ngược x để tạo bit XOR bằng 1; nếu không có mới đi nhánh cùng bit.

Ưu tiên bit cao đúng vì giá trị đóng góp của một bit cao lớn hơn tổng mọi bit thấp hơn nó. Với bài cặp chỉ số khác nhau, có thể truy vấn trên những số đã thêm trước rồi mới thêm số hiện tại, tránh ghép một phần tử với chính nó. Cần chốt độ rộng B và cách xử lý số âm; không trộn biểu diễn số có dấu với so sánh XOR không dấu tùy tiện.

Phần code chính của bài cài Trie ký tự, chưa cài Trie bit. Bài luyện XOR miễn phí bên dưới là bước mở rộng riêng, yêu cầu chuyển bảng cạnh 26 ký tự thành hai nhánh bit.

Lỗi hay gặp và cách tự kiểm

Để tự kiểm tra cây Trie vừa cài đặt, bạn có thể đối chiếu hàm đếm tiền tố với thao tác quét danh sách từ bằng startswith, và kiểm tra tìm từ đầy đủ bằng phép tra trên danh sách gốc ở các ca từ điển rỗng, từ một ký tự, từ trùng lặp và nhiều từ chung tiền tố.

Luyện ngay trên Big-O Coding

Hai bài cài Trie và đếm tiền tố khớp trực tiếp phương thức trong bài. Bài XOR miễn phí mở rộng sang Trie bit, không dùng nguyên mảng con 26 chữ cái.

Câu hỏi thường gặp

Nguồn tham khảo

• cp-algorithms: Construction of the trie
• Open Data Structures: BinaryTrie
• Python: dict