字典树实现_手把手教学 | 双数组字典树

Natural language processing

an important direction in the field of 

computer science and artificial intelligence.

导读

本篇内容结合HanLP中的实现方法，通过python代码实现，对字典树数据结构进行深入学习(对字典树和AC自动机不了解的读者可以看看另一篇推文十分钟学会AC自动机)：

字典树

1.HanLP字典树结构

结构示意图：

python代码构建结构：

节点包含值和子节点两个属性，存在值的节点表示某个词语尾节点，子节点为字典结构：

2.HanLP字典树python实现

节点：

字典树：

判断是否包含：

获取指定子节点：

设置节点：

3.首字散列其余二分的字典树

结构示意图：

python代码构建结构：

4.python实现首字散列其余二分的字典树

由于python中不存在字符类型，字符串的hash算法在64位系统上，位数为64位整数，但Unicode字符总共才136690个，参考HanLP中java实现，用java中字符的散列函数，输出的区间为[0,65535]内的整数，因此将hash后的值截取到5位长度：

定义节点：

子节点的添加方法：

子节点的查询方法：

实现二分查询：

定义字典树BinTrie：

字典树的增加方法：

字典树的查询方法：

简单运行：

结果：

并且HanLP作者何晗已经验证了该数据结构进行最长匹配方法的中文分词，万字/秒比普通trie树有所提升(如逆向匹配算法，从原135万字/秒提升到了210万字/秒)。

5.首字散列其余二分的字典树的优化使用

其实，对于扫描"自然语言处理"该句分词时，原方法用_contains_方法是依次查找"自"、"自然"、"自然语"、"自然语言"等词语是否在词典中。然而，若"自然"不存在，则以"自然"开头的词语也都不存在了。因此考虑用该方式优化分词：当状态转移失败时，则提前终止扫描，进而节省时间。

HanLP作者何晗验证了该方式进行最长匹配方法的中文分词，万字/秒比普通方法有大幅提升(如正向匹配算法，从原213万字/秒提升到了1176万字/秒，比最初的64万字/秒提高了2个数量级)。

6.双数组字典树

核心思想：

由base和check两个数组构成(base和check的索引表示一个状态)，缩短状态转移过程的时间。

具体的，当状态b接受字符c转移到状态p时，满足条件(状态由整数下标表示)：

state[p] = base[state[b]] + index[c]

check[state[p]] == state[b]

若条件不满足则转换失败。

如：当前状态自然(例如state[自然]=1),若想判断是否可以转移到状态自然人，先执行state[自然人] = base[state[自然]] + index[人] = base[1] + index[人],然后判断check[state[自然人]] == state[自然]是否成立即可，仅需一次加法和整数比较就能进行状态转移，转移过程为常数事件。

base和check构建过程*：

假设有一个字符集仅有 {a, b, c} 有单词 a, ab, bbc, bc 构建一个 DAT，首先给字符集编码 index[a] = 1; index[b] = 2; index[c] = 3;

1.构建a:

2.构建ab:

3.构建bbc:

构建b时，发现冲突：

构建bb：

构建bbc：

4.构建bc:

5.搜索bbc是否存在：

1.state[b] = base[state[null]] + index[b] = 2

检查check[state[b]] == state[null] 即 check[2] == 0为true

2.state[bb] = base[state[b]] + index[b] = 1 + 2 = 3

检查check[state[bb]] == state[b] 即 check[3] == 2为true

3.state[bbc] = base[state[bb]] + index[c] = 2 + 3 = 5

检查check[state[bbc]] == state[bb] 即 check[5] == 3为true

则字典中存在bbc

7.python实现双数组字典树

定义Node：

定义HashMap:

HashMap新增:

HashMap判断是否存在:

HashMap获取:

增强版HashMap:

定义双数组字典树：

双数组字典树构建过程：

双数组字典树判断是否存在：

HanLP作者何晗验证了双数组字典树进行最长匹配方法的中文分词，万字/秒比普通方法有大幅提升(完全切分从BinTrie的741万字/秒提升到了1606万字/秒，正向最长匹配从1176万字/秒提升到了3584万字/秒)。

PROMPT

温馨提示

作者原创 | 未经授权请勿转载