雙數組字典樹(Double Array Trie)
參考文獻
3.論文《基於雙數組Trie樹演算法的字典改進和實現》
DAT的基本內容介紹這裡就不展開說了，從Trie過來的同學應該比較熟悉，Trie對記憶體的消耗比較大，DAT正是為了優化該問題而提出。此文重點說一下如何去理解DAT的base數組和check數組，希望能給諸位些幫助，DAT中定義base數組、check數組滿足的條件為：
base[s] + c = t
check[t] = s
這裡s指轉移前的狀態，c指字元的編碼，t指轉移後的狀態，下面逐個理解這兩個公式表示的邏輯。
1. base[s] + c = t
理解這個式子時，不能單純的從數組取值上去理解，比如直接將s當成base數組的下標，因為 s 和 t 都是狀態，而 c 是字元編碼，此時就會疑惑，為啥等式兩邊輸出類型都不一致呢？這到底是怎麼個計算關係？如果有類似的疑惑，那麼可以先摒棄這種的想法。
base數組維護的是Trie樹上節點的資訊，這個公式想表達的意思是：狀態 s (也就是一個節點，Trie樹上每個節點都表示一個狀態，不理解的可以先了解一下狀態機的概念)接收一個字元 c 後，就得到狀態 t ，而並不是base數組中下標為 s 處的取值加上 c值 等於 t 值,所以說不能從僅僅從數值計算上理解這個公式。那麼這個公式是如何用在DAT的創建中的呢？我們從如下幾個問題入手，來了解這個公式的作用。
1.1 s、t 具體是什麼意思？
s、t 表示DAT上的一種狀態、base數組中的元素，實際上就是Trie上的一個個節點，這個節點上包含很多資訊，創建過Trie樹的同學知道，Trie樹節點上一般包含：屬性值value(可以用來記錄詞性)、葉子節點標記flag(是否為詞語的未字元）、子節點數組(用來存儲子節點的資訊)等等
1.2 base數組中存儲的是什麼？
base數組維護的是各個狀態的資訊，即數組中存儲的是各節點的資訊，但是具體內容與1.1節中所說的Trie節點資訊不一致，以參考文獻1中實現為例，每個狀態下包含的資訊包括
transferRatio:計運算元節點在base數組中下標時的轉移基數，為了解決節點存儲位置衝突而引入的，初始值為0
isLeaf:節點是否為詞語的葉子節點。該內容可選，也可以用其它方式表示葉子節點
label:節點存儲的字元，可以理解為該節點是通過插入哪個字元得到的。該內容可選，也可以不要
value:如果該節點為葉子節點，那麼其對應的詞語在詞典中序號。該內容為可選，也可以不要
1.3 base數組的下標表示什麼意思
base數組的下標是基於字元的編碼做加減運算得到的數值。參照1.2節中的例子，創建DAT存儲詞語「中華」，先創建一個base數組，
TrieNode base[10] //假設存儲10個節點
令根節點root = new TrieNode ，很自然的將根節點root存入base[0]。令 root. transferRatio=1 (這裡設為1，也可以設個其他值，初始值隨便，保證base數組不溢出即可)
接著插入字元「中」,假如採用unicode編碼，那麼「中」的碼值為20013，那麼存儲 字元「中」的節點在base數組中的下標就為
0 + base[0].transferRatio + unicode(“中”)=0+1+20013=20014
令 base[20014].transferRatio=1 (這裡設為1主要是為了和初始時的0區分開，表示base[20014]這個位置已經有節點佔據了)
然後插入字元「華」，unicode(‘華’)=21326，因為是節點「中」接收字元「華」，存儲 字元「華」的節點在base數組中的下標就為
20014+ base[20014].transferRatio + unicode(‘華’)=20014+0+21326=41340，
令base[41340].transferRatio=1 ，原因同上。
1.4 c值怎麼計算
c值得計算除了1.3中說的計算字元得unicode值，你還可以計算字元hash值得到，只要保證每個字元(中文、英文、日文等等文字的字元)有一個唯一且確定得編碼值即可。
通過以上幾個問題的說明可知，DAT中每個狀態的下標是唯一的(解決位置衝突之後)，可以用base數組的下標表示狀態，通過索引base數組的下標即可得到各個狀態的資訊。此時，我們再來從數值計算的角度來理解這個公式，即狀態 s 的下標(還要加上偏移transferRatio)加上字元c的編碼值，等於狀態 t (由狀態s 接收字元c 得到)的下標。
2. check[t] = s
理解這個等式，先要從DAT的查詢邏輯說起。在Trie中，我們是怎麼判斷詞語存在的？從根節點開始，依次查詢詞語中的每個字元，若各個字元均存在於當前節點的子節點中，則表明該詞語存在。如果在DAT上也按照這個邏輯來判斷詞語是否存在，則查詢過程是這樣的：還是以1.3節為例，查詢詞語 「中華」 是否存在。從根節點開始，首先查詢 「中」字，
0 + base[0].transferRatio + unicode(“中”)=0+1+20013=20014
若base[20014].transferRatio ≠ 0 ，則表明字元「中」存在。(判斷base數組中一個位置上是否有數據可以採用很多方式，這裡採用參考文獻1中的實現方式，即判斷TrieNode.transferRatio是否非0)
接著查詢字元「華」，
20014+ base[20014].transferRatio + unicode(‘華’)=20014+0+21326=41340
若base[20014].transferRatio ≠ 0，則表明「華」存在。那麼這個邏輯在DAT上是否可靠呢？答案是不可靠，因為在DAT上節點轉移是通過在base數組上索引字元unicode碼值進行的，這就會存在以下的情況
unicode(A) ≠ unicode(B)
unicode(A)+unicode(C) = unicode(B)+unicode(D)
其中 A、B、C、D指unicode編碼規範中收錄的某個字元，此種情況下的查詢邏輯就會出錯，所以在DAT中引入了check數組，在check數組中保存的是當前狀態的父狀態（即當前節點的父節點），還是以1.3節中詞語「中華」為例，以base數組的下標表示狀態，字元「中」所在節點的父節點為根節點，所以check[20014]=0;字元「華」所在節點的父節點下標為20014，即check[41340]=20014，這樣可以確定當前節點的父節點是哪一個，從而解決 unicode(A)+unicode(C) = unicode(B)+unicode(D) 帶來的問題。
