jieba算法过程的理解和分析

Published: 16 Jan 2019 Category: NLP

一、结巴分词算法

作者说明文件中提到的结巴分词用到的算法:

  • 基于Trie树结构实现高效的词图扫描,生成句子中汉字所有可能成词情况所构成的有向无环图(DAG)
  • 采用了动态规划查找最大概率路径, 找出基于词频的最大切分组合
  • 对于未登录词,采用了基于汉字成词能力的HMM模型,使用了Viterbi算法

Trie树是什么?

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

3个基本性质:一、根节点不包含字符,除根节点外每一个节点都只包含一个字符; 二、从根节点到某一节点,路径上经过的字符连接起来,为该节点对应的字符串; 三、每个节点的所有子节点包含的字符都不相同。

1.1 词图扫描并生成DAG

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

聪明的人可能会想到把 dict.txt中所有的词汇全部删掉, 然后再试试结巴能不能分词, 结果会发现, 结巴依然能够分词, 不过分出来的词, 大部分的长度为2.这个就是第三条, 基于HMM来预测分词了.

接着说DAG有向无环图, 也就是给定一个 待分词的句子, 对这个句子进行生成有向无环图. 这篇 http://book.51cto.com/art/201106/269048.htm 比较形象地用图来表示了一个待分词句子的切分情况.

作者是怎么切分的呢?
1、根据dict.txt生成trie树,
2、对待分词句子, 根据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中是词语.

1.2 用动态规划查找最大概率路径, 找出基于词频的最大切分组合

作者的代码中讲字典在生成trie树的同时, 也把每个词的出现次数转换为了频率.

关于频率和概率, 这里在啰嗦几句: 按照定义, 频率其实也是一个0~1之间的小数, 是 事件出现的次数/实验中的总次数, 因此在试验次数足够大的情况下, 频率约等于概率, 或者说频率的极限就是概率. 不过通常人们混淆的是频率和次数, 经常把频率等同于事件出现的次数, 比如这里就是某个词语出现的次数, 所以, 频率在引起混淆的时候, 对中国人来说, 还是先理解为出现次数, 然后理解发现有问题, 就理解为出现次数/总数这个比率吧.

在动态规划中, 先查找待分词句子中已经切分好的词语, 对该词语查找该词语出现的频率(次数/总数), 如果没有该词(既然是基于词典查找, 应该是有的), 就把词典中出现频率最小的那个词语的频率作为该词的频率, 也就是说P(某词语)=FREQ.get('某词语',min_freq), 然后根据动态规划查找最大概率路径的方法, 对句子从右往左反向计算最大概率, P(NodeN)=1.0, P(NodeN-1)=P(NodeN)*Max(P(倒数第一个词))...依次类推, 最后得到最大概率路径, 得到最大概率的切分组合.

为什么对句子从右往左反向计算最大概率?一些教科书上可能是从左往右, 这里反向是因为汉语句子的重心经常落在后面, 就是落在右边, 因为通常情况下形容词太多, 后面的才是主干, 因此, 从右往左计算, 正确率要高于从左往右计算, 这个类似于逆向最大匹配

1.3 对于未登录词,采用基于汉字成词能力的HMM模型,使用了Viterbi算法

未登录词, 作者说的是什么意思? 其实就是词典 dict.txt 中没有记录的词. 上面说了, 把dict.txt中的所有词语都删除了, 结巴分词一样可以分词, 就是说的这个.

怎么做到的? 这个就基于作者采用的HMM模型了, 中文词汇按照BEMS四个状态来标记, B是开始begin位置, E是end, 是结束位置, M是middle, 是中间位置, S是singgle, 单独成词的位置, 没有前, 也没有后.

也就是说, 他采用了状态为(B,E,M,S)这四种状态来标记中文词语, 比如北京可以标注为 BE, 即 北/B 京/E, 表示北是开始位置, 京是结束位置, 中华民族可以标注为BMME, 就是开始, 中间, 中间, 结束.

经过作者对大量语料的训练, 得到了finalseg目录下的三个文件(来自结巴项目的issues):

要统计的主要有三个概率表:

1) prob_trans.py 位置转换概率 位置转换概率,即B(开头),M(中间),E(结尾),S(独立成词)四种状态的转移概率;

{'B': {'E': 0.8518218565181658, 'M': 0.14817814348183422},
'E': {'B': 0.5544853051164425, 'S': 0.44551469488355755},
'M': {'E': 0.7164487459986911, 'M': 0.2835512540013088},
'S': {'B': 0.48617017333894563, 'S': 0.5138298266610544}}

P(E|B) = 0.851, P(M|B) = 0.149,说明当我们处于一个词的开头时,下一个字是结尾的概率 要远高于下一个字是中间字的概率,符合我们的直觉,因为二个字的词比多个字的词更常见。

2)prob_emit.py 位置到单字的发射概率,比如P(“和”|M)表示一个词的中间出现”和”这个字的概率;

3) prob_start.py 词语以某种状态开头的概率,其实只有两种,要么是B,要么是S。这个就是起始向量, 就是HMM系统的最初模型状态

实际上, BEMS之间的转换有点类似于2元模型, 就是2个词之间的转移。二元模型考虑一个单词后出现另外一个单词的概率,是N元模型中的一种。

例如:一般来说,”中国”之后出现”北京”的概率大于”中国”之后出现”北海”的概率,也就是:中国北京 比 中国北海出现的概率大些, 更有可能是一个中文词语.

不过, 作者这里应该不是用的2元分词模型的, 这里的BEMS只提供了单个汉字之间的转换, 发射概率, 并没有提供粒度更大的, 基于词语的发射和转移概率。

给定一个 待分词的句子, 就是观察序列, 对HMM(BEMS)四种状态的模型来说, 就是为了找到一个最佳的BEMS序列, 这个就需要使用viterbi算法来得到这个最佳的隐藏状态序列, 具体的python版的viterbi算法请看维基百科: 维特比算法

通过作者之前训练得到的概率表和viterbi算法, 就可以得到一个概率最大的BEMS序列, 按照B打头, E结尾的方式, 对待分词的句子重新组合, 就得到了分词结果.

比如 对待分词的句子 ‘全世界都在学中国话’ 得到一个BEMS序列 [S,B,E,S,S,S,B,E,S] 这个序列只是举例, 不一定正确, 通过把连续的BE凑合到一起得到一个词, 单独的S放单, 就得到一个分词结果了: 上面的BE位置和句子中单个汉字的位置一一对应, 得到全/S 世界/BE 都/S 在/S 学/S 中国/BE 话/S 从而将句子切分为词语.

REF

对Python中文分词模块结巴分词算法过程的理解和分析
4.6 概率语言模型的分词方法
字典树(Trie树)实现与应用