Trie (cây tiền tố): cách hoạt động, code và độ phức tạp

Trie giải quyết vấn đề gì

Tập băm (hash set) trả lời nhanh "từ chính xác này có được lưu không?", nhưng không trả lời được "những từ nào bắt đầu bằng pre?" mà không kiểm tra từng từ. Danh sách đã sắp xếp trả lời truy vấn tiền tố bằng tìm nhị phân, nhưng chèn chậm. Trie được tổ chức theo tiền tố, nên các câu hỏi về tiền tố là thế mạnh tự nhiên của nó: gợi ý tự động trong ô tìm kiếm, trò chơi chữ, kiểm tra chính tả và khớp tiền tố dài nhất cho tuyến đường mạng.

Ý tưởng giải thích đơn giản

Hãy nghĩ tới danh bạ điện thoại mà bạn thu hẹp dần từng chữ cái. Gõ c hiện mọi người bắt đầu bằng c, gõ ca thu hẹp danh sách, và cứ thế. Trie lưu các từ đúng theo hình dạng đó. Gốc là tiền tố rỗng. Mỗi node có một map từ ký tự kế tiếp tới node con, cộng một cờ kết thúc từ, vì một từ như car có thể vừa là từ hoàn chỉnh vừa là tiền tố của cart.

Ví dụ minh họa: chèn car, cart, cat và dog

Bốn từ có tổng cộng 13 chữ cái nhưng chỉ cần 8 node dưới gốc (c, a, r, t, t, d, o, g), vì car, cart và cat dùng chung ca. Tìm ca đi qua hai node và thành công với tư cách tiền tố, nhưng ca không phải là từ vì node của nó không được đánh dấu kết thúc. Tìm cow thất bại ở bước thứ hai: node c không có con o.

Cài đặt bằng Python

Mỗi node giữ một dict các con, xử lý được mọi bảng chữ cái kể cả Unicode. Phương thức starts_with thu thập mọi từ bên dưới một tiền tố, đây là cốt lõi của gợi ý tự động.

class TrieNode:
    __slots__ = ("children", "is_word")
    def __init__(self):
        self.children = {}
        self.is_word = False
class Trie:
    def __init__(self):
        self.root = TrieNode()
    def insert(self, word):
        node = self.root
        for ch in word:
            node = node.children.setdefault(ch, TrieNode())
        node.is_word = True
    def _find(self, prefix):
        node = self.root
        for ch in prefix:
            node = node.children.get(ch)
            if node is None:
                return None
        return node
    def contains(self, word):
        node = self._find(word)
        return node is not None and node.is_word
    def starts_with(self, prefix):
        node, out = self._find(prefix), []
        stack = [(node, prefix)] if node else []
        while stack:
            node, path = stack.pop()
            if node.is_word:
                out.append(path)
            for ch, child in node.children.items():
                stack.append((child, path + ch))
        return sorted(out)

t = Trie()
for w in ["car", "cart", "cat", "dog"]:
    t.insert(w)
print(t.contains("car"), t.contains("ca"))  # True False
print(t.starts_with("ca"))                  # ['car', 'cart', 'cat']
print(t.starts_with("x"))                   # []

starts_with sắp xếp đầu ra để có thứ tự ổn định. Một hệ thống gợi ý tự động thực tế còn dừng sau vài kết quả đầu và xếp hạng chúng, chẳng hạn theo số lần phổ biến đã lưu.

Độ phức tạp thời gian và không gian

Thời gian không phụ thuộc số từ n, đó là ưu điểm chính so với cây cân bằng chứa chuỗi (O(m log n) phép so sánh). Cái giá là bộ nhớ: mỗi node là một đối tượng riêng với dictionary riêng, nên trie có thể dùng bộ nhớ gấp nhiều lần so với các chuỗi thô.

Các biến thể và lỗi thường gặp

• Con dạng mảng: dùng mảng cố định 26 ô cho chữ thường tiếng Anh. Nhanh hơn dict, nhưng lãng phí với bảng chữ cái thưa hoặc lớn.
• Trie nén (radix tree, Patricia trie): gộp các chuỗi node chỉ có một con thành một cạnh gắn nhãn là chuỗi, tiết kiệm rất nhiều bộ nhớ. Radix tree được dùng trong bảng định tuyến IP và một số bộ định tuyến HTTP.
• Cây tìm kiếm tam phân (ternary search tree): mỗi node có ba con (nhỏ hơn, bằng, lớn hơn), dùng ít bộ nhớ hơn mảng rộng.
• Trie đếm: lưu một bộ đếm trong mỗi node để trả lời "có bao nhiêu từ bắt đầu bằng tiền tố này?" trong O(m).
• Trie theo bit: lưu số theo từng bit để giải các bài toán XOR lớn nhất.

Khi nào dùng trie và các bài toán phỏng vấn điển hình

Dùng trie khi bạn cần truy vấn tiền tố, khớp tiền tố dài nhất hoặc duyệt có thứ tự nhiều chuỗi có tiền tố chung. Dùng set hoặc dict khi chỉ cần tra cứu khớp chính xác: đơn giản hơn và dùng ít bộ nhớ hơn trong Python. Với danh sách từ nhỏ, tĩnh, danh sách đã sắp xếp cùng mô-đun bisect cũng trả lời tốt các truy vấn tiền tố.

Các bài toán điển hình: cài đặt trie (insert, search, starts-with), tìm từ trong lưới với nhiều từ đích, thay từ bằng gốc ngắn nhất của nó, tiền tố chung dài nhất, thiết kế hệ thống gợi ý tìm kiếm, và XOR lớn nhất của hai số bằng trie theo bit.