雙數組壓縮樹

兩個數組 base check

• begin 偏移量

• 公式

  check[begin+code]=begin

  base[begin+code]=begin(子節點的)

  ps：每個詞語的結尾 預設是有一個字元的 這個字元code=0帶入公式如下

  check[begin]=begin

  base[begin]=index(這個詞語的id)

偏移量是不能重複的

流程示範

輸入詞

12

123

345

398

1. 建構字典樹

1. 跟節點開始 begin=base[0]=1 因為數組中還沒有元素偏移量為1,check[0]預設值是0
2. check[1+code_1]=1 check[1+code_3]=1 ,然後找1，3的偏移量，這裡假設為2
3. 為base數組指派base[2+code_1]=2 base[2+code_3]=2
4. check[2+code_2]=2
5. 找2的偏移量假設3 base[3+code_2]=3

6. 這裡需要注意 2下面有3，同時是2的結尾，結尾的code為0指派如下

   base[0+3]=index(這個index一般用負數表示) check[3+code_3]=3

7. 依次類推，即可建構

查詢過程如下

比如要找12

• root節點開始 base[0]==1得到偏移量是1
• 檢查1是否是root的子節點，如果 check[1+code_1]==1說明1是root的子節點
• 然後檢查1是否是一個詞check[1]==1&&base[1]<0 說明1就是一個詞，、
• 依次類推

ps：偏移量是不能重複的，是以建構的時候需要一個數組來維護，使用過的偏移量