# prefix-search
contributed by < `e94046165` >
## 系統環境
```
Architecture: x86_64
CPU 作業模式： 32-bit, 64-bit
Byte Order: Little Endian
CPU(s): 8
On-line CPU(s) list: 0-7
每核心執行緒數：2
每通訊端核心數：4
Socket(s): 1
NUMA 節點： 1
供應商識別號： GenuineIntel
CPU 家族： 6child nodes
型號： 60
Model name: Intel(R) Core(TM) i7-4720HQ CPU @ 2.60GHz
製程： 3
CPU MHz： 2594.026
CPU max MHz: 3600.0000
CPU min MHz: 800.0000
BogoMIPS: 5188.05
虛擬： VT-x
L1d 快取： 32K
L1i 快取： 32K
L2 快取： 256K
L3 快取： 6144K
NUMA node0 CPU(s): 0-7
```
## Trie（字典樹）
在實作 Prefix-search 的時候，當然不能不提到 trie 這樣特別的樹狀資料結構。以下為 trie 的簡介：
字典樹最大的特性為"利用單字的共同前綴（common prefix）作為儲存依據"，用來減少佔用的記憶體與加快搜尋的效能。共同前綴說穿了就是數個單字"前面幾個相同的字母"，像是 CUT 與 CUTE 就有 CUT 這個共同前綴。
舉例而言，若依序輸入 CAT、CUT、CUTE、TO、B 五筆資料，則會建立如下圖的字典樹。
(圖片來源自：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;
root
2. 欲插入字串為 CAT，將 CAT 拆成 C、A、T;
3. root 沒有 value == C 的 children，
建立一個 children，value = C;移動到 C;
root
/
C
4. 因 C 沒有 value == A 的 children，
建立一個 children，value = A;移動到 A;
root
/
C
/
A
5. 因 A 沒有 value == T 的 children，
建立一個 children，value = T;移動到 T;
root
/
C
/
A
/
T
6. 欲插入字串為 CUT，將 CUT 拆成 C、U、T;
7. 在 root 找到 children C，移動到 C;
8. 因 C 沒有 value == U 的 children，
建立一個 children，value = U;移動到 U;
root
/
C
/ \
A U
/
T
9. 因 U 沒有 value == T 的 children，
建立一個 children，value = T;移動到 T;
root
/
C
/ \
A U
/ \
T T
.
.
.
```
**優點：**
trie 的優點顯而易見，即是運作速度快且容易撰寫，針對搜尋目標字串是否存在與前綴相關的議題有不錯的效果。
**缺點：**
因為每個 node 皆可能有最大分支度的 child nodes 數，因此在 node struct 宣告時必須宣告 N(最大分支度) 個指標。在多數情況下，這些指標不會被充份利用，更可能有許多空指標，勢必造成巨大的記憶體成本。
## Ternary search tree (TST)
Ternary search tree 可以解決 trie 大量無用空指標的缺點，因為每個 TST 中的節點皆只有三個子節點。分別用來儲存小於、等於、大於父節點的子節點。
部份參考自[rex662624](https://hackmd.io/K4v3wF-8SFudCT2-ckK9Hg?both)
與上例相同，依序輸入 CAT、CUT、CUTE、TO、B 五筆資料，則會建立如下圖的字典樹。
```
C C C C C
| | | | \ / | \
A ==> A ==> A ==> A T ==>B A T
| |\ |\ |\ | |\ |
T T U T U T U O T U O
| | | |
T T T T
| | |
E E E
```
[ternary search tree](https://www.cs.usfca.edu/~galles/visualization/TST.html) 提供視覺化的種樹(?)過程，不想手畫的話可以用。
TST 與 trie 的差異在於：
1. 移除空的 root
2. 當輸入的字串與已有的前綴分歧時，依小於、等於、大於，插入到該節點之下。
如上圖所示，當字典樹只有 CAT 時，插入 CUTE 之動作如下
比對第一個字 C 與 root(節點C)值相同(C == C)，向下移動到 A
==> U > A，且 A 的右(大於)子節點為空，令 A 的 right child = U
==> 接著在 U 底下接入 T、E 完成插入
與 trie 相比省下不少維護子節點指標的空間，但樹的高度隨之增加，代表 search 時須花費更多時間。
此外，TST 還有一個隱含的問題： **樹的形狀受插入順序影響**
若插入順序為 CAT、CUT、CUTE、TO、B 則建立樹如左圖
但順序改成 TO、CAT、CUT、CUTE、B 則會如右圖
可以看到各字串的深度會跟著樹的形狀改變，在極端情況如將所有的字串由小而大輸入，則 TST 會有相當差的效能。
:::info
TODO： 在輸入字串固定的情況下，如何安排輸入順序使得樹的平均深度(不確定這個詞是否正確，僅用來表示所有 nodes 的3個子節點都被儘量填滿的情況)最小，應該是值得討論的議題。
:::
## 程式碼理解&測試
在讀了 [rex662624](https://hackmd.io/s/SJbHD5sYM) 和 [tina0405](https://hackmd.io/s/SkEFpwh2-#) 後，大致理解了程式碼中未完善的地方，也就不用對整個程式碼進行地毯式的探索。需修改的點大概有以下幾個：
1. 在 test_ref.c line 55 最後一個係數由 CPY 改成 REF
```C
if (!tst_ins_del(&root, &p, INS, CPY))
if (!tst_ins_del(&root, &p, INS, REF))
```
2. 接著到 tst.c 中觀察 tst_ins_del() 中與更改的參數相關的程式碼：
發現 tst_ins_del() 只有在 for (;;) 中的 if(cpy) 與更動 CPY-->REF 有關
```C
if (cpy) { /* allocate storage for 's' */
const char *eqdata = strdup(*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;
}
```
當參數為 CPY 時，cpy == 1，由註解可以看猜出接下來要做的動作是為新加入的字串 allocate storage，實作則用 strdup()實現。strdup() 在 string.h 中被宣告。可以看到，strdup 其實就是把傳入的字串保存到一個未被使用的、新分配的記憶體空間。
```C
char * __strdup (const char *s){
size_t len =strlen (s) + 1;
void *new =malloc (len);
if (new == NULL)
return NULL;
return (char *)memcpy (new, s, len);
}
```
3. 當把參數由 CPY 改為 REF(cpy != 1) ，也就沒有為 pointer 分配空間，測試後果然與前人發生了一樣的問題：
```
choice: s
find words matching prefix (at least 1 char): Ta
Ta - searched prefix in 0.000166 sec
suggest[0] : Ta
suggest[1] : Ta
suggest[2] : Ta
suggest[3] : Ta
suggest[4] : Ta
suggest[5] : Ta
suggest[6] : Ta
suggest[7] : Ta
suggest[8] : Ta
suggest[9] : Ta
suggest[10] : Ta
suggest[11] : Ta
suggest[12] : Ta
suggest[13] : Ta
suggest[14] : Ta
suggest[15] : Ta
suggest[16] : Ta
```
4. 首先，一樣照著在別人共筆中讀到的方法，以 array 保存字串，並且減少輸入的資料來避開 core dumped
```C
int q = 0;
char word2[20000][WRDMAX];
while ((rtn = fscanf(fp, "%s", word2[q])) != EOF) {
char *p = word2[q];
q++;
/* FIXME: insert reference to each string */
if (!tst_ins_del(&root, &p, INS, REF)) {
fprintf(stderr, "error: memory exhausted, tst_insert.\n");
fclose(fp);
return 1;
}
idx++;
}
```
```
choice: s
find words matching prefix (at least 1 char): Ta
Ta - searched prefix in 0.000190 sec
suggest[0] : Ta‘izz,
suggest[1] : Ta’if,
suggest[2] : Tabūk,
suggest[3] : Tabasco,
suggest[4] : Taboão
suggest[5] : Tabora,
suggest[6] : Tabrīz,
suggest[7] : Tachikawa,
suggest[8] : Tacna,
suggest[9] : Tacoma,
suggest[10] : Taegu,
suggest[11] : Taganrog,
suggest[12] : Tagbilaran,
suggest[13] : Tagil,
suggest[14] : Tagiura,
suggest[15] : Tahoua,
suggest[16] : Tahta,
suggest[17] : Tai’an,
suggest[18] : Taicheng,
suggest[19] : Taichung,
suggest[20] : Taiden,
suggest[21] : Tainan,
suggest[22] : Taipei,
suggest[23] : Taiping,
suggest[24] : Taitung
....
```
至此可以看到 search words matching prefix 的功能可以正常運作了。稍後再試著解決 array 不能宣告太大的問題。
```C
char word2[300000][WRDMAX];
```
其實只要把這行 array 宣告放到 main 以外(作為 Global varible)，這麼一來就不會 core dumped 了。[參考資料](http://iamcgod.blogspot.tw/2016/12/globalstackheap.html)
**三種記憶體區間:global,stack,heap**
●global：
存放
全域變數(global variable)
靜態變數(static variable)
●stack：
存放
區域變數(local variable)
函式參數(function/method parameter)
函數的返回位址(function/method return address)
●heap：
通常是給動態記憶配置(dynamic memory allocation)使用，需要 programmer 自己申請，並指明大小，在 c 中 malloc 函數
4. 接著再往下測試，發現 delete 與 quit 無法正常運作。因此察看相對應的函式：
**quit :**
原來是 call tst_free_all(root):
```C
/** free the ternary search tree rooted at p, data storage internal. */
void tst_free_all(tst_node *p)
{
if (!p)
return;
tst_free_all(p->lokid);
if (p->key)
tst_free_all(p->eqkid);
tst_free_all(p->hikid);
if (!p->key)
free(p->eqkid);
free(p);
}
```
改為 tst_free(root):
```C
/** free the ternary search tree rooted at p, data storage external. */
void tst_free(tst_node *p)
{
if (!p)
return;
tst_free(p->lokid);
if (p->key)
tst_free(p->eqkid);
tst_free(p->hikid);
free(p);
}
```
這樣就不會 free 失敗了耶嘿~
**delete :**
更改 tst_ins_del() 中 :
`return tst_del_word(root, curr, &stk, 1);`
的最後一個參數改為 cpy，這樣就可以順利 delete 了，這裡還有一個小細節要注意：data 中 城市名後面的 "," 在 fscanf 時也被讀進去了，所以如果想 find 或 delete Tainan 是會失敗的，必須 find/delete Tainan, 才行。
## 效能分析
Sign in with Wallet
Connect another wallet