双数组trie原理
這個算法的本質就是將Trie樹結構簡化為兩個線性數組，如圖2所示。
base數組和數組中的元素是一一對應的，base數組中的每一個元素相當于Trie樹的一個節點，其值做狀態轉移的基值，check值相當于校驗值，用于檢查該狀態是否存在。對于從狀態
s到狀態t的一個轉移，必須滿足如下兩個條件:
1.base[s]+c=t
2.check[ t] =s
其中c是輸入變量。
數組構造完成之后，要查找一個關鍵碼Ab是很快，只需要一步加法，即只需判斷check[base[A]+b]是否等于A.狀態A有個基值，為base[A],則Ab所在的節點應該為基值+輸入狀態，即base[A]+b,可以這么認為，Ab的節點為base[A]+b,同樣這個節點也存在相應的基值。
同理要查找abc是否在詞典中，只需判斷check[base[base[a]+b]+c]是否等于base[a]+b
雙數組trie樹的構造過程，稍微麻煩點，詳細請參考：http://linux.thai.net/~thep/datrie/datrie.html
假設這樣一個場景，ab,ac,ae已經放入trie中，這時要插入ad, base[ base[a]+d ] !=0,說明ad節點的位置已經被其他的詞占了，譬如是ec。這個時候要調整a的基值，即base[a].如果要調節base[a]就要考慮到，ab,ac,ae的值要改變，同時abe的值也會改變。算法如下：
其中，s就是例子中的a,本來base[a]=t,但是插入ad時，位置已經被其他詞占了，譬如ec,所以這時要調整base[a]的值，調整為base[a] = b,至于b是如果得到的，請繼續研究。。。。
因為現在base[s]=b,所以詞sb,sc,se所對應的節點下標要改變，如行2所示；本來sb,sc,se對應的下標，即節點為base[s]+b,base[s]+c,base[s]+e,現在要改為b+b,b+c,b+e
因為sb,se,sc移到了新位置，所以check要更新，如行1所示；指示sb,sc,se的新節點為b+b,b+c,b+e，但是他們的上一個節點還是s
改變sc的值，那scd的節點也要變化，要主要到scd的節點對應的下標沒有變化，base[base[s]+c] +d ,雖然s的基值變為了b，但是sc的基值還是不變，但是ac的下表變了，所以要更新acd上一個狀態對應的下標，只要更新check[base[ base[s]+c]+d],使其指向下標b+c；如行3 所示
Procedure Relocate(s : state; b : base_index)
{ Move base for state s to a new place beginning at b }
begin
? ? foreach input character c for the state s
? ? { i.e. foreach c such that check[base[s] + c]] = s }
? ? begin
? ? ? ? check[b + c] := s; ? ? { mark owner }//1
? ? ? ? base[b + c] := base[base[s] + c]; ? ? { copy data }//2
? ? ? ? { the node base[s] + c is to be moved to b + c;
? ? ? ? ? Hence, for any i for which check[i] = base[s] + c, update check[i] to b + c }
? ? ? ? foreach input character d for the node base[s] + c
? ? ? ? begin
? ? ? ? ? ? check[base[base[s] + c] + d] := b + c//3
? ? ? ? end;
? ? ? ? check[base[s] + c] := none ? ? { free the cell }
? ? end;
? ? base[s] := b
end
從圖中可以看出，下標s的基值變為b,即虛線所指
對應sc的下標從t變為t',要更新check[t'] = s,check[u] = t'
//
筆試題：
請設計一個字典。以字符串為索引，存儲用戶定義的定長結構。要求有增、刪、查、改的功能。已經給定一個函數，可以由字符串映射到一個簽名，每個簽名由兩個unsigned int類型組成。假設每一個字符串能夠對應唯一的一個簽名，完全沒有重復（或者重復的概率可以忽略），并且簽名分布足夠均勻。
最直接的想法就是構造一個兩層的trie樹
還可以用hash來做，用第一個unsigned int作為hash的key，將key相等的詞的第二個unsigned int安裝順序排序，這樣可以用二分查找法查找
map<int, map<int, data>>
總結
