--- tags: 研究所 --- # 2017q3 Homework2 (prefix-search) contributed by < `twngbm` > ### Ternary search tree 介紹 * 三元搜尋樹是一種字典樹（trie），以下將講解何為字典樹。 #### Trie * Trie 樹是一種利用字串特性來實現的資料結構，英文的每一個單字，有可能會有同樣的前綴，例如apple 和 append 的共同前綴就是 app ，我們可以利用此一特行，來節省儲存空間和加速搜尋時間，也因為此依特性 trie 特別適用於處理大量字串的資料結構時。 * 以下範例示範建構依 Trie 樹，並在樹中插入子節點 :::info 首先創造一根節點，根節點必為空 ::: ``` @ ``` :::info 我們試著插入單字and 1. 首先我們先把and拆分成 a, n ,d 2. 因為前綴a為第一次出現，因此我們在根節點底下創造一新子節點，節點值為a 3. 接下來從這個節點（a）出發，我們剩下 n, d 4. n也是第一次出現，因此我們在a節點下創造一新的n節點，d節點依此累推 ::: ``` @ / a / n / d ``` :::info 再來我們試著插入單字 at 1. 單字拆解成 a,t，從根節點出發 2. a節點以存在，因此不再創造新的節點 3. a節點以下t 節點不存在，因此創造一新的節點t ::: ``` @ / a / \ n t / d ``` >中英文間請以空白隔開[name=課程助教][color=red] :::info 以下示範插入and,at,be,bear，分別對應的value值為0，1，2，3 1. 當我執行 get(be) 時，會 return 2 2. 當我執行 get(bea) 時，會 return NULL，因為搜尋的末節點並不存在 value 值 3. 當我執行get(beat)時，也會return NULL，因為bea節點後並沒有t的節點位置 ::: ``` @ / \ a b / \ \ n t e 2 / 1 \ d a 0 \ r 3 ``` 從以上的結構，我們可以發現以下幾點事情。 :::warning 1. 如果是針對英文單字的資料結構來做 trie 的話，這個trie 樹將會是一個26 叉樹，因為每一個節點會包含可能的26個英文單字。 2. 每個節點創造時，都必須同時創造26個值為NULL的子節點。 3. Trie 的優點為查詢且運作速度快，而且可以很輕易的做到前綴搜尋的動作，但是缺點就像上面所說的，其必須消耗大量的記憶體來儲存非常多的指標，每一個節點都必須建立26個指標，而且有些可能還是NULL。 ::: #### Ternary search tree * 我們可以從上面的例子發現，當元素的數量越大，trie所需的記憶體空間就會急遽上升，光是英文大寫字母的trie，每一個節點就會需要26個pointer，如果加上小寫數字和常用符號，trie的結構會變得非常大而不切實際。 * 因此我們介紹一種簡化版的trie ，Ternary search tree(TST)，這種樹的每個節點最多只會有3個子節點，分別是小於，等於，大於。 * 以下範例示範ternary search tree :::info 首先我們插入一值good，value=0，我們先拆分成g，o，o，d 基本概念跟trie一樣，但是這邊我們將 g 放入根節點 ::: ``` g | o | o | d ``` :::info 接著我們嘗試插入單字got 1. 我們先比對g，發現根節點和got的第一個字母相同（g=g） 2. 因此pointer往下，來到o節點，發現o節點和got的第二個字母相同（o=o） 3. 因此pointer再往下，來到o節點，發現o節點和got的第三個字母不同，而且 **t>o** 4. 因此o節點 **右子樹** 成為t，到這邊我成功將got放入原本的TST中，如下圖 ::: ``` g | o | o— | | d t ``` :::info 接著我們嘗試插入單字goal 1. 我們先比對g，發現根節點和goal的第一個字母相同（g=g） 2. 因此pointer往下，來到o節點，發現o節點和got的第二個字母相同（o=o） 3. 因此pointer再往下，來到o節點，發現o節點和goal的第三個字母不同，而且 **a<o** 4. 因此o節點 **左子樹** 成為a，到這邊我成功將goal放入原本的TST中，如下圖 ::: ``` g | o | —o— | | | a d t | t ``` :::info | Key | Value | | ------ | ------| | sur | 0 | | by | 4 | | shore | 7 | | the | 8 | | she | 10 | | sells | 11 | | are | 12 | | surely | 13 | | sea | 14 | | shells | 15 | 以下圖片示範TST ::: ![](https://i.imgur.com/DMPBCZm.png) 資料來源：http://algs4.cs.princeton.edu/lectures/52Tries.pdf ,p24 我們可以從TST結構中，發現以下幾點事情 :::warning 1. 解決trie中，pointer大量佔用記憶體的情況，因為TST中，每個節點最多只會有3個child 2. 但是換取空間的同時，犧牲了些許時間，例如上途中尋找are的過程，a就必須經過兩次比較（a<s和a<b），但再trie中只需要一次比較 3. 在上面建構的過程中，我們可以發現字串的插入順序會影響TST的整體結構，假設我們第一個插入的字串為abandon，那麼我們可以預期的事，未來所有插入的字串都會在根節點的右子樹底下，如此一來對於查詢的時間成本會增加許多。 4. 對應上述問的的解決方法，我們可以先將預插入的數據做排序，從中間值開始插入，並不斷左右折半插入，如此依來我們就可以產生一個平衡的TST ::: ### 原始程式碼分析 * make完後，執行程式，不難發現d的用途是刪除某一子節點 * a的用途是新增一子節點 :::success source code 的繁體中文翻譯為「原始程式碼」，有時會簡稱「源碼」(但不是「原」碼) :notes: jserv 已修正 by :twngbm ::: - 參考[tina0405](https://hackmd.io/JwDhDMAYHYGMBYC0sDMliPgNgIa0QEbgBMKiWkWF4KWArBQIxA==#)的修改方式 * 首先發現所有FIXME的地方，都是以CPY來傳入參數，但是我們希望以REF的方式去實作 ```c= - tst_ins_del(&root, &p, INS, CPY) + tst_ins_del(&root, &p, INS, REF) ``` 改完後直接執行可以發現，S模式下，輸入的搜尋字串會一直重複。 進入函數tst_ins_del去觀察 ```c=274 if (*p++ == 0) { const char *eqdata = strdup(*s); if (cpy) { /* allocate storage for 's' */ if (!eqdata) return NULL; curr->eqkid = (tst_node *) eqdata; return (void *) eqdata; } else { /* save pointer to 's' (allocated elsewhere) */ curr->eqkid = (tst_node *) *s; return (void *) *s; } } ``` 發現傳入的REF=0，會進入281行執行，但是傳入的*s是單一個空間，因此會產生同一個空間一直重複的問題。 #### MakeFile 修改與argc,argv的用法 #### 修改方法1-增加array * 新增一新的二元array，來儲存所有產生的節點資訊 * 採用較小的dataset（3000筆）來實驗 ```c= char tree[9000][WRDMAX]; while ((rtn = fscanf(fp, "%s", count)) != EOF) { char *p = tree[count++]; ``` 傳入array後發現可以正確執行。 ### Reference * http://algs4.cs.princeton.edu/lectures/52Tries.pdf (搭配以下影片) * https://www.youtube.com/watch?v=LelV-kkYMIg * http://www.cnblogs.com/huangxincheng/archive/2012/11/25/2788268.html