prefix-search

contributed by < workat60474 >

系統環境

Ubuntu 16.04.2
 Linux version 4.8.0-36-generic

 gcc version 5.4.0 20160609 (Ubuntu 5.4.0-6ubuntu1~16.04.4)
* Architecture:          x86_64
* CPU 作業模式：    32-bit, 64-bit
* Byte Order:            Little Endian
* CPU(s):                4
* On-line CPU(s) list:   0-3
* 每核心執行緒數：2
* 每通訊端核心數：2
* Socket(s):             1
* NUMA 節點：         1
* 供應商識別號：  GenuineIntel
* CPU 家族：          6
* 型號：              61
* Model name:            Intel(R) Core(TM) i5-5257U CPU @ 2.70GHz
* 製程：              4
* CPU MHz：             1008.544
* CPU max MHz:           3100.0000
* CPU min MHz:           500.0000
* BogoMIPS:              5400.35
* 虛擬：              VT-x
* L1d 快取：          32K
* L1i 快取：          32K
* L2 快取：           256K
* L3 快取：           3072K
* NUMA node0 CPU(s):     0-3

Trie

中文譯作字典樹，決定樹，前綴樹，是一棵 \(degree 數\geq 2\) 的樹，整顆樹分成兩種 nodes

  1. branch-node ：包含多個指標欄位。
  2. element-node ：只有一個資料欄位。
    而在每一個階層 (level) 中 ，進行branch所根據的是鍵值（key-value)的一部份，而不是整個鍵值。
    在下圖中，具有底色的node代表的就是指 element-node ，而其他的node則代表 branch-node 。

    而進行branch所依據的“鍵值的一部份“，更精確的說，是一個sample(抽樣) funtion，假設鍵值為\(X=x_1x_2...x_n\)而且我們每次都以鍵值的 prefix 作為跳躍的依據。
    那麼其對應的sample funtion即為 ： sample(X,i)=X的第i個字元。

而sample funtion 的優劣表現在於使用該 sample funtion所建造出的Trie之level數目，level數目越少，代表search時間越短。

通常在Trie中，會在一個 element node的鍵值結尾補上一個特殊字元（通常是選擇空白字元），這麼做的目的是希望可以避免有任何一個鍵值是其他鍵值的prefix。

trie的高度：在最差的狀況下，從樹根到element node的這段路徑上都有一個branch node包含鍵值的每一個字元，因此一棵trie的高度最多是\(number of digit +1\) 。

trie的空間浪費
值得注意的是以本次作業為例，因為城市名稱是以英文呈現，這代表基數 (radix)為 26 ，所以會需要26個 child 欄位（a-z) ，這樣的資料結構雖然使得搜尋的時間較低（search time ： \(O(level)\)），但是這種節點結構有空間上的浪費，因為許多child 欄位是NULL。
一棵d個字元的鍵值（城市名稱，如taipei 則 d=6 )， 所建構成基數為r（本次作業中 \(r=26\) )的trie會需要\(O(rdn)\)個child欄位，其中\(n\)代表trie中的element 個數。
在一棵有\(n\)個元素且鍵值有\(d\)個字元的trie裡，每一個element node 可以有最多\(d\)個祖先，且每一個都是一個branch node，因此branch node的個數最多有\(dn\)個。

這代表有\(1-\frac{dn}{rdn}\)比例的空間都用來存放NULL，這是空間上的浪費，也因此我們可以透過改變節點的結構，來降低空間需求，只要付出提高一些搜尋時間的代價就可以了。

Ternary Search Tree

Ternary Search Tree

  • Ternary Search Tree(以下簡稱TST)就是一種為了減少Trie所浪費的空間，改變節點結構而來的資料結構。
  • TST結合了Binary search tree在空間效率上的優勢和 Trie 在搜尋效率上的優勢。
  • TST 的每個node都具有3個child nodes pointers指向下面的child node。
    舉這次作業的例子：







typedef struct tst_node {
    char key;               /* char key for node (null for node with string) */
    unsigned refcnt;        /* refcnt tracks occurrence of word (for delete) */
    struct tst_node *lokid; /* ternary low child pointer */
    struct tst_node *eqkid; /* ternary equal child pointer */
    struct tst_node *hikid; /* ternary high child pointer */
} tst_node;

翻閱了資料結構聖經本，發現沒有提到ternary search tree，對於TST的細節，我參考了這篇網站：
https://www.cs.upc.edu/~ps/downloads/tst/tst.html
搭配

Select a repo