【结巴分词资料汇编】结巴中文分词源码分析(2)

作者这个版本(0.37)中使用前缀字典实现了词库的存储(即dict.txt文件中的内容)，而弃用之前版本的trie树存储词库，中实现的trie树是基于dict类型的而且dict中又嵌套dict 类型，这样嵌套很深，导致内存耗费严重，具体点这里，下面是@gumblex commit的内容:

对于get_DAG()函数来说，用Trie数据结构，特别是在Python环境，内存使用量过大。经实验，可构造一个前缀集合解决问题。

jieba0.37版本中实际使用是前缀字典具体实现(对应代码中Tokenizer.FREQ字典)，即就是利用python中的dict把dict.txt中出现的词作为key，出现频次作为value，比如sentece : “北京大学”,处理后的结果为：{u’北’:17860, u’北京’ :34488,u’北京大’: 0,u’北京大学’: 2053}，具体详情见代码：

DAG根据我们生成的前缀字典来构造一个这样的DAG，对一个sentence DAG是以{key:list[i,j…], …}的字典结构存储，其中key是词的在sentence中的位置，list存放的是在sentence中以key开始且词sentence[key:i+1]在我们的前缀词典中 的以key开始i结尾的词的末位置i的列表，即list存放的是sentence中以位置key开始的可能的词语的结束位置，这样通过查字典得到词, 开始位置+结束位置列表。

通过上面两小节可以得知，我们已经有了词库(dict.txt)的前缀字典和待分词句子sentence的DAG，基于词频的最大切分 要在所有的路径中找出一条概率得分最大的路径，该怎么做呢？

“去北京大学玩”的前缀字典:

关于HMM的介绍网络上有很多资源，比如 52nlp HMM系列,在此不再具体介绍了，但一些基础知识要明确的：

• HMM(Hidden Markov Model): 隐式马尔科夫模型。 HMM模型可以应用在很多领域，所以它的模型参数描述一般都比较抽象，以下篇幅针对HMM的模型参数介绍直接使用它在中文分词中的实际含义来讲：

• HMM解决的三类问题： a. 评估问题(概率计算问题) 即给定观测序列 O=O1,O2,O3…Ot和模型参数λ=(A,B,π)，怎样有效计算这一观测序列出现的概率. (Forward-backward算法) b. 解码问题(预测问题) 即给定观测序列 O=O1,O2,O3…Ot和模型参数λ=(A,B,π)，怎样寻找满足这种观察序列意义上最优的隐含状态序列S。 (viterbi算法,近似算法) c. 学习问题 即HMM的模型参数λ=(A,B,π)未知，如何求出这3个参数以使观测序列O=O1,O2,O3…Ot的概率尽可能的大. (即用极大似然估计的方法估计参数,Baum-Welch,EM算法)

• HMM 模型的五元组表示： { states，//状态空间 observations，//观察空间 start_probability，//状态的初始分布，即π  transition_probability，//状态的转移概率矩阵，即A emission_probability//状态产生观察的概率，发射概率矩阵,即B }

使用jieba对句子:”到MI京研大厦”进行分词，若是使用非HMM模式则分词的结果为： 到/MI/京/研/大厦， 使用HMM分词则结果为：到/MI/京研/大厦。下面一段是利用上一节的程序的计算结果。

 从句子”到MI京研大厦”对应的前缀字典可以看出“京研”并没有在字典中，但是也被Viterbi算法识别出来了，可以看出HMM的强大之处了，也正是 HMM 三大基本问题之一，即根据观察序列，求隐藏状态序列。 上一节中我们说明了HMM由五元组表示，那么这样的五元组参数在中文分词中的具体含义是：

• states(状态空间) & observations(观察空间). 汉字按照BEMS四个状态来标记，分别代表 Begin End Middle 和 Single， {B:begin, M:middle, E:end, S:single}。分别代表每个状态代表的是该字在词语中的位置，B代表该字是词语中的起始字，M代表是词语中的中间字，E代表是词语中的结束字，S则代表是单字成词。 观察空间为就是所有汉字(我她…)，甚至包括标点符号所组成的集合。 状态值也就是我们要求的值，在HMM模型中文分词中，我们的输入是一个句子(也就是观察值序列)，输出是这个句子中每个字的状态值，用这四个状态符号依次标记输入句子中的字，可方便的得到分词方案。 如： 观察序列：我在北京 状态序列：SSBE 对于上面的状态序列，根据规则进行划分得到 S/S/BE/ 对应于观察序列：我/在/北京/ 分词任务就完成了。 同时我们可以注意到： B后面只可能接(M or E)，不可能接(B or E)。而M后面也只可能接(M or E)，不可能接(B, S)。

  上文只介绍了五元组中的两元 states & observations，下文介绍剩下的三元（start_probability，transition_probability，emission_probability）.

• start_probability(状态的初始分布). 初始状态概率分布是最好理解的，如下

  示例数值是对概率值取对数之后的结果(trick, 让概率相乘变成对数相加)，其中-3.14e+100作为负无穷，也就是对应的概率值是0。它表示了一个句子的第一个字属于{B,E,M,S}这四种状态的概率，如上可以看出，E和M的概率都是0，这和实际相符合，开头的第一个字只可能是词语的首字(B)，或者是单字成词(S)，这部分内容对应 jieba/finalseg/prob_start.py文件，具体源码。

• transition_probability（状态的转移概率矩阵） 转移概率是马尔科夫链很重要的一个知识点，马尔科夫链(一阶)最大的特点就是当前T=i时刻的状态state(i)，只和T=i时刻之前的n个状态有关，即: {state(i-1), state(i-2), … state(i - n)} HMM模型有三个基本假设： a. 系统在时刻t的状态只与时刻t-1处的状态相关,(也称为无后效性）; b. 状态转移概率与时间无关,(也称为齐次性或时齐性);  c. 假设任意时刻的观测只依赖于该时刻的马尔科夫链的状态，与其它观测及状态无关,(也称观测独立性假设)。 其中前两个假设为马尔科夫模型的假设。 模型的这几个假设能大大简化问题。 再看下transition_probability，其实就是一个嵌套的字典，数值是概率求对数后的值,示例: 如P[‘B’][‘E’]代表的含义就是从状态B转移到状态E的概率，由P[‘B’][‘E’] = -0.510825623765990，表示状态B的下一个状态是E的概率对数是-0.510825623765990。 这部分内容对应 jieba/finalseg/prob_trans.py文件，具体源码。

• emission_probability(状态产生观察的概率，发射概率) 根据HMM观测独立性假设发射概率，即观察值只取决于当前状态值，也就是: P(observed[i], states[j]) = P(states[j]) * P(observed[i]|states[j]),其中P(observed[i]|states[j])这个值就是从emission_probability中获取。 emission_probability示例如下：

• 比如P[‘B’][‘一’]代表的含义就是’B’状态下观测的字为’一’(对应的汉字为’一’)的概率对数P[‘B’][‘一’] = -3.6544978750449433。 这部分内容对应 jieba/finalseg/prob_emit.py文件，具体源码。

到这里已经结合HMM模型把jieba的五元参数介绍完，这五元的关系是通过一个叫Viterbi的算法串接起来，observations序列值是Viterbi的输入，而states序列值是Viterbi的输出，输入和输出之间Viterbi算法还需要借助三个模型参数，分别是start_probability，transition_probability，emission_probability。对于未登录词（OOV）的问题，即已知观察序列S，初始状态概率prob_start，状态观察发射概率prob_emit，状态转换概率prob_trans。 求状态序列W，这是个解码问题，维特比算法可以解决。

• Viterbi 维特比算法 HMM第二个问题又称为解码问题(预测问题)即给定观测序列 O=O1,O2,O3…Ot和模型参数λ=(A,B,π)，怎样寻找满足这种观察序列意义上最优的隐含状态序列S。 (viterbi算法,近似算法)，同样的，暴力算法是计算所有可能性的概率，然后找出拥有最大概率值的隐藏状态序列。与问题一的暴力解决方案类似，复杂度为O(N^T)。 那应该用什么方案呢？还是动态规划！ 假设观察序列为O1,O2,O3,…,Ot. 在时刻i ∈ (1,t]时，定义D为观察O1,O2,…,Oi且Si=Sk时产生该观察序列的最大概率： 其中，S1,S2,….S(i-1),在此时也已经可以得到(子问题)。 它是一个是对子问题求最大值的最优解问题。 对于解码问题，因为需要求出的是使得观察序列概率最大的隐藏状态的序列，而不是最大概率，所以，在算法计算过程中，还需要记录前一个隐藏状态的值。

• jieba Viterbi 的应用

  jieba中对于未登录词问题，通过__cut_DAG 函数我们可以看出这个函数前半部分用 calc 函数计算出了初步的分词，而后半部分就是就是针对上面例子中未出现在语料库的词语进行分词了。 由于基于频度打分的分词会倾向于把不能识别的词组一个字一个字地切割开，所以对这些字的合并就是识别OOV的一个方向，__cut_DAG定义了一个buf 变量收集了这些连续的单个字，最后把它们组合成字符串再交由 finalseg.cut 函数来进行下一步分词。

对应的viterbi算法: