Try   HackMD

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

與上例相同，依序輸入 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 提供視覺化的種樹(?)過程，不想手畫的話可以用。
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 會有相當差的效能。

TODO： 在輸入字串固定的情況下，如何安排輸入順序使得樹的平均深度(不確定這個詞是否正確，僅用來表示所有 nodes 的3個子節點都被儘量填滿的情況)最小，應該是值得討論的議題。

程式碼理解&測試

在讀了 rex662624 和 tina0405 後，大致理解了程式碼中未完善的地方，也就不用對整個程式碼進行地毯式的探索。需修改的點大概有以下幾個：

  1. 在 test_ref.c line 55 最後一個係數由 CPY 改成 REF
if (!tst_ins_del(&root, &p, INS, CPY))
if (!tst_ins_del(&root, &p, INS, REF))
  1. 接著到 tst.c 中觀察 tst_ins_del() 中與更改的參數相關的程式碼：
    發現 tst_ins_del() 只有在 for (;;) 中的 if(cpy) 與更動 CPY–>REF 有關
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 其實就是把傳入的字串保存到一個未被使用的、新分配的記憶體空間。

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);
}
  1. 當把參數由 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
  1. 首先，一樣照著在別人共筆中讀到的方法，以 array 保存字串，並且減少輸入的資料來避開 core dumped
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 不能宣告太大的問題。

char word2[300000][WRDMAX];

其實只要把這行 array 宣告放到 main 以外(作為 Global varible)，這麼一來就不會 core dumped 了。參考資料
三種記憶體區間: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 函數

  1. 接著再往下測試，發現 delete 與 quit 無法正常運作。因此察看相對應的函式：
    quit :
    原來是 call tst_free_all(root):
/** 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):

/** 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, 才行。

效能分析

Last changed by 
 
Lai Dong
0
602
Published on HackMD