HMM 模型在 jieba 分词流程中的作用

jieba 在经过第一轮以已知词典为基础的分词之后，默认会通过 HMM 模型（隐马尔可夫模型）对第一轮分词后产生的连续的独立单字进行概率拼词，来完成对于未知词（OOV）的预测。

HMM 模型的思路是，通过概率计算为每一个字打上一个位置标签，位置标签有以下四种：

  • B: 即 Begin，意为词的开头
  • M: 即 Middle，意为词的中间
  • E: 即 End，意为词的结尾
  • S: 即 Single，意为单字成词

HMM 模型的核心依托于 viterbi 算法实现

注：为了避免极小 float 概率数值连乘导致下溢，无法比较浮点数大小，所以在计算时全部采用的是 对数概率和 替代 概率连乘 进行运算。下文中 对数概率 统一简写为 概率，不再进行额外说明。

viterbi 算法核心原理

通过预先定义的三张概率表（首字概率、转移概率、发射概率）计算输入的连续单字列表中的各个字在各种标签组合下的概率和最大的作为最优路径完成新词预测。

首字概率：“BMES” 四个标签作为首字的概率，是标签级别概率，这个概率是固定的，所有字统一，定义在 /jieba/finalseg/prob_start.py 文件中）

P={'B': -0.26268660809250016,

    'E': -3.14e+100,

    'M': -3.14e+100,

    'S': -1.4652633398537678}

转移概率：当前字的某个标签 → 下一个字的某个标签 的概率，同样为标签级别概率，表示标签之前跳转的概率数值，与具体字无关，该数值一样为固定数值，配置在 /jieba/finalseg/prob_trans.py 文件中。

例如：“直聘” 二字中 “直” 为 B 标签， → “聘” 为 E 标签，转移概率即 P(B → E) = -0.510825623765990。

P={'B': {'E': -0.510825623765990, 'M': -0.916290731874155},

 'E': {'B': -0.5897149736854513, 'S': -0.8085250474669937},

 'M': {'E': -0.33344856811948514, 'M': -1.2603623820268226},

 'S': {'B': -0.7211965654669841, 'S': -0.6658631448798212}}

发射概率：当前字在 “BMES” 四个标签下每个标签下对应的概率。这个是一张巨大的概率配置表，存储了常用汉字在各个标签下的出现概率。这是 viterbi 算法判断对应字的标签的核心概率表。

注：若某个字并没有被定义在发射概率表中，则其发射概率默认取值为 MIN_FLOAT = -3.14e100

from __future__ import unicode_literals

  

P={'B': {'\u4e00': -3.6544978750449433,  # 一

       '\u4e01': -8.125041941842026,  # 丁

       '\u4e03': -7.817392401429855,  # 七

       '\u4e07': -6.3096425804013165,  # 万

       '\u4e08': -8.866689067453933,  # 丈

       '\u4e09': -5.932085850549891,  # 三

       '\u4e0a': -5.739552583325728,  # 上

       # ...

    }

}

viterbi 算法流程

  1. 先计算连续单字列表的第一个字作为 B 和 S 的概率。

    注：这个步骤，实际上会计算首字在 “BMES” 中各个标签下的首字概率，但是 jieba 源码中首字概率是配置在 /jieba/finalseg/prob_start.py 文件中的固定值。在该文件中 M 和 E 标签的概率被强制设定为了极小 flaot 值，远小于 B 和 S 标签的概率，所以是通过概率直接规避了第一个字作为 M 或 E 出现的可能性。

  2. 从第二个字开始遍历，找截止到当前字的在各个标签下的最优概率路径。

    1. 遍历 “BMES” 中的每个标签
      1. 获取当前标签下，当前字的发射概率 emit_p
      2. 从当前标签允许出现的前置标签中进行循环
        1. 计算 前一个字在对应前置标签下的最优路径概率和 + 前置标签 → 当前标签 的转移概率 + 当签字在当前标签下的发射概率。找所有计算结果中概率和最大的作为最优路径并记录下来
PrevStatus = {

	'B': 'ES',
	
	'M': 'MB',
	
	'S': 'SE',
	
	'E': 'BM'

}
  1. 由于句子必须以 E 或 S 标签结尾，所以仅从最后一个字是 E 标签 或 S 标签的路径中找概率和最大的路径作为最终最优路径返回。

jieba 的 viterbi 算法源码

def viterbi(obs, states, start_p, trans_p, emit_p):

    V = [{}]  # tabular

    path = {}

    for y in states:  # init

        V[0][y] = start_p[y] + emit_p[y].get(obs[0], MIN_FLOAT)

        path[y] = [y]

    for t in xrange(1, len(obs)):

        V.append({})

        newpath = {}

        for y in states:

            em_p = emit_p[y].get(obs[t], MIN_FLOAT)

            (prob, state) = max(

                [(V[t - 1][y0] + trans_p[y0].get(y, MIN_FLOAT) + em_p, y0) for y0 in PrevStatus[y]])

            V[t][y] = prob

            newpath[y] = path[state] + [y]

        path = newpath

  

    (prob, state) = max((V[len(obs) - 1][y], y) for y in 'ES')

  

    return (prob, path[state])

Viterbi 算法流程图

flowchart TD A[输入连续单字] --> B[初始化] B --> C[计算首字概率] C --> D[记录路径] subgraph Viterbi循环 F[遍历后续文字] G[遍历标签] H[计算发射概率] I[计算转移概率] J[选择最优路径] end D --> F F --> G G --> H H --> I I --> J J --> G J --> M[从句尾字符为 B 或 S 标签的路径中选取最终最优路径] M --> N[输出标签] N --> O[完成分词]