Nianwen Xue在《Chinese Word Segmentation as Character Tagging》中将中文分词视作为序列标注问题（sequence tagging problem），由此引入监督学习算法来解决分词问题。

1. HMM

首先，我们将简要地介绍HMM（主要参考了李航老师的《统计学习方法》）。HMM包含如下的五元组：

• 状态值集合[Math Processing Error]Q={q1,q2,⋯,qN}，其中[Math Processing Error]N为可能的状态数；
• 观测值集合[Math Processing Error]V={v1,v2,⋯,vM}，其中[Math Processing Error]M为可能的观测数；
• 转移概率矩阵[Math Processing Error]A=[aij]，其中[Math Processing Error]aij表示从状态[Math Processing Error]i转移到状态[Math Processing Error]j的概率；
• 发射概率矩阵（在[2]中称之为观测概率矩阵）[Math Processing Error]B=[bj(k)]，其中[Math Processing Error]bj(k)表示在状态[Math Processing Error]j的条件下生成观测[Math Processing Error]vk的概率；
• 初始状态分布[Math Processing Error]π.

一般地，将HMM表示为模型[Math Processing Error]λ=(A,B,π)，状态序列为[Math Processing Error]I，对应测观测序列为[Math Processing Error]O。对于这三个基本参数，HMM有三个基本问题：

• 概率计算问题，在模型[Math Processing Error]λ下观测序列[Math Processing Error]O出现的概率；
• 学习问题，已知观测序列[Math Processing Error]O，估计模型[Math Processing Error]λ的参数，使得在该模型下观测序列[Math Processing Error]P(O|λ)最大；
• 解码（decoding）问题，已知模型[Math Processing Error]λ与观测序列[Math Processing Error]O，求解条件概率[Math Processing Error]P(I|O)最大的状态序列[Math Processing Error]I。

2. 中文分词

将状态值集合[Math Processing Error]Q置为[Math Processing Error]{B,E,M,S}，分别表示词的开始、结束、中间（begin、end、middle）及字符独立成词（single）；观测序列即为中文句子。比如，“今天天气不错”通过HMM求解得到状态序列“B E B E B E”，则分词结果为“今天/天气/不错”。

通过上面例子，我们发现中文分词的任务对应于解码问题：对于字符串[Math Processing Error]C={c1,⋯,cn}，求解最大条件概率

[Math Processing Error]maxP(t1,⋯,tn|c1,⋯,cn)

其中，[Math Processing Error]ti表示字符[Math Processing Error]ci对应的状态。应如何求解状态序列呢？解决的办法便是Viterbi算法；其实，Viterbi算法本质上是一个动态规划算法，利用到了状态序列的最优路径满足这样一个特性：最优路径的子路径也一定是最优的。定义在时刻[Math Processing Error]t状态为[Math Processing Error]i的概率最大值为[Math Processing Error]δt(i)，则有递推公式：

[Math Processing Error](1)δt+1(i)=max[δt(j)aji]bi(ot+1)

其中，[Math Processing Error]ot+1即为字符[Math Processing Error]ct+1。

3. 开源实现Jieba

以下的源码分析基于Jieba 0.36版本。

Jieba的jieba.finalseg实现HMM中文分词。prob_start.py定义初始状态分布[Math Processing Error]π：

P={'B': -0.26268660809250016,

 'E': -3.14e+100,

 'M': -3.14e+100,

 'S': -1.4652633398537678}

prob_trans.py转移概率矩阵[Math Processing Error]A：

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}}

prob_emit.py定义了发射概率矩阵[Math Processing Error]B，比如，P("和"|M)表示状态为M的情况下出现“和”这个字的概率；

P={'B': {'一': -3.6544978750449433,

       '丁': -8.125041941842026,

       '七': -7.817392401429855,

    ...}

 'S': {':': -15.828865681131282,

       '一': -4.92368982120877,

       ...}

 ...}

关于训练模型的生成，作者在这里有解释，来源主要有两个：标准的切分语料 + ICTCLAS切分的txt小说。还有一个大家可能会疑惑的问题，为什么Jieba中的概率矩阵中出现了负数？不急，我们先来看看Viterbi算法的实现——jieba.finalseg.viterbi函数：

PrevStatus = {

    'B': 'ES',

    'M': 'MB',

    'S': 'SE',

    'E': 'BM'

}



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])

为了适配中文分词任务，Jieba对Viterbi算法做了如下的修改：

• 状态转移时应满足PrevStatus条件，即状态[Math Processing Error]B的前一状态只能是[Math Processing Error]E或者[Math Processing Error]S，...
• 最后一个状态只能是[Math Processing Error]E或者[Math Processing Error]S，表示词的结尾。

与此同时，Jieba在实现公式[Math Processing Error](1)时，对其求对数，将相乘转化成了相加：

[Math Processing Error]ln⁡δt+1(i)=max{ln⁡δt(j)+ln⁡aji+ln⁡bi(ot+1)}

这就回答了上面的问题——为什么概率矩阵中出现了负数，是因为对其求了对数。

Jieba的HMM分词：

from jieba.finalseg import cut



sentence = "小明硕士毕业于中国科学院计算所，后在日本京都大学深造"

print('/'.join(cut(sentence)))

分词结果为“小明/硕士/毕业于/中国/科学院/计算/所/，/后/在/日/本京/都/大学/深造”，我们发现：关于“日本京都”出现分词错误的情况。这是因为最大条件概率[Math Processing Error]P(I|O)对应的状态序列不一定是分词正确的标注序列。此外，HMM做了两个基本假设：

• 齐次Markov性假设，即任意时刻t的状态仅与前一时刻状态相关，与其他时刻的状态、时刻t均无关；
• 观测独立性假设，任意时刻t的观测仅依赖于该时刻HMM的状态，与其他的观测及状态均无关。

然而，在中文字符串中，字符[Math Processing Error]ct不仅与前一字符[Math Processing Error]ct−1相关，与前面的若干字符都有关系。正因如此，纯粹地采用HMM做中文分词始终存在着分词不准确的情况。

4. 参考资料

[1] Xue, Nianwen. "Chinese word segmentation as character tagging." Computational Linguistics and Chinese Language Processing 8.1 (2003): 29-48.
[2] 李航. "统计学习方法." 清华大学出版社, 北京 (2012).
[3] Itenyh, Itenyh版-用HMM做中文分词二：模型准备.
[4] Django梦之队, 对Python中文分词模块结巴分词算法过程的理解和分析.（源链接挂了，为转载链接）