雙數組Trie樹 Double-arrayTrie

Tire 樹結構存在較大的資料稀疏，造成了空間浪費。Double-array結合了array查詢效率高、list節省空間的優點，可以有效降低空間浪費，具體是通過兩個數組base、check來實作。Trie樹可以等同于一個自動機，狀态為樹節點的編号，邊為字元。

• base數組中每個元素對應trie中的一個節點即狀态；
• check數組表示的事某個狀态的前驅狀态，用來驗證轉移的有效性；
• 兩個數組滿足如下轉移方程：

  base[s] + c = t

  [1]

  check[t] = s

  [2]

  s 是目前狀态下标 c 是輸入字元的數值（或編碼）。

double array trie 在構造時 base 數組中的值如何确定：

1. 首先預處理需要構造的檔案，将首字相同的詞條排列在一起，首字不同的詞條按照首字詞條數兩由大到小排列，首字相同的按照次字 UTF 編碼有小到大排序，依次類推，形成有序的詞條集合。 比如：“lie”、“人民”、“浙江”、“民生”，“like” ，排序後為：

   lie、like、人民、民生、浙江

   。

'浙'.encode('utf-8') > '民'.encode('utf-8') > '人'.encode('utf-8')
True
           

在構造英文或中英文混合Double-array Trie 時英文可以使用 ACSII編碼，如果以中文 UTF 編碼作為輸入數值的話，會造成樹嚴重的稀疏；中文

‘人’.encode('utf-8')

輸出

b'\xe4\xba\xba'

數值比較大，是以要對其進行重新編碼：比如說所有字元從數字

1

開始遞增編碼；

就拿上面排序好的詞條：

lie、like、人民、民生、浙江

----->>

l -- 1, 人 -- 2, 民 -- 2, 浙 -- 4, i -- 5, 生 -- 6, 江 -- 7, e -- 8, k -- 9

。

構造 Double-array Trie字典時，初始化數組為0；根節點對應于0位置并且base和check都為0：

• 首先确定所有詞條深度為1（首字，‘中國’中深度1，國深度為2）的字元對應位置的base值；
• 确定base值時要確定其後深度為2的字元都能存入數組；
• 然後根據深度2的字元的編碼來确定其對應的位置以及check值；
• 以此類推确定2層base值，直至字元結束。

對上面已将編碼的詞條來确定其base和check值：

• 确定四個首字元的對應的位置：

  根據上面狀态轉移公式 [1] 可以得出：

  base[0] + code[l] = 0 + 1

  、

  base[0] + code[人] = 0 + 2 = 2

  、

  base[0] + code[民] = 0 + 3 = 3

  、

  base[0] + code[浙] = 0 + 4 = 4

  ， 根據狀态轉移公式 [2] 可以得出：

  check[1] = check[2] = check[3] = check[4] = 0

s&t	1	2	3	4
base
check
l	人	民	浙

• 有了開頭我們繼續确定接下來的 base 和 check：

  • base[l] + code[i] = x + 5

    ，

    check[x + 5] = x

    ,，取

    x=1

    ，那麼

    base[l] = 1

    ，

    check[1 + 5] = 1

    ;

s&t	1	2	3	4	5	6
base	1
check	1
l	人	民	浙	li

• • base[人] + code[民] = x + 3

    ，

    check[x + 3] = x

    ，check 位置0、1、2、3、4、6已經被用，那麼x可以取

    x = 2

    ，那麼

    base[人] = 2 (base[2] = 2)

    ，

    check[2 + 3] = 2

    ，此時

    人民

    已經組成了一個詞條并且不是其他詞條的字首（在目前上下文中）， 是以

    base[5] = -5

    ;

s&t	1	2	3	4	5	6
base	1	2	-5
check	2	1
l	人	民	浙	人民	li

• • base[民] + code[生] = x + 6

    ，

    check[x + 6] = x

    ， 可以取

    x = 1

    , 那麼

    base[民] = 1

    ，

    check[1 + 6] = 3

    ，注意

    民生

    已經是一個詞條了，并且不是其他詞條的字首，是以

    base[7] = -7

    ；

s&t	1	2	3	4	5	6	7
base	1	2	1	-5	-7
check	2	1	3
l	人	民	浙	人民	li	民生

• • base[浙] + code[江] = x + 7

    ，

    check[x + 7] = x

    ， 可以取

    x = 1

    , 那麼

    base[浙] = 1

    ，

    check[1 + 7] = 4

    ，注意

    浙江

    已經是一個詞條了，并且不是其他詞條的字首，是以

    base[8] = -8

    ；

s&t	1	2	3	4	5	6	7	8
base	1	2	1	1	-5	-7	-8
check	2	1	3	4
l	人	民	浙	人民	li	民生	浙江

• • base[i] + code[e] = x + 8

    ，

    check[x + 8] = x

    ， 可以取

    x = 1

    , 那麼

    base[i] = 1

    ，

    check[1 + 9] = 6

    ，注意

    lie

    已經是一個詞條了，并且不是其他詞條的字首，是以

    base[9] = -9

    ；

s&t	1	2	3	4	5	6	7	8	9
base	1	2	1	1	-5	1	-7	-8	-9
check	2	1	3	4	6
l	人	民	浙	人民	li	民生	浙江	lie

• • base[i] + code[k] = 1 + 9

    ，

    check[1 + 9] = 6

    ，這裡base[i] 已知了；

s&t	1	2	3	4	5	6	7	8	9	10
base	1	2	1	1	-5	1	-7	-8	-9
check	2	1	3	4	6	6
l	人	民	浙	人民	li	民生	浙江	lie	lik

• • base[k] + code[e] = x + 8

    ，

    check[x + 8] = x

    ，取

    x = 3

    ，那麼

    check[3 + 8] = 10

    ， 注意

    like

    已經是一個詞條了，并且不是其他詞條的字首，是以

    base[11] = -11

    ；

最終：

s&t	1	2	3	4	5	6	7	8	9	10	11
base	1	2	1	1	-5	1	-7	-8	-9	3	-11
check	2	1	3	4	6	6	10
l	人	民	浙	人民	li	民生	浙江	lie	lik	like

查找“人民”這個詞為例：

狀态轉移公式：

base[s] + c = t

[1]

check[t] = s

[2]

t1 = base[0] + code[人] = 0 + 2 = 2

check[2] = 0

并且

base[2] !< 0

，繼續往下找；

base[2] + code[民] = 2 + 3 = 5

,

check[5] = 2

并且

base[5] < 0

，是以

人民

這個詞在Double-array Trie樹中；

并且

base[5] = -5

說明樹中沒有以

人民

為字首的詞，如果來查找

人民大會堂

就會查找失敗；

參考文獻

[1] 戴耿毅、佘靜濤，基于雙數組Ｔｒｉｅ樹算法的字典改進和實作 2012