trie 介紹

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

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

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

1. 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), 因此若搜尋筆數不多,可能使用其他方法更有效率

2. 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)

reference:
1. https://www.coursera.org/learn/gaoji-shuju-jiegou/lecture/1s2Nc/trie-shu
2. http://algs4.cs.princeton.edu/lectures/52Tries.pdf