詳解用Python程式實作字典樹Trie的結構技巧

字典樹（Trie）可以保存一些字串->值的對應關係。基本上，它跟 Java 的 HashMap 功能相同，都是 key-value 映射，只不過 Trie 的 key 只能是字串。

Trie 的強大之處就在於它的時間複雜度。它的插入和查詢時間複雜度都為 O(k) ，其中 k 為 key 的長度，與 Trie 中保存了多少個元素無關。 Hash 表號稱是 O(1) 的，但在計算 hash 的時候就肯定會是 O(k) ，而且還有碰撞之類的問題；Trie 的缺點是空間消耗很高。
至於Trie樹的實現，可以用數組，也可以用指針動態分配，我做題時為了方便就用了數組，靜態分配空間。
Trie樹，又稱單字找出樹或鍵樹，是一種樹狀結構，是一種哈希樹的變種。典型應用是用於統計和排序大量的字串（但不僅限於字串），所以經常被搜尋引擎系統用於文字詞頻統計。它的優點是：最大限度地減少無謂的字串比較，查詢效率比哈希表高。
Trie的核心思想是空間換時間。利用字串的公共前綴來降低查詢時間的開銷以達到提高效率的目的。
Trie樹中每個單字都是透過character by character方法進行存儲，相同前綴單字共用前綴節點.
可以看到,每條路徑組成一個單字.上面這顆樹存了to/tea/ ted/ten/inn這些字.

Trie樹的基本性質可以歸納為：
（1）根節點不包含字符，除根節點意外每個節點只包含一個字元。
（2）從根節點到某一個節點，路徑上經過的字元連接起來，為該節點對應的字串。
（3）每個節點的所有子節點包含的字串不相同。

性質
（1）根節點不包含字符，除根節點外的每個節點只包含一個字符。
（2）從根節點到某一個節點，路徑上經過的字元連接起來，為該節點對應的字串。
（3）每個節點的所有子節點包含的字串不相同。

基本思想（以字母樹為例）：
1、插入過程
#對於一個單詞，從根開始，沿著單字的各個字母所對應的樹中的節點分支向下走，直到單字遍歷完，將最後的節點標記為紅色，表示該單字已插入Trie樹。
2、查詢過程
同樣的，從根開始按照單字的字母順序向下遍歷trie樹，一旦發現某個節點標記不存在或單字遍歷完成而最後的節點未標記為紅色，則表示該單字不存在，若最後的節點標記為紅色，表示該單字存在。

應用
（1）詞頻統計
比直接用hash節省空間
（2）搜尋提示
#輸入前綴的時候提示可以構成的字
（3）作為輔助結構
如字尾樹，AC自動機等的輔助結構

##實作
雖然Python沒有指標,但是可以用嵌套字典來實現樹結構.對於非ascii的單字,統一用unicode編碼來插入與搜尋.

#coding=utf-8 
class Trie: 
  root = {} 
  END = '/' 
  def add(self, word): 
    #从根节点遍历单词,char by char,如果不存在则新增,最后加上一个单词结束标志 
    node = self.root 
    for c in word: 
      node=node.setdefault(c,{}) 
    node[self.END] = None 
 
  def find(self, word): 
    node = self.root 
    for c in word: 
      if c not in node: 
        return False 
      node = node[c] 
    return self.END in node

更多詳解用Python程式碼實作字典樹Trie的結構技巧相關文章請關注PHP中文網！