双数组Trie树 Double-arrayTrie
程序员文章站
2022-04-17 21:27:42
...
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 数组中的值如何确定:
- 首先预处理需要构造的文件,将首字相同的词条排列在一起,首字不同的词条按照首字词条数两由大到小排列,首字相同的按照次字 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 | 0 | 1 | 2 | 3 | 4 |
---|---|---|---|---|---|
base | 0 | ||||
check | 0 | 0 | 0 | 0 | 0 |
l | 人 | 民 | 浙 |
- 有了开头我们继续确定接下来的 base 和 check:
-
base[l] + code[i] = x + 5
,check[x + 5] = x
,,取x=1
,那么base[l] = 1
,check[1 + 5] = 1
;
-
s&t | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|---|---|
base | 0 | 1 | |||||
check | 0 | 0 | 0 | 0 | 0 | 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 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|---|---|
base | 0 | 1 | 2 | -5 | |||
check | 0 | 0 | 0 | 0 | 0 | 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 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
---|---|---|---|---|---|---|---|---|
base | 0 | 1 | 2 | 1 | -5 | -7 | ||
check | 0 | 0 | 0 | 0 | 0 | 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 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
---|---|---|---|---|---|---|---|---|---|
base | 0 | 1 | 2 | 1 | 1 | -5 | -7 | -8 | |
check | 0 | 0 | 0 | 0 | 0 | 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 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|---|---|
base | 0 | 1 | 2 | 1 | 1 | -5 | 1 | -7 | -8 | -9 |
check | 0 | 0 | 0 | 0 | 0 | 2 | 1 | 3 | 4 | 6 |
l | 人 | 民 | 浙 | 人民 | li | 民生 | 浙江 | lie |
-
-
base[i] + code[k] = 1 + 9
,check[1 + 9] = 6
,这里base[i] 已知了;
-
s&t | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
---|---|---|---|---|---|---|---|---|---|---|---|
base | 0 | 1 | 2 | 1 | 1 | -5 | 1 | -7 | -8 | -9 | |
check | 0 | 0 | 0 | 0 | 0 | 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 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
---|---|---|---|---|---|---|---|---|---|---|---|---|
base | 0 | 1 | 2 | 1 | 1 | -5 | 1 | -7 | -8 | -9 | 3 | -11 |
check | 0 | 0 | 0 | 0 | 0 | 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] 戴耿毅、佘静涛,基于双数组Trie树算法的字典改进和实现 2012
下一篇: 叫他本人来