这篇博客主要阐述我们在分词任务中常用的分词库结巴jieba分词的实现原理,以及之前博客中讲到的HMM在分词中的应用,算是复习与加深理解一下HMM的知识。jieba分词作为一个十年前的分词库,更新到现在依然还是非常好用而且也很经典适合学习。
看了这么多可能还是跟我一样一头雾水,可以跟着一起看看每一步的具体实现。
结巴分词自带了一个叫做dict.txt
的词典,里面有349046
条词,其每行包含了词条
、词条出现的次数
(这个次数是结巴作者基于人民日报语料等资源训练得出来的)和词性
,如下图所示。
在基于词典的中文分词方法中,词典匹配算法是基础。为了保证切分速度,需要选择一个好的查找词典算法。
这里介绍词典的Trie树组织结构。基于前缀词典实现的词图扫描,就是把这34万多条词语,放到一个trie树的数据结构中,trie树也叫前缀树或字典树,也就是说一个词语的前面几个字一样,就表示他们具有相同的前缀,就可以使用trie树来存储,具有查找速度快的优势。
一个搜索数字的trie树的一个节点只保留一个字符。如果一个单词比一个字符长,则包含第个字符的节点有指针指向下一个字符的节点,以此类推。这样组成一个层次结构的树,树的第一层包括所有单词的第一个字符,树的第二层包括所有单词的第二个字符,以此类推。很显然,trie树的最大高度是词典中最长单词的长度。
DAG有向无环图,就是后一句中的生成句子中汉字所有可能成词情况所构成的有向无环图
,这个是说,给定一个待分词的句子,将它的所有词匹配出来,构成词图,即是一个有向无环图DAG,如下图所示:
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中都是词语。
作者的代码中将字典在生成trie树的同时,也把每个词的出现次数转换为了频率。频率其实也是一个0~1之间的小数,是事件出现的次数/实验中的总次数
,因此在试验次数足够大的情况下,频率约等于概率,或者说频率的极限就是概率。
动态规划中,先查找待分词句子中已经切分好的词语,对该词语查找该词语出现的频率(次数/总数),如果没有该词(既然是基于词典查找,应该是有可能没有该词),就把词典中出现频率最小的那个词语的频率作为该词的频率。也就是说,P(某词语)=FREQ.get(‘某词语’, min_freq)
, 然后根据动态规划查找最大概率路径。对句子从右往左反向计算最大概率(也可以是从左往右,这里反向是因为汉语句子的重心经常落在后面,就是落在右边,主要是因为在通常情况下形容词太多,后面的才是主干,因此,从右往左计算,正确率要高于从左往右计算,类似于逆向最大匹配的分词方法)
所以状态转移方程为
P(NodeN)=1.0, P(NodeN-1)=P(NodeN)*Max(P(倒数第一个词))
,依次类推,最后得到最大概率路径,即得到最大概率的切分组合。
所以在上图DAG中,得到的最大切分组合是有-意见-分歧,即0-1-3-5
未登录词(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
中,下面为表中内容;
{'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序列
复习一下,HMM的典型模型是一个五元组:
HMM模型的三个基本假设如下:
回到正题,在结巴分词中五元组分别为:
给你一个隐马尔科夫链的例子。
可以标注为:给/S 你/S 一个/BE 隐马尔科夫链/BMMMME 的/S 例子/BE 。/S
B -0.26268660809250016 E -3.14e+100 M -3.14e+100 S -1.4652633398537678
数值是对概率值取【对数】之后的结果(可以让概率【相乘】的计算变成对数【相加】)。其中-3.14e+100作为负无穷,也就是对应的概率值是0。
也就是句子的第一个字属于{B,E,M,S}这四种状态的概率
这五元的关系是通过一个叫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 之后,能对输入句子从右向左地回溯回来,找出对应的状态序列。
具体代码实现如下:
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
所以切词结果就是:
小明/硕士/毕业于/中国/科学院/计算/所
这里可以通过理解上文提到的所有,进行分词。
维特比算法是基于动态规划思想的隐马尔科夫模型解法。动态规划原理提到,假设存在一条最优路径,那么将该路径切分成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)
jieba分词都是调用jieba.cut 这个函数,cut函数即是分词的入口,这个函数在文件jieba/__init__.py ,代码如下:
#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函数来绘制出相应的流程图
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。