Double Array Trie

Trie結構是模式比對中經常用到的經典結構，在字元串進行中發揮着重要的作用，比如分詞算法，就會利用Trie結構将分句的已知詞條先識别出來，然後再判斷剩下的未識别部分是否是新的未知詞。

經典的Trie結構如下圖所示，

是一個典型的多叉樹結構，為了保證用Trie結構進行模式比對的效率，Trie結構的每一個節點往往會容納輸入字元集的所有字母構成的數組，以便實作高速查找，這樣的缺點就是記憶體空間的大量浪費，因為越到Trie結構的葉節點，每個節點所包含的字母數量就越少，很可能出現為了幾個字元，而多出幾十個空位的情況.如上圖，沒有一個Trie節點的元素多于3個，但是為了算法的效率，每個節點都需要預留26個空位。讀者可能會考慮對于Trie結構的每個節點，用散清單代替數組，改直接查找為散列查找，來減少空間的浪費，但是像Trie這樣的基本處理工具，每秒鐘可能需要對目标文本執行上萬次的比對操作，散列計算的開銷很可能會成為影響程式效率的瓶頸。那麼有沒有既可以充分利用節點空間，又可以避免散列計算開銷的Trie實作呢。Jun-Ichi Aoe（日本）于1989年提出的double-array結構，正是将Trie結構的高效率與空間的緊湊利用相結合的理想解決方案。

前面我們提到，可以用散清單來節省Trie結構節點的空間浪費，但是我們又不想對每一次字元查找都進行散列運算，實際上，我們使用散清單的初衷，無非也就是對于目前節點，我們去哪幾個節點去比對下一個輸入字元。這裡我們以字元集a-z為例，來考慮如何實作Trie結構的壓縮存儲。

如上圖所示，我們假設有一個很長的數組BASE[1...n]，此時對于集合K，我們可以将BASE[1...26]，作為對應的Trie結構的根節點，這樣對于第1個輸入字元，肯定可以映射到BASE[1...26]中的一個，然後我們将BASE[27...52]作為當第1個輸入字元是a時，第2個字元對應的區間。BASE[53...78]作為當第1個字元是b時，第2個字元的映射區間，依次下去，将BASE[27...702]對應Trie結構根節點26個字母所分别對應的的第2層頂點。此時我們實作了将Trie結構的各層頂點映射到一個一維數組上面。為了能夠索引到對應的BASE數組中的正确位置，我們還需要一個CHECK數組與BASE中的元素一一對應，來标記目前字元是從哪個父節點索引過來的。比如說BASE[53]的a是從BASE[2]=b索引過來的，而不是從BASE[1]或者BASE[3]索引過來的，對應于模式串字首ba，而不是aa，ca。以上圖為例，CHECK[27]到CHECK[52]的值都等于1，說明節點1是節點27-52的父節點。對于目前節點i，輸入字元c，BASE與CHECK的關系是CHECK[BASE[i]+c]=i。

下面我們來看一下如何利用這種形式的Trie結構，并根據輸入的模式集合，來充分利用記憶體空間。對于輸入集合K={baby,bachelor,back,badge,badger,badness,bcs}，我們會發現其對應的Trie結構的根節點隻有一個合法輸入b，也就是說BASE[1...26]，我們隻用到了一個節點BASE[2]，其餘25個節點都白白浪費掉了，那麼我們有沒有辦法把這些地方複用為Trie結構的2層節點呢。字母b之後的合法輸入有a，c，是以我們可以考慮找到這樣的一個位置r，使得BASE[r]+a，BASE[r]+c都是還未使用的節點，這樣我們就可以把r作為父節點b的2層子節點的索引位置，容易得到r=1，就滿足條件，是以，我們沒必要使用BASE[27...52]的空間來存放b的子節點a，c，直接使用BASE[1]，BASE[3]就可以了。此時BASE[2]=0，CHECK[1]=CHECK[3]=2。同樣，對于輸入ba其後的合法輸入有b，c，d三個，我們可以找到一個位置r令BASE[r]+b，BASE[r]+c，BASE[r]+d都為未使用節點，然後将ba之後的子節點安排在這幾個位置就可以了。r=2就滿足條件，此時BASE[1]=3，CHECK[3]=CHECK[4]=CHECK[5]=1。

下面給出對于模式集合K建構Double-Array的算法。

我們以例子來說明Double-Array的建構算法。模式集合K={baby,bachelor,back,badge,badger,badness,bcs}，輸入字元集合a-z對應數字0-25，BASE，CHECK數組均從0開始，所有單元的初始狀态都為-1。另外對于BASE數組中的值，我們需要分區使用，後面會解釋。這裡首先要說一下獨立字尾的概念，以模式集合K中的模式badness為例，其字首b，ba，bad分别都與其他模式的字首有重疊，而字首badn就是模式badness的獨有字首了，是以從n到模式末尾的整個字尾ness，就是模式badness的獨立字尾。對于模式串的獨立字尾，我們無需将其組織在Trie結構中，而專門将其甩到另外一個結構TAIL中集中管理。

 1 2 3 4 5 6 7 8 9

 b a b y

 b a c h e l o r

 b a c k 

 b a d g e

 b a d g e r

 b a d n e s s

 b c s 

現在我們分層來建構集合K的Double-Array Trie結構，首先我們考察集合的第1層（也相當于所有模式串的首字母）所構成的集合S1，我們發現S1={b}，此時我們在BASE數組中要找到這樣的位置i對于S1的所有元素s，有BASE[i+s]=-1。對于集合S1，我們發現i=0有BASE[0+1]=BASE[1]=-1就滿足條件，是以我們将CHECK[1]=-1保持不變。

接着我們來處理集合的第2層。在之後的進行中我們要注意，隻有字首相同的一組字元，我們才把他們作為一個集合來處理，相當于Trie結構的一個節點。對于本例來說，所有模式串的第1個字母都是b，我們可以得到一個集合S2={a,c}，我們需要在BASE中尋找i使得BASE[i+0]=-1，BASE[i+2]=-1，此時0滿足條件，我們對于集合S2的共同字首b，找到其在BASE中對應的位置是BASE[1],是以我們令BASE[1]=0，CHECK[0]=CHECK[2]=1。這裡對于滿足條件的i值，我們隻取滿足條件的正值，但是不一定是最小的。

再接着處理第3層，此時字首ba的直接後繼字母集合S3={b，c，d}，我們發現i=2可以滿足BASE[3]=BASE[4]=BASE[5]=-1，此時我們用字首ba找到其在BASE中的位置BASE[0]，令BASE[0]=2，同時令CHECK[3]=CHECK[4]=CHECK[5]=0。而字首bc的直接後繼字母集合S4={s}，這裡我們不會将s安置在BASE數組中，因為字首為bc的模式串隻有一個bcs，是以對于模式bcs來說，字首bc之後的部分已經形成了前面所說的獨立字尾，也就是說當比對完字首bc之後，後面的比對就由多模式比對退化為目标串的與bcs的字尾s的比對操作，此時就不需要再用Trie結構來進行查找，而直接将目标串的餘下部分與s執行比較就可以了。是以我們讓TAIL[1]="s"。

用上面的辦法逐層處理模式集合的字元，按照公共字首分組處理（例如公共字首bad的後繼集合S4={g,n}），遇到獨立字尾，就将該獨立字尾加入TAIL數組中，直到把所有模式串的獨立字尾都加入到TAIL表中為止，建構Double-Array結構完畢。這裡有一種情況需要特别關注，以模式badge和badger為例，badge是badger的包含字首，當我們建構到badge尾部的時候就會出現既要索引TAIL表中的對應獨立字尾（此時TAIL表的獨立字尾為空串，但是依然要有），以表示一個比對模式被發現。又要繼續跳轉的雙重需要，此時我們可能需要對BASE值進行分區使用來兼顧這樣的需求，比如将BASE值分為高16位和低16位，高16位用于索引TAIL數組，低16位用于實作跳轉，當BASE值大于65535時，說明目前BASE值索引到了一個比對模式的獨立字尾，将其減去65535，所剩下的就是對應的TAIL索引。AOE的論文中是在每個模式的後面加入一個不可能字元使得任何兩個模式都不存在字首包含關系，來解決這個問題的。

上面就是逐層建構Double-Array的基本步驟，用此方法建構的Double-Array結構如圖所示，由于BASE中的數值可能包含多重意思，這裡将可以直接索引的模式，直接寫在BASE的對應單元内，當比對到達這些單元時，直接将輸入的字元與字尾進行比較即可：

利用建構好的Double-Array比對指定的模式的算法步驟如下。将臨時變量r置為0，對于首位輸入字元c，我們先要判斷BASE[c]和CHECK[c]，如果BASE[c]！=-1，CHECK[c]=-1，則令r=c，繼續執行後續的比對查找。如果不比對，說明輸入字母c不是Trie結構的根節點成員，放棄之。然後我們得到t= BASE[r]+c，以及CHECK[t]，判斷CHECK[t]是否等于r，如果不相等，則說明目前Trie節點不包含輸入字母c，在模式集合中中沒有該模式，是以比對失敗，否則令r=t，再繼續執行上述操作。直到比對失敗，或者最終索引到TAIL中的比對模式為止。

用上述的方法比對模式badge的過程如下。

1）對于字母b，BASE[1]!=-1, CHECK[1]=-1，可以繼續執行比對操作, r = 1。

2）對于字母a，t=BASE[1]+a=0, CHECK[t]=CHECK[0]=1, CHECK[t]=r, r=t=0;

3）對于字母d，t=BASE[0]+d=5, CHECK[5]=0, CHECK[t]=r, r=5;

4）對于字母g，t=BASE[5]+g=6, CHECK[6]=5, CHECK[t]=r, r=6;

5）對于字母e，t=BASE[6]+e=8, CHECK[8]=badge，發現比對。

模式ada的失敗比對過程如下

1）對于字母a，BASE[0]=2!=-1,CHECK[0]=1!=-1，是以ada不是集合中的模式，比對終止。

模式baec的失敗比對過程如下

1）對于字母b，BASE[1]!=-1, CHECK[1]=-1，可以繼續執行比對操作, r = 1。

2）對于字母a，t=BASE[1]+a=0, CHECK[t]=CHECK[0]=1, CHECK[t]=r, r=t=0；

3）對于字母e，t=BASE[0]+e=6，CHECK[t]=CHECK[6]=5!=0，比對失敗，是以baec不是集合中的模式。

後記：

一般的算法或者資料結構，往往是時間和空間的某種妥協，如果要提高運作效率，往往需要一些額外的記憶體空間，反之亦然。而Double-Array之于Trie結構，就好像是一種完美的诠釋，在實作了對Trie結構空間的充分利用的同時，又不犧牲查找速度，那麼是不是Double-Array就無懈可擊了呢。當然不是。要駕馭這種優美結構的代價，就是實作Double-Array的高複雜性，以及在Double-Array中插入，修改，删除單條資料的高代價。AOE在論文中詳細介紹了Double-Array的增加，變更，删除條目的操作算法，相較于通俗的Trie實作，要複雜的多得多，本文我也僅僅是将自己對Double-Array的一點淺顯了解寫出來而已，實際上Double-Array是一個相當複雜的資料結構，他隻能在某些應用場合替代普通的Trie結構，以後如果條件允許，我還會将Double-Array的更多細節一一介紹。