字典树---Python自然语言处理（3）

什么是字典树

在自然语言处理中，字符串集合常用字典树存储，这是一种字符串上的树形数据结构。字典树中每条边都对应一个字，从根节点往下的路径构成一个个字符串。

字典树并不直接在节点上存储字符串，而是将词语视作根节点到某节点之间的一条路径，并在终点节点上做个标记（表明到该节点就结束了）。

要查询一个单词，指需要顺着这条路径从根节点往下走。如果能走到标记的节点，则说明该字符串在集合中，否则说明不在。下图为字典树结构示例：

如上图所示，每条路径都是一个词汇，且没有子节点就可以判定该条路径结尾了。具体可以映射为下标所示：

至于字典树的实现，相信只要认真学过数据结构的读者，都能手到擒来，这里不在赘述。因为HanLP库已经提供了多种字典树。

DoubleArrayTrieSegment

认识DoubleArrayTrieSegment类之前，我们需要了解双数组字典书的概念。

我们都知道，在树中遍历查找之时，我们一般用二分查找，假如某一个树的节点有N个节点，那么其复杂度就为O(logN)，这样查找起来一条一条树的遍历会非常的慢，所以就诞生了双数组字典树的概念。

双数组字典树（DAT）是一种状态转移复杂度为常数的数据结构。那么什么是状态呢？从确定有限状态自动机（DFA）的角度来讲，每个节点都是一个状态，状态表示当前已查询到的前缀。

从父节点到子节点的移动过程可以看作一次状态转移。在按照某个字符进行状态转移前，我们会向父节点询问该字符与子节点的映射关系（也就是一条路径一条边）。如果父节点有满足条件的边，则状态转移到子节点；否则立即失败，查询不到。当成功完成了全部转移时，我们就拿到了最后一个状态，询问该状态是否时最终状态。如果是，就查询到该词汇，否则该单词不存在于字典中。

比如我们查询首图的“北京大学”，状态开始为0，查询到北时状态为3，查询到京时状态为4，查询到大时状态为6，查询到学时状态为7，最后判断7是否还有子节点，如果没有匹配该词汇，如果有该词汇不在字典中。比如查询“北京大”就不在词汇中。

而双数组字典由base与check两个数组组成，其中base数组即节点，也是状态，分为空闲状态与占用状态，check数组为每个元素表示某个状态的前驱状态。具体公式如下：

base[s] + c = t
check[t] =  s

base树组中的s代表当前状态的下标，t代表转移状态的下标，c代表输入字符的数值

base[s] + c = t //表示一次状态转移

由于转移后状态下标为t，且父子关系是唯一的，所以可通过检验当前元素的前驱状态确定转移是否成功

check[t] = s //检验状态转移是否成功

这种算法相对于传统的Trie树二分查找的优点是，只需要一个加法一次比较即可完成一次状态转移，只花费了常数时间，下面给出了双数组Tree树的原理图（注意观察状态转移的过程）

了解了双数组字典树的原理，我们就可以来学习DoubleArrayTrieSegment，DoubleArrayTrieSegment分词器是对DAT（双数组字典树）最长匹配的封装，默认加载hanlp.properites中CoreDictionaryPath指定的词典。

对应的python代码如下：

if __name__ == "__main__":
    HanLP.Config.ShowTermNature=False#分词结果不显示词性
    segment=DoubleArrayTrieSegment()
    print(segment.seg("在来到这个世界之前，一起都很Happy"))

运行之后，得到如下图所示的结果：

当然，这是HanLP提供给我们的默认词典，如果想加载自己的词典，或者前文提到的其他开源的词典库，可以替换代码如下所示：

DoubleArrayTrieSegment(["词典1"，"词典2"])

但是不知道读者注意到了没有，上面的英文happy，它给我们拆成了单个的字母，但其实这是一个整体，如果这里替换成数字，也是一个一个数字，那么如何不让其拆开呢？

我们来看一段代码：

if __name__ == "__main__":
    HanLP.Config.ShowTermNature=True
    segment=DoubleArrayTrieSegment()
    segment.enablePartOfSpeechTagging(True)
    print(segment.seg("在来到这个世界之前，一起都很Happy"))

enablePartOfSpeechTagging函数的意思是激活数字与英文识别，同时我们把ShowTermNature改为True，观察其输出的结果：

这里与我们前面自己写的算法输出一模一样，有分开的词汇以及词汇的标记属性。

AhoCorasickDoubleArrayTrieSegment

虽然双数组字典树能遍历大量的数据，但是如果数据比较长的，这些长的词汇又比较多的话，比如“受命于天，既寿永昌”算一个词汇，那么其处理起来时间复杂度依旧非常耗时。所以，我们就需要使用ACDAT进行遍历。

这里博主不讲解其原理，因为太长篇幅有限，感兴趣的可以专门学习树结构的处理。读者只需要知道其原理，什么时候用双数组遍历，什么时候用ACDAT遍历就行。而HanLP封装的ACDAT的实现类是AhoCorasickDoubleArrayTrieSegment。

下面，我们来实现AhoCorasickDoubleArrayTrieSegment，代码如下：

if __name__ == "__main__":
    HanLP.Config.ShowTermNature = False
    segment = JClass("com.hankcs.hanlp.seg.Other.AhoCorasickDoubleArrayTrieSegment")()
    print(segment.seg("在来到这个世界之前，一起都很井然有序"))

运行之后，效果如下：

需要注意的是，python的HanLP虽然提供了AhoCorasickDoubleArrayTrieSegment类，但是读者可以试试，替换后运行会报错，控制台会提示该类没有seg函数。而HanLP库又是基于Java开发的，所以在实际的项目中，尽量使用JClass加载Java类进行实战，因为python的HanLP库运行速度比Java慢一倍，但python的好处是相对简单，可以调用其他程序的类，所以速度这方面只要python引用Java类进行调用，其实速度一样。