prefix-search

contributed by <codecrazer>

TST原理

trie 介紹

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

同步發表於個人部落格

trie 是一種樹狀的數據結構,用來儲存大量字串,每個節點由個一個字組成,先創原點,再將單字逐個加入,若遇到之前沒有的,則加入那個分枝

其主要應用領域在 bioinformatics,information retrieval

trie 可分為好幾種,以下由我一一道來

26 way trie: 一個節點有26個分支,主要用在英文單字的儲存,圖解如下=>

假設有aaa,aab,efg三個單字,先創原點,用＠表示

        先加入aaa                再加入aab           最後加入efg
        @                                   @                       @
       /                                  /                       / \
     a                                  a                        a   e
    /        =>                        /              =>        /    \
   a                                  a                        a     f
  /                                 / \                       / \     \
 a                                 a   b                     a  b     g

須注意每個節點需用一個變數來表示是否為終點,比如說上圖我們搜尋aa,也能找到,但是aa實際上不存在於我們的資料中;此外,每新增一個節點,其實我們需要新增26個指標,來指向NULL

來看trie的複雜度,假設有n個字串,字串長度最長為L,建立trie所需複雜度為O(n*L),insert的複雜度為O(L),search的複雜度亦為O(L),非常的快,且能支援prefix search, 意思為輸入前綴,有相同前綴的單字都會跑出來, 舉例來說,輸入pet,可能會跑出peter,petty之類的

另一種分析複雜度的方法,假設全部的字數為N,理想狀態下,若字串長度差不多,則insert,search,delete的complexity皆為O(log N),因為高度為log N

缺點: space complexity實在太大太大, 需要27*N(reference), 因此若搜尋筆數不多,可能使用其他方法更有效率

Ternary search tries(TST):

和上面的trie類似, 也是每個節點儲存一個字以及變數,但不同的是每個節點只有三個子節點,分別是左邊接值小(表示字串開始的值比目前節點小),值相等往下方走,右方值大(表示字串開始的值比目前節點大)

TST insert, 圖解=>

  先加入aaa                再加入dcb                       再加入ef
                            (d比a大,所以接右邊)        (e比a大,往下再比,又比d大,所以接右邊)                  
   a                                       a                       a     
   |                                 =>    |\              =>      |\      
   a                                       a d                     a d        
   |                                       | |                     | | \       
   a                                       a c                     a c  e       
                                             |                       |  |
                                             b                       b  f

其實訣竅很簡單, 就是比大小XD,遇到值大右走,值小左走,值相等往下

有一點很值得提的,就是TST是由Robert Sedgewick和Jon L. Bentley在1990年代提出,
其中Robert Sedgewick 就是參考資料2的作者

複雜度分析,其實很明顯可以看出time complexity 比26-way多, 但是 space complexity 少非常多
分析如下,search 和 insert 都變成 O(L+logN),其中L是字串長度,N是總字數,原因很簡單,因為原本字串
長度就是L, logN代表最多能被多接幾個; 至於空間複雜度很簡單,就是4N(reference)