[心得] Prefix-Search 作業心得(1)

[buckle (buckle)]

#include <自己的作業自己寫.h>

**Trie（字典樹）
在實作 Prefix-search 的時候，當然不能不提到 trie 這樣特別的樹狀資料結構。
以下為 trie 的簡介：
字典樹最大的特性為"利用單字的共同前綴（common prefix）作為儲存依據"，用來
減少佔用的記憶體與加快搜尋的效能。共同前綴說穿了就是數個單字"前面幾個相同的
字母"，像是 CUT 與 CUTE 就有 CUT 這個共同前綴。

舉例而言，若依序輸入 CAT、CUT、CUTE、TO、B 五筆資料，則會建立如下圖的字典樹。
https://i.imgur.com/quFVMHU.png (圖片來源自：https://goo.gl/vyvzAG)

而 Trie 建立的規則如下：
1. 所有 nodes 皆接在 root 這個不包含任何字母的節點底下。
2. 除了 root 以外，其他 nodes 皆代表一個字母。
3. 每個 node 最多可能有 26 個子節點(若universal set 為所有不分大小寫的字母)。
4. 每個 children 皆為字串可能的下一個字母，在上圖中，C 節點後有 A 與 U 兩
   個可能的字母。
5. 整棵樹的高度為 "最長字串 + 1"
6. "並非"只有葉子代表一個字串的結尾，從 root 向下走訪的每個節點，皆可能是某
   個字串的結尾。如上圖中的 CUT。

簡易實作步驟(以上面的字典樹為例)：
1. 一開始，建立一個 value = NULL 的節點 root;

2. 欲插入字串為 CAT，將 CAT 拆成 C、A、T;
3. root 沒有 value == C 的 children，建立一個 children，value = C;移動到 C;
4. 因 C 沒有 value == A 的 children，建立一個 children，value = A;移動到 A;
5. 因 A 沒有 value == T 的 children，建立一個 children，value = T;移動到 T;

6. 欲插入字串為 CUT，將 CUT 拆成 C、U、T;
7. 在 root 找到 children C，移動到 C;
8. 因 C 沒有 value == U 的 children，建立一個 children，value = U;移動到 U;
9. 因 U 沒有 value == T 的 children，建立一個 children，value = T;移動到 T;
.
.
.

優點：trie 的優點顯而易見，即是運作速度快且容易撰寫，針對搜尋目標字串是否存在
      與前綴相關的議題有不錯的效果。

缺點：因為每個 node 皆可能有最大分支度的 child nodes 數，因此在 node struct 宣
      告時必須宣告 N(最大分支度) 個指標。在多數情況下，這些指標不會被充份利用
      ，更可能有許多空指標，勢必造成巨大的記憶體成本。

TODO:改用 Ternary search tree (TST)以減少不必要的記憶體成本，與 trie 相比較，
     列出 優缺點。

此文章僅為個人學習留下點足跡，若有錯誤歡迎批評指教。

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 118.171.198.108
※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1521903961.A.9A1.html
推 gus2: 第5好像是"因 A"  如果可以的話，分享你的實作也不錯
※ 編輯: buckle (118.171.198.108), 03/24/2018 23:15:48
→ wtchen: 請問你有C/C++的實作嗎？不然有點離題喔
有喔 之後會貼一些c語言實作，只是因爲這整個系列會有點長，所以想說分段打心得
→ wtchen: 雖然我對你的分享很有興趣，不過這邊畢竟是C/C++討論區
推 KanzakiHAria: 何謂運作速度快? 有時間複雜度嗎?
→ KanzakiHAria: 紅黑樹保證三個操作都是O(log N) N 是數量
→ KanzakiHAria: 這邊的trie時間複雜度好像還會跟bit length有關
※ 編輯: buckle (42.77.73.70), 03/25/2018 10:45:41
→ buckle: 可參考這篇 有時間複雜度的比較
→ buckle: http://www.raychase.net/1783
D※ 編輯: buckle (42.77.73.70), 03/25/2018 10:55:45
→ wtchen: 原po我等你兩天，請你補足或再po跟C/C++有關的部份
推 wtchen: 不然我只能砍文
推 wtchen: PS: 請不要付煎，我真的很有興趣看
噓 Sidney0503: 當你個版?
※ 編輯: buckle (118.171.198.108), 03/25/2018 22:47:17