Jieba分词包（二）——trie树和DAG

小鱼儿 2022-08-14 03:43 159阅读 0赞

# Jieba分词包（二）——trie树和DAG #

在Jieba分词包的源码中，有一个重要的分词函数——\_\_cut\_DAG(sentence)，它里面涉及到了trie树和DAG有向无环图。在作者的说明文档中也指出了：基于Trie树结构实现高效的词图扫描，生成句子中汉字所有可能成词情况所构成的有向无环图（DAG)。所以说这篇博客我们就来说说Jieba里面的trie树和DAG图。

## 1. trie树 ##

Jieba里面的trie树是基于一个字典构建的，这个字典在dict.txt中，里面有2W多条词，包含了词条出现的次数（这个次数是于作者自己基于人民日报语料等资源训练得出来的）和词性。这个第一条的trie树结构的词图扫描，说的就是把这2万多条词语，放到一个trie树中，而trie树是有名的前缀树，也就是说一个词语的前面几个字一样，就表示他们具有相同的前缀，就可以使用trie树来存储，具有查找速度快的优势。

从上面的trie树你就可以猜到，trie树这家伙是一个用来存储有相同前缀的字符串（汉字也行，反正都是字符），而且查找的速度很快。为什么要这么快的查收速度呢？哦，原来是后面画DAG图的时候要用到trie树的速度快的优势。

不管怎么说，我们先简单说一下trie树吧~

ps：trie树也叫字典树，也叫单词查找树，看出来了吧~这家伙居然把自己的名字和功能紧密结合啦~~

单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希表高。

下面我们有and,as,at,cn,com这些关键词，那么如何构建trie树呢？

![Center][]

从上面的图中，我们或多或少的可以发现一些好玩的特性。  
  
第一：根节点不包含字符，除根节点外的每一个子节点都包含一个字符。  
第二：从根节点到某一节点，路径上经过的字符连接起来，就是该节点对应的字符串。  
第三：每个单词的公共前缀作为一个字符节点保存。每个节点的所有子节点包含的字符都不相同

既然学Trie树，我们肯定要知道这玩意是用来干嘛的。  
  
第一：词频统计。  
  
可能有人要说了，词频统计简单啊，一个hash或者一个堆就可以打完收工，但问题来了，如果内存有限呢？还能这么玩吗？所以这里我们就可以用trie树来压缩下空间，因为公共前缀都是用一个节点保存的。  
  
第二: 前缀匹配  
  
就拿上面的图来说吧，如果我想获取所有以"a"开头的字符串，从图中可以很明显的看到是：and,as,at，如果不用trie树，你该怎么做呢？很显然朴素的做法时间复杂度为O(N2) ，那么用Trie树就不一样了，它可以做到h，h为你检索单词的长度，可以说这是秒杀的效果。  
  
举个例子：现有一个编号为1的字符串”and“，我们要插入到trie树中，采用动态规划的思想，将编号”1“计入到每个途径的节点中，那么以后我们要找”a“，”an“，”and"为前缀的字符串的编号将会轻而易举。

![Center 1][]

更多关于trie树的，可参考：http://www.cnblogs.com/huangxincheng/archive/2012/11/25/2788268.html

## 2. DAG图 ##

给定一个待分词的句子，对这个句子进行生成有向无环图。对待分词句子，根据dict.txt生成的trie树，生成DAG, 实际上通俗的说, 就是对待分词句子, 根据给定的词典进行查词典操作, 生成几种可能的句子切分. dag是啥玩意?记录了啥呢? 作者的源码中记录的是句子中某个词的开始位置, 从0到n-1(n为句子的长度), 每个开始位置作为字典的键, value是个list, 其中保存了可能的词语的结束位置(通过查字典得到词, 开始位置+词语的长度得到结束位置)。

例如:\{0:\[1,2,3\]\} 这样一个简单的DAG, 就是表示0位置开始, 在1,2,3位置都是词, 就是说0~1, 0~2,0~3这三个起始位置之间的字符, 在dict.txt中是词语.

比如 sentence 是 "国庆节我在研究结巴分词"，对应生成的DAG是这样的：\{0: \[0, 1, 2\], 1: \[1\], 2: \[2\], 3: \[3\], 4: \[4\], 5: \[5, 6\], 6: \[6\], 7: \[7, 8\], 8: \[8\], 9: \[9, 10\], 10: \[10\]\} 其中的数字表示每个汉字在sentence中的位置，所以0：\[0,1,2\] 表示 在trie 树中，"国"开头的词语中对应于该 sentence 有三种匹配情况：国，国庆，国庆节。

[Center]: /images/20220810/99274dfe2f5e4b18bdec7cf6855eef2a.png
[Center 1]: /images/20220810/409ecffd94704c5a89ea01fb8f1da243.png