前言 在谈谈中文分词基本问题 我们讨论过基于词典的分词和基于字的分词两大类，在NLP中经典的词典分词方法解析 文中我们利用n-gram实现了基于词典的分词方法。其中，我们也讨论了这种方法的缺陷，就是OOV的问题，即对于未登录词会失效在，并简单介绍了如何基于字进行分词，本文着重阐述下如何利用HMM实现基于字的分词方法。
隐马尔可夫模型 首先，我们将简要地介绍HMM（Hidden Markov Model）。HMM包含如下的五元组：
状态值集合Q={q1,q2,…,qN}，其中N为可能的状态数；
观测值集合V={v1,v2,…,vM}，其中M为可能的观测数；
转移概率矩阵A=[aij]，其中aij表示从状态i转移到状态j的概率；
发射概率矩阵（也称之为观测概率矩阵）B=[bj(k)]，其中bj(k)表示在状态j的条件下生成观测vk的概率；
初始状态分布π.
一般地，将HMM表示为模型λ=(A,B,π)，状态序列为I，对应测观测序列为O。对于这三个基本参数，HMM有三个基本问题：
HMM分词 在（1）中我们已经讨论过基于字分词，是如何将分词转换为标签序列问题，这里我们简单阐述下HMM用于分词的相关概念。将状态值集合Q置为{B,E,M,S}，分别表示词的开始、结束、中间（begin、end、middle）及字符独立成词（single）；观测序列即为中文句子。比如，“今天天气不错”通过HMM求解得到状态序列“B E B E B E”，则分词结果为“今天/天气/不错”。
其中，ti表示字符ci对应的状态。
两个假设 在求条件概率
我们利用贝叶斯公式可得
类似于n-gram的情况，我们需要作出两个假设来减少稀疏问题：
即如下：
这样我们就可以将上面的式子转化为：
而在我们的分词问题中状态T只有四种即{B,E,M,S}，其中P(T)可以作为先验概率通过统计得到，而条件概率P(C|T)即汉语中的某个字在某一状态的条件下出现的概率，可以通过统计训练语料库中的频率得出。
Viterbi算法 有了以上东东，我们应如何求解最优状态序列呢？解决的办法便是Viterbi算法；其实，Viterbi算法本质上是一个动态规划算法，利用到了状态序列的最优路径满足这样一个特性：最优路径的子路径也一定是最优的。定义在时刻t状态为i的概率最大值为δt(i)，则有递推公式：
其中，ot+1即为字符ct+1。
代码实现 我们基于HMM实现一个简单的分词器，这里我主要从jieba分词中抽取了HMM的部分，具体逻辑如下：
1 P={'B' : -0.26268660809250016,2 'E' : -3.14e+100,3 'M' : -3.14e+100,4 'S' : -1.4652633398537678}
prob_trans.py转移概率矩阵A：
1 P={'B' : {'E' : -0.510825623765990, 'M' : -0.916290731874155},2 'E' : {'B' : -0.5897149736854513, 'S' : -0.8085250474669937},3 'M' : {'E' : -0.33344856811948514, 'M' : -1.2603623820268226},4 'S' : {'B' : -0.7211965654669841, 'S' : -0.6658631448798212}}prob_emit.py定义了发射概率矩阵B，比如，P('和'|M)表示状态为M的情况下出现“和”这个字的概率（注：在实际的代码中汉字都用unicode编码表示）；
1 P={'B' : {'一' : -3.6544978750449433 ,2 '丁' : -8.125041941842026 ,3 '七' : -7.817392401429855 ,4 ... }5 'S' : {':' : -15.828865681131282 ,6 '一' : -4.92368982120877 ,7 ... }8 ... }
关于模型的训练作者给出了解解释：“来源主要有两个，一个是网上能下载到的1998人民日报的切分语料还有一个msr的切分语料。另一个是我自己收集的一些txt小说，用ictclas把他们切分（可能有一定误差）。 然后用python脚本统计词频。要统计的主要有三个概率表：1)位置转换概率，即B（开头）,M（中间),E(结尾),S(独立成词）四种状态的转移概率；2）位置到单字的发射概率，比如P('和'|M)表示一个词的中间出现”和'这个字的概率；3) 词语以某种状态开头的概率，其实只有两种，要么是B，要么是S。”
在seg_hmm.py中viterbi函数如下：
1 PrevStatus = { 2 'B': 'ES', 3 'M': 'MB', 4 'S': 'SE', 5 'E': 'BM' 6 } 7 8 def viterbi(obs, states, start_p, trans_ p, emit_p): 9 V = [{}] # tabular10 path = {}11 for y in states: # init12 V[0 ][y ] = start_p[y] + emit_ p[y].get(obs[0], MIN_FLOAT)13 path[y] = [y]14 for t in range(1, len(obs)):15 V.append({})16 newpath = {}17 for y in states:18 em_p = emit_ p[y].get(obs[t], MIN_FLOAT)19 (prob, state) = max(20 [(V[t - 1 ][y0 ] + trans_p[y0].get(y, MIN_ FLOAT) + em_p, y0) for y0 in PrevStatus[y]])21 V[t ][y ] = prob22 newpath[y] = path[state] + [y]23 path = newpath24 25 (prob, state) = max((V[len(obs) - 1 ][y ], y) for y in 'ES')26 27 return (prob, path[state])为了适配中文分词任务，Jieba对Viterbi算法做了如下的修改：
与此同时，这里在实现地推公式时，对其求对数，将相乘转化成了相加：
这也就是概率矩阵中出现了负数，是因为对其求了对数。
实现效果 我们写一个简单的自测函数：
1 if __name__ == '__main__' : 2 ifile = '' 3 ofile = '' 4 try : 5 opts, args = getopt.getopt(sys.argv[1 :], 'hi:o:' , ['ifile=' , 'ofile=' ]) 6 except getopt.GetoptError: 7 print('seg_hmm.py -i <inputfile> -o <outputfile>' ) 8 sys.exit(2 ) 9 for opt, arg in opts:10 if opt == '-h' :11 print('seg_hmm.py -i <inputfile> -o <outputfile>' )12 sys.exit()13 elif opt in ('-i' , '--ifile' ):14 ifile = arg15 elif opt in ('-o' , '--ofile' ):16 ofile = arg17 18 with open(ifile, 'rb' ) as inf:19 for line in inf:20 rs = cut(line)21 print(' ' .join(rs))22 with open(ofile, 'a' ) as outf:23 outf.write(' ' .join(rs) + '\n' )
运行如下：
完整代码 我提炼了完整的代码放到了github上，大家可以看看HMM分词方法的语料到模型，再到最终分词预测的整个流程：
看完，赶紧点个“好看”鸭
点鸭点鸭
