HMM算法用于分词
一、HMM的典型模型五元组
状态集、观测集、初始状态分布、状态转移矩阵、发射矩阵。
1、状态集
(B, M, E, S)，B代表该字是词语中的起始字，M代表是词语中的中间字，E代表是词语中的结束字，S则代表是单字成词。
2、观测集
就是所有汉字(东南西北你我他…)，甚至包括标点符号所组成的集合。
在HMM模型中文分词中，输入是一个句子(也就是观察序列)，输出是这个句子中每个字的状态值，即状态序列。
3、初始状态分布
每一句话第一个字符的对应状态概率。
在训练阶段参数估计中得到。
如：{'B': -0.48164247830489765,'M': -3.14e+100, 'E': -3.14e+100, 'S': -0.96172723110752845}
可以看到第一个字符的初始状态只能是‘B’和‘S’。
4、转移概率矩阵
状态集STATES={‘B’,‘M’,‘E’,‘S’}之间的转移概率。
在中文分词中状态转移矩阵是一个4*4的矩阵，在训练阶段参数估计中得到。1、统计训练数据中状态转移的频数确定矩阵；2、频数矩阵除以对应每一行状态的统计数得到频率；3、对频率取对数。
如：
{'B': {'B': -3.14e+100, 'M':-1.9594399657636383, 'E': -0.15191340104766693, 'S': -3.14e+100},
'M': {'B': -3.14e+100, 'M':-1.0983633205740504, 'E': -0.40558961540346977, 'S': -3.14e+100},
'E': {'B':-0.78182902092047468, 'M': -3.14e+100, 'E': -3.14e+100, 'S':-0.62312924475978682},
'S': {'B': -0.74289298827998818,'M': -3.14e+100, 'E': -3.14e+100, 'S': -0.81330579119502522}}
可以看到对应状态‘B’后面只能接‘M’和‘E’；状态‘M’后面只能接‘M’和‘E’；状态‘E’后面只能接‘B’和‘S’；状态‘S’后面只能接‘B’和‘S’。
5、发射概率矩阵
每一个字符对应状态集STATES={‘B’,‘M’,‘E’,‘S’}中每一个状态的概率。
通过对训练集每个字符对应状态的频数统计得到。
二、 Viterbi算法
Viterbi算法用在测试阶段对输入文本序列进行标注，输入是观测序列，输出是状态序列，需要借助三个模型参数，分别是初始化矩阵、状态转移矩阵、发射概率矩阵。
被标注的文本是：小明硕士毕业于中国科学院计算所
1、变量定义
二维数组 weight[4][15]——4是状态数(0:B,1:E,2:M,3:S)，15是输入句子的字数。比如 weight[0][2] 代表观测值“硕”字被标注为状态值B的概率。
二维数组 path[4][15]——4是状态数(0:B,1:E,2:M,3:S)，15是输入句子的字数。比如 path[0][2] 代表 weight[0][2]取到最大值时，前一个字的状态，比如 path[0][2] = 1, 则代表 weight[0][2]取到最大时，前一个字(也就是“明”)的状态是E。记录前一个字的状态是为了使用viterbi算法计算完整个 weight 之后，能对输入句子从右向左地回溯回来，找出对应的状态序列。
2、变量初始化
weight[0][0]，weight[1][0]，weight[2][0]，weight[3][0]要被初始化，分别代表第0个词“小”被标注为B、E、M、S的概率。根据初始状态分布和发射概率矩阵求解。
初始状态分布
B:-0.26268660809250016
E:-3.14e+100
M:-3.14e+100
S:-1.4652633398537678
发射概率矩阵可以得出
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
注意上式计算的时候是相加而不是相乘，因为之前取过对数的原因。
3、变量求解
tmp=weight[k][i-1] + _transProb[k][j] + _emitProb[j][sentence[i]];
后一个字的标注取{B,E,M,S}的概率weight与前一个字的标注取{B,E,M,S}的概率weight有关。后一个字的weight要根据前一个字的weight去推断。
4、确定边界条件和路径回溯
对于每个句子，最后一个字的状态只可能是 E 或者 S，不可能是 M 或者 B。
所以在本文的例子中只需要比较 weight[1][14] 和 weight[3][14] 的大小即可，即最后一个字标注为E和S的概率谁大。
在本例中weight[1][14] < weight[3][14]，即 S > E，也就是说第14字(最后一个字)的标注是S。path[3][14]的取值代表第14个字标注为S(3)时，前一个字(第13个字)的标注。所以回溯的起点就是path[3][14]。
回溯的路径是:
SEBEMBEBEMBEBEB
倒序一下就是:
BE/BE/BME/BE/BME/BE/S
所以切词结果就是:
小明/硕士/毕业于/中国/科学院/计算/所
三、代码实现
1、语料信息
首先，需要一个完整的语料信息，该语料库需要：
1）覆盖范围广。
理论上需要覆盖你所有可能会被分词的文字，否则发射矩阵为出现极端情况，无法分词。
2）需要文本标注正确。
如一些专有名词，"太平洋保险"等等，需要被分为一个词，因为他是一个公司名称，而不应该被分为"太平洋/保险"。
提取该语料库，可能需要人工干预。
将分词的结果进行标注，按照上文提到的信息，打上SBME的标注（方便起见，这里直接用jieba分词的结果）：
2、计算初始状态概率分布
ME是不会出现在句首，即将其概率设置为0，在矩阵中为：-3.14e+100（取了log值）。
3、计算转移概率矩阵
其中有一些是不可能转移的信息，如：B->S，E->M等等，将这些情况的概率的log值设置为-3.14e+100。其他的按照词前后的状态序列统计，统计前后之间的关系，这里已知假设，当前状态仅与前一状态有关，与更前面的状态无关。所以，思路：
内容按照/拆分->取出状态序列->分拆为2元组->统计前一状态出现后一状态的概率
4、计算发射概率矩阵
内容按照/拆分->取出状态：观测的key：value->统计某状态下，某观测出现的次数，即为概率值。某状态下，所有观测出现的概率和为1。（拿到一个盒子，所有球出现的概率和为1）
5、使用Viterbi算法
HMM+Viterbi实现中文分词，代码见HMM中文分词
