2017q3 Homework2 (prefix-search)

contributed by < twngbm >

Ternary search tree 介紹

• 三元搜尋樹是一種字典樹（trie），以下將講解何為字典樹。

Trie

• Trie 樹是一種利用字串特性來實現的資料結構，英文的每一個單字，有可能會有同樣的前綴，例如apple 和 append 的共同前綴就是 app ，我們可以利用此一特行，來節省儲存空間和加速搜尋時間，也因為此依特性 trie 特別適用於處理大量字串的資料結構時。
• 以下範例示範建構依 Trie 樹，並在樹中插入子節點

首先創造一根節點，根節點必為空

@

我們試著插入單字and

1. 首先我們先把and拆分成 a, n ,d
2. 因為前綴a為第一次出現，因此我們在根節點底下創造一新子節點，節點值為a
3. 接下來從這個節點（a）出發，我們剩下 n, d
4. n也是第一次出現，因此我們在a節點下創造一新的n節點，d節點依此累推

      @
     /
    a
   /
  n
 /
d

再來我們試著插入單字 at

1. 單字拆解成 a,t，從根節點出發
2. a節點以存在，因此不再創造新的節點
3. a節點以下t 節點不存在，因此創造一新的節點t

      @
     /
    a
   / \
  n   t
 /
d

中英文間請以空白隔開課程助教

以下示範插入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

從以上的結構，我們可以發現以下幾點事情。

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

首先我們插入一值good，value=0，我們先拆分成g，o，o，d
基本概念跟trie一樣，但是這邊我們將 g 放入根節點

g
|
o
|
o
|
d

接著我們嘗試插入單字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

接著我們嘗試插入單字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

Key	Value
sur	0
by	4
shore	7
the	8
she	10
sells	11
are	12
surely	13
sea	14
shells	15

以下圖片示範TST

資料來源：http://algs4.cs.princeton.edu/lectures/52Tries.pdf ,p24
我們可以從TST結構中，發現以下幾點事情

1. 解決trie中，pointer大量佔用記憶體的情況，因為TST中，每個節點最多只會有3個child
2. 但是換取空間的同時，犧牲了些許時間，例如上途中尋找are的過程，a就必須經過兩次比較（a<s和a<b），但再trie中只需要一次比較
3. 在上面建構的過程中，我們可以發現字串的插入順序會影響TST的整體結構，假設我們第一個插入的字串為abandon，那麼我們可以預期的事，未來所有插入的字串都會在根節點的右子樹底下，如此一來對於查詢的時間成本會增加許多。
4. 對應上述問的的解決方法，我們可以先將預插入的數據做排序，從中間值開始插入，並不斷左右折半插入，如此依來我們就可以產生一個平衡的TST

原始程式碼分析

• make完後，執行程式，不難發現d的用途是刪除某一子節點
• a的用途是新增一子節點

source code 的繁體中文翻譯為「原始程式碼」，有時會簡稱「源碼」(但不是「原」碼)

jserv

已修正
by :twngbm

• 參考tina0405的修改方式

• 首先發現所有FIXME的地方，都是以CPY來傳入參數，但是我們希望以REF的方式去實作

- tst_ins_del(&root, &p, INS, CPY)
+ tst_ins_del(&root, &p, INS, REF)

改完後直接執行可以發現，S模式下，輸入的搜尋字串會一直重複。
進入函數tst_ins_del去觀察

 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筆）來實驗

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