jieba结巴分词原理浅析与理解 HMM应用在中文分词 及部分代码阅读

2021-06-26 18:50:38 浏览数 (3)

1. 背景

这篇博客主要阐述我们在分词任务中常用的分词库结巴jieba分词的实现原理，以及之前博客中讲到的HMM在分词中的应用，算是复习与加深理解一下HMM的知识。jieba分词作为一个十年前的分词库，更新到现在依然还是非常好用而且也很经典适合学习。

2. 中文分词背景

2.1 特点

  1. 在中文里面，词是最小的能够独立活动的有意义的语言成分；
  2. 汉语是以字位单位，不像西方语言，词与词之间没有空格之类的标志指示词的边界；
  3. 分词问题为中文文本处理的基础性工作,分词的好坏对后面的中文信息处理其关键作用。

2.2 难点

  1. 分词规范，词的定义还不明确 《统计自然语言处理》宗成庆
  2. 歧义切分问题，交集型切分问题，多义组合型切分歧义等 结婚的和尚未结婚的 => 结婚／的／和／尚未／结婚／的 结婚／的／和尚／未／结婚／的
  3. 未登录词问题有两种解释： 一是已有的词表中没有收录的词， 二是已有的训练语料中未曾出现过的词，第二种含义中未登录词又称OOV(Out of Vocabulary)。对于大规模真实文本来说，未登录词对于分词的精度的影响远超歧义切分。一些网络新词，自造词一般都属于这些词。

2.3 基本方法

  • 基于字典、词库匹配的分词方法(基于规则)
    • 基于字符串匹配分词，机械分词算法。将待分的字符串与一个充分大的机器词典中的词条进行匹配。分为正向匹配和逆向匹配；最大长度匹配和最小长度匹配；单纯分词和分词与标注过程相结合的一体化方法。所以常用的有：正向最大匹配，逆向最大匹配，最少切分法。实际应用中，将机械分词作为初分手段，利用语言信息提高切分准确率。优先识别具有明显特征的词，以这些词为断点，将原字符串分为较小字符串再机械匹配，以减少匹配错误率，或将分词与词类标注结合。
  • 基于词频度统计的分词方法(基于统计)
    • 相邻的字同时出现的次数越多，越有可能构成一个词语，对语料中的字组频度进行统计，基于词的频度统计的分词方法是一种全切分方法。jieba是基于统计的分词方法，jieba分词采用了动态规划查找最大概率路径, 找出基于词频的最大切分组合，对于未登录词，采用了基于汉字成词能力的HMM模型，使用了Viterbi算法
  • 基于知识理解的分词方法
    • 该方法主要基于句法、语法分析，并结合语义分析，通过对上下文内容所提供信息的分析对词进行定界，它通常包括三个部分：分词子系统、句法语义子系统、总控部分。在总控部分的协调下，分词子系统可以获得有关词、句子等的句法和语义信息来对分词歧义进行判断。这类方法试图让机器具有人类的理解能力，需要使用大量的语言知识和信息。由于汉语语言知识的笼统、复杂性，难以将各种语言信息组织成机器可直接读取的形式。因此目前基于知识的分词系统还处在试验阶段。

3. 结巴算法简述

3.1 综述

  1. 基于前缀词典实现高效的词图扫描，生成句子中汉字所有可能成词情况所构成的有向无环图 (DAG);
    1. 使用前缀字典实现了词库的存储(即dict.txt文件中的内容); 生成句子中汉字所有可能成词情况所构成的有向无环图。DAG根据我们生成的前缀字典来构造一个这样的DAG，对一个sentence DAG是以{key:listi,j…, …}的字典结构存储，其中key是词的在sentence中的位置，list存放的是在sentence中以key开始且词sentencekey:i 1在我们的前缀词典中的以key开始i结尾的词的末位置i的列表，即list存放的是sentence中以位置key开始的可能的词语的结束位置，这样通过查字典得到词, 开始位置 结束位置列表。
    2. 例如:句子“抗日战争”生成的DAG中{0:0,1,3} 这样一个简单的DAG, 就是表示0位置开始, 在0,1,3位置都是词, 就是说0~0,0~1,0~3 即 “抗”，“抗日”，“抗日战争”这三个词 在dict.txt中是词。
  2. 采用了动态规划查找最大概率路径, 找出基于词频的最大切分组合; 基于上面的DAG利用动态规划查找最大概率路径。根据动态规划查找最大概率路径的基本思路就是对句子从右往左反向计算最大概率，..依次类推, 最后得到最大概率路径, 得到最大概率的切分组合
  3. 对于未登录词，采用了基于汉字成词能力的 HMM 模型，使用了 Viterbi 算法；
    1. 未登录词中说的OOV， 其实就是词典 dict.txt 中没有记录的词。这里采用了HMM模型。HMM基础可以参见上一篇博客；
    2. 模型的关键相应参数λ=(A,B,π)，经过对大量语料的训练, 得到了finalseg目录下的三个文件（初始化状态概率（π）即词语以某种状态开头的概率，其实只有两种，要么是B，要么是S。这个就是起始向量, 就是HMM系统的最初模型状态，对应文件prob_start.py；隐含状态概率转移矩A 即字的几种位置状态(BEMS四个状态来标记, B是开始begin位置, E是end, 是结束位置, M是middle, 是中间位置, S是single, 单独成词的位置)的转换概率，对应文件prob_trans.py；观测状态发射概率矩阵B 即位置状态到单字的发射概率，比如P(“狗”|M)表示一个词的中间出现”狗”这个字的概率，对应文件prob_emit.py）。

看了这么多可能还是跟我一样一头雾水，可以跟着一起看看每一步的具体实现。

3.2 基于前缀词典实现高效的词图扫描，生成句子中汉字所有可能成词情况所构成的有向无环图(DAG)

3.2.1 Trie前缀树

结巴分词自带了一个叫做dict.txt的词典，里面有349046条词，其每行包含了词条、词条出现的次数（这个次数是结巴作者基于人民日报语料等资源训练得出来的）和词性，如下图所示。

在基于词典的中文分词方法中，词典匹配算法是基础。为了保证切分速度，需要选择一个好的查找词典算法。

这里介绍词典的Trie树组织结构。基于前缀词典实现的词图扫描，就是把这34万多条词语，放到一个trie树的数据结构中，trie树也叫前缀树或字典树，也就是说一个词语的前面几个字一样，就表示他们具有相同的前缀，就可以使用trie树来存储，具有查找速度快的优势。

一个搜索数字的trie树的一个节点只保留一个字符。如果一个单词比一个字符长，则包含第个字符的节点有指针指向下一个字符的节点，以此类推。这样组成一个层次结构的树，树的第一层包括所有单词的第一个字符，树的第二层包括所有单词的第二个字符，以此类推。很显然，trie树的最大高度是词典中最长单词的长度。

3.2.2 DAG有向无环图

DAG有向无环图，就是后一句中的生成句子中汉字所有可能成词情况所构成的有向无环图，这个是说，给定一个待分词的句子，将它的所有词匹配出来，构成词图，即是一个有向无环图DAG，如下图所示：

DAG词图，每条边上是一个词

那么具体是怎么做的呢？分为两步：

  1. 根据dict.txt词典生成trie树；
  2. 对待分词句子，根据trie树，生成DAG。

实际上，通俗的说，就是对待分词句子，根据给定的词典进行查词典操作，生成几种可能的句子切分，形成类似上图所示的DAG图。

对于DAG的实现，在源码中，作者记录的是句子中某个词的开始位置，从0到n-1(n为句子的长度)，设置一个python的字典，每个开始位置作为字典的键，value是个python的list，其中保存了可能的词语的结束位置（通过查字典得到词，然后将词的开始位置加上词语的长度得到结束位置）。例如：{0:[1,2,3]}这样一个简单的DAG，就是表示0位置开始，在1,2,3位置都是某个词的结束位置，就是说0 ~ 1, 0 ~ 2，0 ~ 3这三个位置范围之间的字符，在dict.txt中都是词语。

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

作者的代码中将字典在生成trie树的同时，也把每个词的出现次数转换为了频率。频率其实也是一个0~1之间的小数，是事件出现的次数/实验中的总次数，因此在试验次数足够大的情况下，频率约等于概率，或者说频率的极限就是概率。

动态规划中，先查找待分词句子中已经切分好的词语，对该词语查找该词语出现的频率(次数/总数)，如果没有该词(既然是基于词典查找，应该是有可能没有该词)，就把词典中出现频率最小的那个词语的频率作为该词的频率。也就是说，P(某词语)=FREQ.get(‘某词语’, min_freq)， 然后根据动态规划查找最大概率路径。对句子从右往左反向计算最大概率(也可以是从左往右，这里反向是因为汉语句子的重心经常落在后面，就是落在右边，主要是因为在通常情况下形容词太多，后面的才是主干，因此，从右往左计算，正确率要高于从左往右计算，类似于逆向最大匹配的分词方法)

所以状态转移方程为

P(NodeN)=1.0, P(NodeN-1)=P(NodeN)*Max(P(倒数第一个词))，依次类推，最后得到最大概率路径，即得到最大概率的切分组合。

所以在上图DAG中，得到的最大切分组合是有-意见-分歧，即0-1-3-5

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

未登录词(Out Of Vocabulary word, OOV word)，在这里指词典dict.txt中没有记录的词。如果把dict.txt中的所有词语都删除了，结巴分词一样可以分词，就是说的这个。怎么做到的? 这个就基于作者采用的HMM模型了，中文词汇按照BEMS四个状态来标记，B是开始begin位置，E是是结束end位置，M是中间middle位置，S是single，单独成词的位置。也就是说，他采用了状态为(B,E,M,S)这四种状态来标记中文词语，比如北京可以标注为 BE, 即北/B京/E，表示北是开始位置，京是结束位置。中华民族可以标注为BMME，就是开始，中间，中间，结束。

经过作者对大量语料的训练，得到了finalseg目录下的三个文件:

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

1) 位置转换概率，即B(开头)，M(中间)，E(结尾)，S(独立成词) 四种状态的转移概率，该表存放于prob_trans.py中，下面为表中内容；

代码语言：txt复制
{'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）位置到单字的发射概率，比如P("和"|M)表示一个词的中间出现"和"这个字的概率，该表存放于prob_emit.py中；

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

实际上，BEMS之间的转换有点类似于2元模型，就是2个词之间的转移。二元模型考虑一个单词后出现另外一个单词的概率，是N元模型中的一种。 例如：一般来说，中国之后出现北京的概率大于中国之后出现北海的概率，也就是：中国北京比中国北海出现的概率大些，更有可能是一个中文词语。

将一个给定的待分词的句子视为一个观察序列，对HMM(BEMS)四种状态的模型来说，就是为了找到一个最佳的BEMS隐状态序列，这个就需要使用Viterbi算法来得到这个最佳的隐藏状态序列。通过提前训练好的HMM转移概率、发射概率，使用基于动态规划的viterbi算法的方法，就可以找到一个使概率最大的BEMS序列。按照B打头，E结尾的方式，对待分词的句子重新组合，就得到了分词结果。

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

接下来我们详细看一下如何使用HMM的viterbi找到BEMS序列

3.4.1 HMM基本概念

复习一下，HMM的典型模型是一个五元组:

  • StatusSet: 状态值集合
  • ObservedSet: 观察值集合
  • TransProbMatrix: 转移概率矩阵
  • EmitProbMatrix: 发射概率矩阵
  • InitStatus: 初始状态分布

HMM模型的三个基本假设如下：

  • 有限历史性假设(当前状态只与上一个状态相关):
    • P(Statusi|Statusi-1,Statusi-2,… Status1) = P(Statusi|Statusi-1)
  • 齐次性假设(状态和当前时刻无关):
    • P(Statusi|Statusi-1) = P(Statusj|Statusj-1)
  • 观察值独立性假设(观察值只取决于当前状态值):
    • P(Observedi|Statusi,Statusi-1,…,Status1) = P(Observedi|Statusi)

3.4.2 HMM中五元组对应结巴分词

回到正题，在结巴分词中五元组分别为：

  • 状态值集合（StatusSet） 为(B, M, E, S): {B:begin, M:middle, E:end, S:single}。分别代表每个状态代表的是该字在词语中的位置，B代表该字是词语中的起始字，M代表是词语中的中间字，E代表是词语中的结束字，S则代表是单字成词。 如：给你一个隐马尔科夫链的例子。 可以标注为：给/S 你/S 一个/BE 隐马尔科夫链/BMMMME 的/S 例子/BE 。/S
  • 观察值集合（ObservedSet） 为就是所有汉字(东南西北你我他…)，甚至包括标点符号所组成的集合。 状态值也就是我们要求的值。在HMM模型中文分词中, 输入是一个句子(也就是观察值序列)，输出是这个句子中每个字的状态值。
  • 初始状态概率分布（InitStatus ） 如：

B -0.26268660809250016 E -3.14e 100 M -3.14e 100 S -1.4652633398537678

数值是对概率值取【对数】之后的结果(可以让概率【相乘】的计算变成对数【相加】)。其中-3.14e 100作为负无穷，也就是对应的概率值是0。

也就是句子的第一个字属于{B,E,M,S}这四种状态的概率

  • 转移概率矩阵（TransProbMatrix ） 根据上文提到的有限历史性假设 转移概率是马尔科夫链Status(i)只和Status(i-1)相关，这个假设能大大简化问题。所以，它其实就是一个4x4(4就是状态值集合的大小)的二维矩阵。矩阵的横坐标和纵坐标顺序是BEMS x BEMS。(数值是概率求对数后的值）
  • 发射概率矩阵（EmitProbMatrix ） 上文提到的观察值独立性假设 P(Observedi, Statusj) = P(Statusj) * P(Observedi|Statusj) 其中，P(Observedi|Statusj)这个值就是从EmitProbMatrix中获取。

3.4.3 使用HMM Viterbi算法decode

这五元的关系是通过一个叫Viterbi的算法串接起来，ObservedSet序列值是Viterbi的输入，而StatusSet序列值是Viterbi的输出，输入和输出之间Viterbi算法还需要借助三个模型参数，分别是InitStatus, TransProbMatrix, EmitProbMatrix。

以下句子为例：

小明硕士毕业于中国科学院计算所

定义变量

二维数组 weight4，4是状态数(0:B,1:E,2:M,3:S)，15是输入句子的字数。比如 weight0 代表 状态B的条件下，出现’硕’这个字的可能性。

二维数组 path4，4是状态数(0:B,1:E,2:M,3:S)，15是输入句子的字数。比如 path0 代表 weight0取到最大时，前一个字的状态，比如 path0 = 1, 则代表 weight0取到最大时，前一个字(也就是明)的状态是E。记录前一个字的状态是为了使用viterbi算法计算完整个 weight4 之后，能对输入句子从右向左地回溯回来，找出对应的状态序列。

具体代码实现如下：

代码语言：txt复制
B:-0.26268660809250016
E:-3.14e 100
M:-3.14e 100
S:-1.4652633398537678

且由EmitProbMatrix可以得出

Status(B) -> Observed(小)  :  -5.79545
Status(E) -> Observed(小)  :  -7.36797
Status(M) -> Observed(小)  :  -5.09518
Status(S) -> Observed(小)  :  -6.2475

所以可以初始化 weight[i][0] 的值如下：

weight[0][0] = -0.26268660809250016   -5.79545 = -6.05814
weight[1][0] = -3.14e 100   -7.36797 = -3.14e 100
weight[2][0] = -3.14e 100   -5.09518 = -3.14e 100
weight[3][0] = -1.4652633398537678   -6.2475 = -7.71276

注意上式计算的时候是相加而不是相乘，因为之前取过对数的原因。

//遍历句子，下标i从1开始是因为刚才初始化的时候已经对0初始化结束了
for(size_t i = 1; i < 15; i  )
{
    // 遍历可能的状态
    for(size_t j = 0; j < 4; j  ) 
    {
        weight[j][i] = MIN_DOUBLE;
        path[j][i] = -1;
        //遍历前一个字可能的状态
        for(size_t k = 0; k < 4; k  )
        {
            double tmp = weight[k][i-1]   _transProb[k][j]   _emitProb[j][sentence[i]];
            if(tmp > weight[j][i]) // 找出最大的weight[j][i]值
            {
                weight[j][i] = tmp;
                path[j][i] = k;
            }
        }
    }
}

确定边界条件和路径回溯

边界条件如下：

对于每个句子，最后一个字的状态只可能是 E 或者 S，不可能是 M 或者 B。

所以在本文的例子中我们只需要比较 weight1(E) 和 weight3(S) 的大小即可。

在本例中：

weight1 = -102.492;

weight3 = -101.632;

所以 S > E，也就是对于路径回溯的起点是 path3。

回溯的路径是:

SEBEMBEBEMBEBEB

倒序一下就是:

BE/BE/BME/BE/BME/BE/S

所以切词结果就是:

小明/硕士/毕业于/中国/科学院/计算/所

这里可以通过理解上文提到的所有，进行分词。

3.4.4 进一步理解Viterbi算法

维特比算法是基于动态规划思想的隐马尔科夫模型解法。动态规划原理提到，假设存在一条最优路径，那么将该路径切分成N段，那么这N段小路径都分别是该环境下的最优路径，否则就存在着其他未知小路径，能组成一个比最优路径还更好的路径，这显然不成立。

基于上述原理，我们只需要从时刻t=1开始，递归的计算子安时刻t状态为i的各条部分路径的最大概率，直至得到时刻t=T的状态为i的各条路径的最大概率，便可以得到最优路径。

假设HMM模型，隐藏状态={1,2,3}，观测序列={红，白，红}，模型参数如下，求解最大概率隐藏状态序列。

计算t=1时刻的概率

已知t=1时刻，观测为红，分别计算在在状态1,2,3的条件下得到观测的概率：

由上图，此时取状态=3时，得到最大局部概率，但是，这个节点并不一定会是最优路径的节点。

计算t>1时刻的概率

在t=2时刻观测到白，t=3时刻观测到红，分别计算观测概率如下：

如上图，在t=2时，对于状态s=1，分别计算由t-1时刻的状态s={1,2,3}的局部概率计算得到的t时刻的局部概率，得到最大的t时刻概率，以此类推。其中，0.1*0.5中的0.5来自于隐藏状态1转移到隐藏状态1的概率，0.16*0.3中的0.3来自于隐藏状态2转移到隐藏状态1的概率，以此类推。

递归结束

在t=3时刻，可以得到最大概率p=0.0147，此时可以得到最优路径的终点是i_3 = 3.

回溯最优路径

由最优路径的终点3开始，向前找到之前时刻的最优点：

（1）在t=2时刻，因为i_3 = 3，状态3的最大概率来源于状态3（上图没有显示出来，但可以参考状态1的计算过程）

（2）在t=1时刻，因为i_2 = 3，也可以得到最大概率来源于状态3

最后得到最优路径为（3,3,3）

4. 具体实现

jieba分词都是调用jieba.cut 这个函数，cut函数即是分词的入口，这个函数在文件jieba/__init__.py ,代码如下：

代码语言：txt复制
#jieba分词的主函数,返回结果是一个可迭代的 generator
 def cut(self, sentence, cut_all=False, HMM=True):
     '''
     The main function that segments an entire sentence that contains
     Chinese characters into seperated words.
     Parameter:
         - sentence: The str(unicode) to be segmented.
         - cut_all: Model type. True for full pattern, False for accurate pattern.
         - HMM: Whether to use the Hidden Markov Model.
     '''
     sentence = strdecode(sentence) # 解码为unicode
     # 不同模式下的正则
     if cut_all:
         re_han = re_han_cut_all
         re_skip = re_skip_cut_all
     else:
         re_han = re_han_default
         re_skip = re_skip_default
 
      # 设置不同模式下的cut_block分词方法
     if cut_all:
         cut_block = self.__cut_all
     elif HMM:
         cut_block = self.__cut_DAG
     else:
         cut_block = self.__cut_DAG_NO_HMM
     # 先用正则对句子进行切分
     blocks = re_han.split(sentence)
     for blk in blocks:
         if not blk:
             continue
         if re_han.match(blk): # re_han匹配的串
             for word in cut_block(blk):# 根据不同模式的方法进行分词
                 yield word
         else:# 按照re_skip正则表对blk进行重新切分
             tmp = re_skip.split(blk)# 返回list
             for x in tmp:
                 if re_skip.match(x):
                     yield x
                 elif not cut_all: # 精准模式下逐个字符输出
                     for xx in x:
                         yield xx
                 else:
                     yield x

其中参数sentence是需要分词的句子样本；cut_all是分词的模式，精确模式，全模式，默认使用HMM模型。下面根据cut函数来绘制出相应的流程图

5. 其他中文分词工具

  • 百度NLP开源工具LAC
  • 阿里云的分词和NER服务
  • 哈工大LTP
  • 清华THULAC
  • 斯坦福大学中文CoreNLP
  • 复旦大学的Fnlp
  • 中科院的ICTCLAS。

6. Ref

  1. https://www.cnblogs.com/baiboy/p/jieba2.html
  2. https://zhuanlan.zhihu.com/p/40502333
  3. https://www.jianshu.com/p/0eee07a5bf38
  4. https://zhuanlan.zhihu.com/p/137802990
机器学习 腾讯云TI平台 机器学习平台 深度学习 NLP服务

0 人点赞