前綴樹

trie樹實際上是一個DFA，通常用轉移矩陣表示。行表示狀態，列表示輸入字元，(行, 列)位置表示轉移狀態。這種方式的查詢效率很高，但由於稀疏的現象嚴重，空間利用效率很低。也可以採用壓縮的存儲方式即鏈表來表示狀態轉移，但由於要線性查詢，會造成效率低下。

於是人們提出了下面兩種結構。

三數組Trie(Tripple-Array Trie)結構包括三個數組：base,next和check.

二數組Trie(Double-Array Trie)包含base和check兩個數組。base數組的每個元素表示一個Trie節點，即一個狀態；check數組表示某個狀態的前驅狀態。

這是一個用於詞頻統計的程序範例，因使用了getline(3)，所以需要glibc才能鏈接成功，沒有glibc的話可以自行改寫。代碼由“JohnBull”捐獻，遵從GPL版權聲明。