跳轉到

3.1 Trie樹#

概念說明#

Trie（字典樹、前綴樹）是把一組字串儲存成樹的資料結構：從根節點出發，每一條邊對應一個字元；某個字符串的「前綴路徑」就是從根走到對應節點的路徑。一組樣式共享共同前綴時在樹上自動合併，因此空間與樣式總長度成正比（共用可進一步壓縮）。每個節點標記「是否為完整單詞的結尾」（is_word），以區分「前綴存在」與「完整單詞存在」。

Trie 的核心賣點：查詢時間只與查詢字串長度 L 成正比，每次沿著邊走一步（用字典或陣列找子節點），與字典裡有多少詞無關。英文建議用 dict 子節點以節省空間（字母表大時建 26 槽陣列反而浪費；中文則用 dict 更必要，因為常用漢字數千）。

三大基本操作： - 插入：從根沿前綴走，缺邊就建新節點，走完標記 is_word。 - 查詢完整單詞：沿前綴走，任何一步缺邊即不存在；走完檢查 is_word。 - 前綴查詢：走到查詢前綴末端即算存在（不必檢查 is_word），這是實現自動完成（autocomplete）的基礎。

進階操作包含：DFS 收集某前綴下所有詞（自動完成候選）、刪除節點遞回修剪、加上失敗連結成為 Aho-Corasick（下一節）。Trie 也用於 IP 路由（二進位 trie）、中文注音/拼音輸入法的候選詞組織等。

演算法步驟#

  1. 插入（單詞 s）：cur = 根；對每個字元 c：若 cur.children 缺 c 就建立；cur = cur.children[c]；結束時 cur.is_word = True。
  2. 尋找節點（字串 s）：同上走完全部字元，回傳節點或 None。
  3. 自動完成（前綴 p）：先用「尋找節點」定位前綴節點，再 DFS 該子樹收集全部 is_word 詞語。
  4. 刪除：DFS 找到底之後，去除 is_word；若子節點清空且非其他單詞前綴，向上修剪。

Python 程式碼範例#

class TrieNode:
    __slots__ = ("children", "is_word", "word")
    def __init__(self):
        self.children = {}      # 字元 -> TrieNode
        self.is_word = False
        self.word = None        # 完整該詞時的字串，方便自動完成收集

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        cur = self.root
        for ch in word:
            if ch not in cur.children:
                cur.children[ch] = TrieNode()
            cur = cur.children[ch]
        cur.is_word = True
        cur.word = word

    def find_node(self, s):
        cur = self.root
        for ch in s:
            if ch not in cur.children:
                return None
            cur = cur.children[ch]
        return cur

    def search(self, word):          # 完整單詞？
        node = self.find_node(word)
        return node is not None and node.is_word

    def starts_with(self, prefix):   # 前綴存在？
        return self.find_node(prefix) is not None

    def autocomplete(self, prefix, limit=10):
        node = self.find_node(prefix)
        if node is None:
            return []
        ans = []
        def dfs(u):
            if len(ans) >= limit:
                return
            if u.is_word:
                ans.append(u.word)
            for ch in sorted(u.children):
                dfs(u.children[ch])
        dfs(node)
        return ans

    def delete(self, word):
        def dfs(u, i):
            if i == len(word):
                u.is_word, u.word = False, None
                return not u.children
            c = word[i]
            child = u.children.get(c)
            if not dfs(child, i + 1):
                return False
            del u.children[c]
            return not u.children and not u.is_word
        if self.search(word):
            dfs(self.root, 0)

tr = Trie()
words = ["演算法", "演算法分析", "演算", "字串", "字串比對", "字元編碼"]
for w in words:
    tr.insert(w)

print(tr.search("演算法"))           # True
print(tr.search("演算"))             # False（是前綴不是完整詞）
print(tr.starts_with("字串比"))     # True
print(tr.autocomplete("演"))        # ['演算', '演算法', '演算法分析']
tr.delete("演算")
print(tr.autocomplete("演"))

複雜度分析#

設樣式集合總字元數 M、查詢字串長度 L、字母表大小 |Σ|：

  • 插入/查詢：O(L) 時間；空間最壞 O(M × |Σ|)（用陣列），用 dict 實作般是 O(M)。
  • 自動完成 DFS：O(子樹節點數)。
  • 與 Python set/dict 查詢 O(L)（平均）比起來沒有速度優勢，Trie 的優勢在排序輸出、前綴查詢、共享前綴、與失敗函數整合做聯合比對。

練習#

  1. 為 Trie 實作 iter_words()：以 DFS 中序輸出所有單詞，驗證輸出與排序後的列表一致。
  2. 實作最長前綴匹配：給一個句子，找出每個位置起「在字典中最長的匹配前綴」（中文分詞的一種正/反向最大匹配雛形）。
  3. 將十萬筆英文單詞分別插入 Trie 與 set，比較建置時間與記憶體（可用 sys.getsizeof 粗估或 tracemalloc），並討論壓縮 Trie（Radix Tree）如何減少空間。