在做文本处理的时候，首先要做的预处理就是分词。英文单词天然有空格隔开容易按照空格分词，但是也有时候需要把多个单词做为一个分词，比如一些名词如“New York”，需要做为一个词看待。而中文由于没有空格，分词就是一个需要专门去解决的问题了。无论是英文还是中文，分词的原理都是类似的。
简单而言，汉语自动分词就是让计算机系统在汉语文本中的词与词之间自动加上空格或其他边界标记。虽然听起来简单，但是到目前为止，对于“词”这个概念，依然有一些基本问题像“什么是词”“词是什么”没有确切的答案。有关调研表明，即使母语是汉语，对汉语文本中出现的词语的认同率大概只有70%。因此，从严格意义上将，自动分词是一个没有明确定义的问题。
分词中的基本问题
分词中涉及到三个基本问题：分词规范、歧义切分和未登录词的识别。
分词规范
我们从小学习汉语开始，基本顺序就是汉字->词语->句子->段落->篇章，而其中词是什么，什么是词语，这个问题看似有些莫名其妙，但是如何界定一个词语却是分词中一个很重要的话题。
“小明看到湖岸上的花草，一株不知名的小花引起了他的注意”
对于这句话中的“湖岸”、“花草”、“不知名”等，不同的词语界定方式就会出现不一样的分词结果，如我们可以切分成以下几种形式：
- “小明/看到/湖岸/上/的/花草/，一株/不知名/的/小花/引起/了/他的/注意”
- “小明/看到/湖/岸/上/的/花/草，一株/不/知名/的/小花/引起了/他的/注意”
- “小明/看到/湖岸/上的/花/草，一株/不知名的/小花/引起了/他的/注意”
我们可以看出不同的词语界定方式，可以组合出很多种分词结果，所以说分词可以看做是找寻一个没有明确定义问题的答案。所以当我们在衡量一个分词模型的好坏时，我们首先需要确定一个统一的标准，即所谓Golden Data，大家所有的模型都在统一的数据集上进行训练和评测，这样比较才会具有可参考性。
歧义切分
歧义字段在汉语中是普遍存在的，而歧义字段是汉语切分的一个重要难点。梁南元最早对歧义字段进行了两种基本的定义：
- 交集型切分歧义：汉字串AJB称作交集型切分歧义，如果满足AJ、JB同时为词（A、J、B分别为汉字串）。此时汉字串J称作交集串。如，大学生（大学/学生）、研究生物（研究生/生物）、结合成（结合/合成）.
- 组合型切分歧义：汉字串AB称作多义组合型切分歧义，如果满足A、B、AB同时为词。如，起身（他|站|起|身|来/明天|起身|去北京）、学生会（我在|学生会|帮忙/我的|
学生|会来|帮忙）
我们可以看出歧义字段给我们的分词问题带来了极大的困扰，所以想要正确的做出切分判断，一定要结合上下文语境，甚至韵律、语气、重音、停顿等。
未登录词识别
未登录词，一种是指已有的词表中没有收录的词，另一种是指训练语料中未曾出现过的词。而后一种含义也可以被称作集外词，OOV（out of vocabulary），即训练集以外的词。通常情况下未登录词和OOV是一回事，我们这里不加以区分。
未登录词大体可以分为如下几个类型：
- 新出现的普通词汇，如网络用语当中层出不穷的新词，这在我们的分词系统这种也是一大挑战，一般对于大规模数据的分词系统，会专门集成一个新词发现模块，用于对新词进行挖掘发现，经过验证后加入到词典当中。
- 专有名词，在分词系统中我们有一个专门的模块，命名体识别（NER name entity recognize），用于对人名、地名以及组织机构名等单独进行识别。
- 专业名词和研究领域名称，这个在通用分词领域出现的情况比较少，如果出现特殊的新领域，专业，就会随之产生一批新的词汇。
- 其他专用名词，包含其他新产生的产品名、电影、书籍等等。
经过统计汉语分词出现问题更多是由于未登录词造成的，那么分词模型对于未登录词的处理将是衡量一个系统好坏的重要指标。
常用的汉语分词方法
自从汉语自动分词的问题被提出来以后，人们提出了很多分词方法，有文献介绍了16中不同的分词方法，包括正向最大匹配法（forward maximum matching method，FMM），逆向最大匹配法（Backward maximum matching method，BMM），双向扫描法等。这些方法基本上都是在上世纪80年代左右提出来的，大多数都是基于词表（词典）进行的。因此，一般称为基于词表（词典）的分词方法。后来随着统计方法的迅速发展，人们又提出来基于统计模型（HMM 和 n元语法）的分词方法，以及规则方法和统计方法相结合的分词技术。
基于词典的方法是经典的传统分词方法，这种方式很直观，我们从大规模的训练语料中提取分词词库，并同时将词语的词频统计出来，我们可以通过逆向最大匹配、N-最短路径等分词方法对句子进行切分。基于词典的分词方法非常直观，可以很容易的通过增减词典来调整最终的分词效果，比如当我们发现某个新出现的名词无法被正确切分的时候，我们可以直接在词典当中进行添加，以达到正确切分的目的；同样的过于依赖于词典也导致这种方法对于未登录词的处理不是很好，并且当词典当中的词出现公共子串的时候，就会出现歧义切分的问题，这需要语料库足够的丰富，从而能够对每个词的频率有一个很好的设置。
不同于基于词典的分词方法，需要依赖于一个事先编制好的词典，通过查词典的方式作出最后的切分决策；基于字的分词方法将分词过程看作是字的分类问题，其认为每个字在构造一个特定词语时都占据着一个确定的构词位置（词位）。这种方法最早由薛念文等人于2002年提出，并在各种分词大赛上取得了不错的成绩，尤其是对未登录词问题的处理，召回率一直很高。
一般情况下，我们认为每个字的词位有4种情况：B（Begin）、E（End）、M（Middle）、S（Single），那么我们对于一个句子的切分就可以转为对句子中每个字打标签的过程，举个例子：
- 自然语言处理/可以/应用/在/诸多/领域。
- 自B 然M 语M 言M 处M 理E 可B 以E 应B 用E 在S 诸B 多E 领B 域E。
我们对句子中的每个字赋予了一个词位，即BEMS中的一个标签，这样我们就完成了分词的目的。
基于字的方法将传统的语言学问题转换为了一个更加容易建模的序列标注问题，我们可以用最大熵模型为每个字进行标签分类；也可以利用HMM将其看作一个解码问题；或者考虑句子间的时序关系，利用判别模型CRF来建模；同样深度学习中的LSTM也可以用在这里进行建模。
中文分词工具
有一些比较好的开源的中文分词工具，参考6中列出了常用的6个中文分词工具的对比。上面的基于词典和基于字的方法就是结合Jieba分词工具介绍的。
首先看一下Jieba的使用。jieba源代码在github上开源，作者一直在维护，有很多issue，而且与时俱进，现在已经用上了神经网络。
支持四种分词模式：
- 精确模式，试图将句子最精确地切开，适合文本分析；
- 全模式，把句子中所有的可以成词的词语都扫描出来, 速度非常快，但是不能解决歧义；
- 搜索引擎模式，在精确模式的基础上，对长词再次切分，提高召回率，适合用于搜索引擎分词。
- paddle模式，利用PaddlePaddle深度学习框架，训练序列标注（双向GRU）网络模型实现分词。
目前先看看前三种方式的使用。有一些有意思的现象。
jieba分词对已收录词和未收录词都有相应的算法进行处理，其处理的思路很简单，当然，过于简单的算法也是制约其召回率的原因之一。
其主要的处理思路如下：
- 加载词典dict.txt
- 从内存的词典中构建该句子的DAG（有向无环图）
- 对于词典中未收录词，使用HMM模型的viterbi算法尝试分词处理
- 已收录词和未收录词全部分词完毕后，使用dp寻找DAG的最大概率路径
- 输出分词结果
语料库和词典
jieba分词模型使用了一些语料来做训练集，在https://github.com/fxsjy/jieba/issues/7 中，作者说
来源主要有两个，一个是网上能下载到的1998人民日报的切分语料还有一个msr的切分语料。另一个是我自己收集的一些txt小说，用ictclas把他们切分（可能有一定误差）。 然后用python脚本统计词频。 jieba分词的默认语料库选择看起来满随意，作者也吐槽高质量的语料库不好找，所以如果需要在生产环境使用jieba分词，尽量自己寻找一些高质量的语料库来做训练集。
语料库中所有的词语被用来做两件事情：
- 对词语的频率进行统计，作为登录词使用
- 对单字在词语中的出现位置进行统计，使用BMES模型进行统计，供后面套HMM模型Viterbi算法使用。
统计后的结果保存在dict.txt中，摘录其部分结构如下：
上访 212 v
上访事件 3 n
上访信 3 nt
上访户 3 n
上访者 5 n
上证 120 j
上证所 8 nt
上证指数 3 n
上证综指 3 n
上诉 187 v
上诉书 3 n
上诉人 3 n
上诉期 3 b
上诉状 4 n
上课 650 v其中，第一列是中文词语，第二列是词频，第三列是词性，jieba分词现在的版本除了分词也提供词性标注等其他功能，这个不在本文讨论范围内，可以忽略第三列。jieba分词所有的统计来源，就是这个语料库产生的两个模型文件。
接下来我们看看为什么分词工具有这样的表现。如果有时间，可以直接分析jieba的源代码。
首先看一下基于词典的方法；然后基于统计的方法，我们讨论一下HMM。
正向最大匹配思想MM
- 从左向右取待切分汉语句的m个字符作为匹配字段，m为大机器词典中最长词条个数。
2. 查找大机器词典并进行匹配。若匹配成功，则将这个匹配字段作为一个词切分出来。
若匹配不成功，则将这个匹配字段的最后一个字去掉，剩下的字符串作为新的匹配字段，进行再次匹配，重复以上过程，直到切分出所有词为止。
逆向最大匹配算法RMM
该算法是正向最大匹配的逆向思维，匹配不成功，将匹配字段的最前一个字去掉，实验表明，逆向最大匹配算法要优于正向最大匹配算法。
双向最大匹配法(Bi-directction Matching method,BM)
双向最大匹配法是将正向最大匹配法得到的分词结果和逆向最大匹配法的到的结果进行比较，从而决定正确的分词方法。据SunM.S. 和 Benjamin K.T.（1995）的研究表明，中文中90.0％左右的句子，正向最大匹配法和逆向最大匹配法完全重合且正确，只有大概9.0％的句子两种切分方法得到的结果不一样，但其中必有一个是正确的（歧义检测成功），只有不到1.0％的句子，或者正向最大匹配法和逆向最大匹配法的切分虽重合却是错的，或者正向最大匹配法和逆向最大匹配法切分不同但两个都不对（歧义检测失败）。这正是双向最大匹配法在实用中文信息处理系统中得以广泛使用的原因所在。
这个思想很简单，相对应的代码，也比较简单。以下代码参考：
# -*- coding:utf8 -*-
import codecs
import string
import re
import sys
def load_dict(filename):
f = open(filename,'r',encoding="utf-8").read()
maxLen = 1
dict=f.split("\n")
for i in dict:
if len(i)>maxLen:
maxLen=len(i)
return dict,maxLen;
#分词 返回分好的列表
def maxlen_segmentation(dict,maxLen,sentence,foreward=True):
wordList=[] #结果
i=0
j=0
while(len(sentence)>0):
n = len(sentence)
if foreward:
word=sentence[0:maxLen]
else:
word=sentence[n-maxLen:n]
found=False; #是否找到词
while((not found) and (len(word)>0)):
if(word in dict): #命中
wordList.append(word+' ')
print("命中 %s"%word)
i+=len(word)
if foreward:
sentence=sentence[len(word):n]#后移
else:
sentence=sentence[0:n-len(word)]#前移
#print("下一个 %s"%sentence)
#input();
found=True;
else:
#当词长为1时,强行命中
if(len(word)==1):
wordList.append(word+'\n')
#print("单字 %s"%word)
i+=len(word)
if foreward:
sentence=sentence[len(word):n]#后移
else:
sentence=sentence[0:n-len(word)]#前移
#print("下一个 %s"%sentence)
#input();
found=True;
else:
if foreward:
word=word[0:len(word)-1]
else:
word=word[1:len(word)]
#print(word)
return wordList
def mAIn():
"""if len(sys.argv)!=3:
print('用法：seg.py 词典文件名 输入文件名')
return
"""
#dict,maxLen=load_dict(sys.argv[1])
dict,maxLen=load_dict("dict.txt")
#strIn = open(sys.argv[2],encoding="utf-8").read()
strIn = open("in.txt", encoding="utf-8").read()
print("开始分词...\n")
f_result=maxlen_segmentation(dict,maxLen,strIn,True)
b_result=maxlen_segmentation(dict,maxLen,strIn,False)
print('前向最大匹配分词：%d个词'%len(f_result))
print('后向最大匹配分词：%d个词'%len(b_result))
open('foreward.txt','w',encoding="utf-8").writelines(f_result)
open('backward.txt','w',encoding="utf-8").writelines(b_result[::-1])
print('结果已保存在foreward.txt backward.txt')
if __name__ == '__main__':
main()看一下运行效果。
前向效果：
我 是 中国 人
腾 讯 和 阿里 都 在 新 零售 大举 布局
结婚 的 和尚 未 结婚 的
南京市 长江 大桥
我 在 学生 物后向效果：
我 是 中 国人
腾 讯 和 阿里 都 在 新 零售 大举 布局
结婚 的 和 尚未 结婚 的
南京市 长江 大桥
我 在 学 生物 因为它是基于词典的，所以分词效果的好坏很大程度上取决于词典本身的精确程度。
接下来看一下基于统计的方法。
以下例子来自于参考12和，在此表示感谢。
这里首先介绍下n-gram。
N-gram的第一个特点是某个词的出现依赖于其他若干个词，第二个特点是我们获得的信息越多，预测越准确。正式来说，N-gram模型是一种语言模型（Language Model，LM），语言模型是一个基于概率的判别模型，它的输入是一句话（单词的顺序序列），输出是这句话的概率，即这些单词的联合概率（joint probability）。
N-gram本身也指一个由N个单词组成的集合，各单词具有先后顺序，且不要求单词之间互不相同。常用的有 Bi-gram (N=2) 和 Tri-gram (N=3)，一般已经够用了。例如在上面这句话里，可以分解的 Bi-gram 和 Tri-gram ：
Bi-gram : {I, love}, {love, deep}, {love, deep}, {deep, learning}
Tri-gram : {I, love, deep}, {love, deep, learning}假设一个字符串s由m个词组成，因此我们需要计算出P(w1,w2,⋯,wm)的概率，根据概率论中的链式法则得到如下：
![自然语言处理1：分词 第3张图片]( "自然语言处理1：分词 第3张图片")
直接计算这个概率的难度有点大，因此引入马尔科夫假设（Markov Assumption）：一个词的出现仅与它之前的若干个词有关，即
，其中i为某个词的位置，n为定义的相关的前几个词，因此得到如下：
当n=1时，即一元模型（Uni-gram）
但 n=2时，即二元模型（Bi-gram）
当n=3时，即三元模型（Tri-gram）
N可以取很高，然而现实中一般 bi-gram 和 tri-gram 就够用了；而且N取得太大，会导致参数空间过大和数据稀疏严重等问题，因为词同时出现的情况可能没有。
如何计算其中的每一项条件概率呢？答案是极大似然估计（Maximum Likelihood Estimation，MLE），简单点就是计算频率：
具体地，以Bi-gram为例，我们有这样一个由三句话组成的语料库：
容易统计，“I”出现了3次，“I am”出现了2次，因此能计算概率：
同理，还能计算出如下概率：
另外再提供一个《Language Modeling with Ngrams》中的例子，Jurafsky et al., 1994 从加州一个餐厅的数据库中做了一些统计：
因此算出了“I want chinese food”这句话的概率，但有时候这句话会很长，那么概率（都是小于1的常数）的相乘很可能造成数据下溢（downflow），即很多个小于1的常数相乘会约等于0，此时可以使用log概率解决。
结合jieba分词来看一下n-gram语言模型的应用。
以下内容来自参考8，在此表示感谢。
jieba分词主要是基于统计词典，构造一个前缀词典；然后利用前缀词典对输入句子进行切分，得到所有的切分可能，根据切分位置，构造一个有向无环图；通过动态规划算法，计算得到最大概率路径，也就得到了最终的切分形式。
实例讲解
以“去北京大学玩”为例，作为待分词的输入文本。
离线统计的词典形式如下，每一行有三列，第一列是词，第二列是词频，第三列是词性。这里需要强调一下，北 17860这一项，是'北'这个字，作为单独词素出现的，譬如像'向北走'，类似地，'京'也是像'赴京赶考'这样的情况。
...
北京大学 2053 nt
大学 20025 n
去 123402 v
玩 4207 v
北京 34488 ns
北 17860 ns
京 6583 ns
大 144099 a
学 17482 n
...根据这个词典，可能有多个分词的方法
0 -> 1 -> 2 -> 3 -> 4 -> 5
# 分词结果1
去 / 北 / 京 / 大 / 学 / 玩
# 路径2
0 -> 1 , 2 -> 3 -> 4 -> 5
# 分词结果2
去 / 北京 / 大 / 学 / 玩
# 路径3
0 -> 1 , 2 -> 3 , 4 -> 5
# 分词结果3
去 / 北京 / 大学 / 玩
# 路径4
0 -> 1 , 2 , 3 , 4 -> 5
# 分词结果4
去 / 北京大学 / 玩
...N-gram的思路就是分别计算这些情况的对应的概率。为了高效计算这个概率，基于前缀词典构造DAG，然后使用动态规划从后向前计算每种情况的概率。
前缀词典构建
首先是基于统计词典构造前缀词典，如统计词典中的词“北京大学”的前缀分别是“北”、“北京”、“北京大”；词“大学”的前缀是“大”。统计词典中所有的词形成的前缀词典如下所示，你也许会注意到“北京大”作为“北京大学”的前缀，但是它的词频却为0，这是为了便于后面有向无环图的构建。因为，在后面计算DAG的时候，'北京大’可以作为后面还可以可以到达的词的一个指示，可以结合后面的代码理解。
...
北京大学 2053
北京大 0
大学 20025
去 123402
玩 4207
北京 34488
北 17860
京 6583
大 144099
学 17482
...看一下代码：
for line in f: //f是词典；该for循环用于构造前缀词典
try:
line = line.strip().decode('utf-8')
word, freq = line.split()[:2]
freq = int(freq)
self.wfreq[word] = freq //更新词典中原有词的频率
for idx in range(len(word)):
wfrag = word[:idx + 1]
if wfrag not in self.wfreq:
self.wfreq[wfrag] = 0 # trie: record char in word path
self.total += freq
count += 1
有向无环图构建
有向无环图，directed acyclic graphs，简称DAG，是一种图的数据结构，顾名思义，就是没有环的有向图。下面的图就是一个DAG。
DAG在分词中的应用很广。jieba采用了Python的dict结构，可以更方便的表示DAG。最终的DAG是以{k : [k , j , ..] , m : [m , p , q] , ...}的字典结构存储，其中k和m为词在文本sentence中的位置，k对应的列表存放的是文本中以k开始且词sentence[k: j + 1]在前缀词典中的 以k开始j结尾的词的列表，即列表存放的是sentence中以k开始的可能的词语的结束位置，这样通过查找前缀词典就可以得到词。
0: [0]
1: [1,2,4]
2: [2]
3: [3,4]
4: [4]
5: [5]对于0: [0]，表示位置0对应的词，就是0 ~ 0，就是“去”；对于1: [1,2,4]，表示位置1开始，在1，2，4位置都是词，就是1 ~ 1，1 ~ 2，1 ~ 4，即“北”，“北京”，“北京大学”这三个词。
get_DAG(self, sentence)函数进行对系统初始化完毕后，会构建有向无环图。从前往后依次遍历文本的每个位置，对于位置k，首先形成一个片段，这个片段只包含位置k的字，然后就判断该片段是否在前缀词典中，
1. 如果这个片段在前缀词典中，
1.1 如果词频大于0，就将这个位置i追加到以k为key的一个列表中；
1.2 如果词频等于0，如同第2章中提到的“北京大”，则表明前缀词典存在这个前缀，但是统计词典并没有这个词，继续循环；
2. 如果这个片段不在前缀词典中，则表明这个片段已经超出统计词典中该词的范围，则终止循环；
3. 然后该位置加1，形成一个新的片段，该片段在文本的索引为[k:i+1]，继续判断这个片段是否在前缀词典中。jieba分词中get_DAG函数实现如下，
# 有向无环图构建主函数
def get_DAG(self, sentence):
# 检查系统是否已经初始化
self.check_initialized()
# DAG存储向无环图的数据，数据结构是dict
DAG = {}
N = len(sentence)
# 依次遍历文本中的每个位置
for k in xrange(N):
tmplist = []
i = k
# 位置k形成的片段
frag = sentence[k]
# 判断片段是否在前缀词典中
# 如果片段不在前缀词典中，则跳出本循环
# 也即该片段已经超出统计词典中该词的长度
while i < N and frag in self.wfreq:
# 如果该片段的词频大于0
# 将该片段加入到有向无环图中
# 否则，继续循环
if self.wfreq[frag]:
tmplist.append(i)
# 片段末尾位置加1
i += 1
# 新的片段较旧的片段右边新增一个字
frag = sentence[k:i + 1]
if not tmplist:
tmplist.append(k)
DAG[k] = tmplist
return DAG
以“去北京大学玩”为例，最终形成的有向无环图为，
{0: [0], 1: [1,2,4], 2: [2], 3: [3,4], 4: [4], 5: [5]}对于每一种划分，都将相应的首尾位置相连，例如，对于位置1,可以将它与位置1、位置2、位置4相连接，最终构成一个有向无环图，如下所示，
最大概率路径计算
在得到所有可能的切分方式构成的有向无环图后，我们发现从起点到终点存在多条路径，多条路径也就意味着存在多种分词结果，例如，
# 路径1
0 -> 1 -> 2 -> 3 -> 4 -> 5
# 分词结果1
去 / 北 / 京 / 大 / 学 / 玩
# 路径2
0 -> 1 , 2 -> 3 -> 4 -> 5
# 分词结果2
去 / 北京 / 大 / 学 / 玩
# 路径3
0 -> 1 , 2 -> 3 , 4 -> 5
# 分词结果3
去 / 北京 / 大学 / 玩
# 路径4
0 -> 1 , 2 , 3 , 4 -> 5
# 分词结果4
去 / 北京大学 / 玩
...因此，我们需要计算最大概率路径，也即按照这种方式切分后的分词结果的概率最大。在计算最大概率路径时，jieba分词采用的方式是1-gram，也即每个词的概率相乘。为了计算高效，采用从后往前这种方式进行计算。为什么采用从后往前这种方式计算呢？因为，我们这个有向无环图的方向是从前向后指向，对于一个节点，我们只知道这个节点会指向后面哪些节点，但是我们很难直接知道有哪些前面的节点会指向这个节点。
可以想一下对于“去 北 京 大 学 玩”，如果我们想要从前向后计算到达‘学’字的最大概率，那么必须要知道由前面哪几个字可以到达‘学&#39;字。但是从‘学’字出发计算到‘玩’字的最大概率是可以计算得出的。
在采用动态规划计算最大概率路径时，每到达一个节点，它前面已经计算的节点到终点的最大路径概率已经计算出来。上面构建出的有向无环图DAG的每个节点，都是带权的，对于在前缀词典里面的词语，其权重就是它的词频；我们想要求得route = (w1,w2,w3,...,wn)，使得 ![自然语言处理1：分词 第18张图片]( "自然语言处理1：分词 第18张图片") 最大。
如果需要使用动态规划求解，需要满足两个条件，
- 重复子问题
- 最优子结构
我们来分析一下最大概率路径问题，是否满足动态规划的两个条件。
重复子问题
对于节点wi和其可能存在的多个后继节点Wj和Wk，
任意通过Wi到达Wj的路径的权重 = 该路径通过Wi的路径权重 + Wj的权重，也即{Ri -> j} = {Ri + weight(j)}
任意通过Wi到达Wk的路径的权重 = 该路径通过Wi的路径权重 + Wk的权重，也即{Ri -> k} = {Ri + weight(k)}即对于拥有公共前驱节点Wi的节点Wj和Wk，需要重复计算达到Wi的路径的概率。
最优子结构
对于整个句子的最优路径Rmax和一个末端节点Wx，对于其可能存在的多个前驱Wi，Wj，Wk...，设到达Wi，Wj，Wk的最大路径分别是Rmaxi，Rmaxj，Rmaxk，有，
Rmax = max(Rmaxi,Rmaxj,Rmaxk,...) + weight(Wx)于是，问题转化为，求解Rmaxi，Rmaxj，Rmaxk，...等，
组成了最优子结构，子结构里面的最优解是全局的最优解的一部分。
状态转移方程为，
Rmax = max{(Rmaxi,Rmaxj,Rmaxk,...) + weight(Wx)}jieba分词中计算最大概率路径的主函数是calc(self, sentence, DAG, route)，函数根据已经构建好的有向无环图计算最大概率路径。
函数是一个自底向上的动态规划问题，它从sentence的最后一个字（N-1）开始倒序遍历sentence的每个字（idx）的方式，计算子句sentence[idx ~ N-1]的概率对数得分。然后将概率对数得分最高的情况以（概率对数，词语最后一个位置）这样的元组保存在route中。
函数中，logtotal为构建前缀词频时所有的词频之和的对数值，这里的计算都是使用概率对数值，可以有效防止下溢问题。
jieba分词中calc函数实现如下，
def calc(self, sentence, DAG, route):
N = len(sentence)
# 初始化末尾为0
route[N] = (0, 0)
logtotal = log(self.total)
# 从后到前计算
for idx in xrange(N - 1, -1, -1):
route[idx] = max((log(self.FREQ.get(sentence[idx:x + 1]) or 1) -
logtotal + route[x + 1][0], x) for x in DAG[idx])上面的计算过程，self.total打印一下，是60101967；这个数目是所有词的词频相加得到的结果；不同的词数是349046。相应地，logtotal约为17.91；首先是填充了route[6]，（0，0）；然后从最后一个字开始计算，‘去北京大学玩’，也即开始计算‘玩’；
ln(4207) - 17.91 = -9.56DAG[5]中没有其他的x，所以更新route[5] = (-9.56，5)
接下来是&#39;学&#39;，DAG[4]同样只有4自己，所以计算
ln(17432) - 17.91 + （-9.56） = -17.70更新route[4] = (-17.70，4)
对于’大‘，它有两种方式，分别是&#39;大学&#39;和&#39;大&#39;、&#39;学&#39;；这样的话，分别计算
ln(144099) - 17.91 + (-17.70) = -23.73
ln(20025) - 17.91 + (-9.56) = -17.57更新route[3] = (-17.57, 4)
可以看一下运行效果。
{0: [0], 1: [1, 2, 4], 2: [2], 3: [3, 4], 4: [4], 5: [5]}
(4207, &#39;玩&#39;)
(17482, &#39;学&#39;)
(144099, &#39;大&#39;)
(20025, &#39;大学&#39;)
(6583, &#39;京&#39;)
(17860, &#39;北&#39;)
(34488, &#39;北京&#39;)
(2053, &#39;北京大学&#39;)
(123402, &#39;去&#39;)
{6: (0, 0), 5: (-9.567048044164698, 5), 4: (-17.709674112779485, 4), 3: (-17.573864399983357, 4), 2: (-26.6931716802707, 2), 1: (-19.851543754900984, 4), 0: (-26.039894284878688, 0)}
去 北京大学 玩最后就是从前向后找一个概率最大的情况。
本部分代码可以参考：
以及
表示感谢。
基于汉字成词能力的HMM模型
以下内容来自参考9，在此表示感谢。
前面已经介绍了基于前缀词典和动态规划方法实现分词，我们之前看到过，如果没有前缀词典或者有些词不在前缀词典中，jieba分词一样可以分词，那么jieba分词是如何对未登录词进行分词呢？这就是本部分将要讲解的，基于汉字成词能力的HMM（Hidden Markov Model）模型识别未登录词。
可以对比一下对“哈利波特的移动城堡”的分词结果。
因为在原始的词典中有“哈利波”所以，n-gram算法分词为：
哈利波 特 的 移动 城堡HMM的分词结果则为：
哈利波特 的 移动 城堡利用HMM模型进行分词，主要是将分词问题视为一个序列标注（sequence labeling）问题，其中，句子为观测序列，分词结果为状态序列。首先通过语料训练出HMM相关的模型，然后利用Viterbi算法进行求解，最终得到最优的状态序列，然后再根据状态序列，输出分词结果。
实例
序列标注，就是将输入句子和分词结果当作两个序列，句子为观测序列，分词结果为状态序列，当完成状态序列的标注，也就得到了分词结果。
以“去北京大学玩”为例，我们知道“去北京大学玩”的分词结果是“去 / 北京大学 / 玩”。对于分词状态，由于jieba分词中使用的是4-tag，因此我们以4-tag进行计算。4-tag，也就是每个字处在词语中的4种可能状态，B、M、E、S，分别表示Begin（这个字处于词的开始位置）、Middle（这个字处于词的中间位置）、End（这个字处于词的结束位置）、Single（这个字是单字成词）。具体如下图所示，“去”和“玩”都是单字成词，因此状态就是S，“北京大学”是多字组合成的词，因此“北”、“京”、“大”、“学”分别位于“北京大学”中的B、M、M、E。
HMM模型有三个基本问题：
1.概率计算问题，给定模型 和观测序列 ，怎样计算在模型 下观测序列O出现的概率 ，也就是Forward-backward算法；
2.学习问题，已知观测序列 ，估计模型 ，使得在该模型下观测序列的概率 尽可能的大，即用极大似然估计的方法估计参数；
3.预测问题，也称为解码问题，已知模型 和观测序列 ，求对给定观测序列条件概率 最大的状态序列 ，即给定观测序列。求最有可能的对应的状态序列；其中，jieba分词主要中主要涉及第三个问题，也即预测问题。
*HMM模型中的五元组表示：*
1.观测序列；
2.隐藏状态序列；
3.状态初始概率；
4.状态转移概率；
5.状态发射概率；这里仍然以“去北京大学玩”为例，那么“去北京大学玩”就是观测序列。
而“去北京大学玩”对应的“SBMMES”则是隐藏状态序列，我们将会注意到B后面只能接（M或者E），不可能接（B或者S）；而M后面也只能接（M或者E），不可能接（B或者S）。
状态初始概率表示，每个词初始状态的概率；jieba分词训练出的状态初始概率模型如下所示。其中的概率值都是取对数之后的结果（可以让概率相乘转变为概率相加），其中-3.14e+100代表负无穷，对应的概率值就是0。这个概率表说明一个词中的第一个字属于{B、M、E、S}这四种状态的概率，如下可以看出，E和M的概率都是0，这也和实际相符合：开头的第一个字只可能是每个词的首字（B），或者单字成词（S）。这部分对应jieba/finaseg/prob_start.py，具体可以进入源码查看。差不多对应着ln(0.77)和ln(0.23)
P={&#39;B&#39;: -0.26268660809250016,
&#39;E&#39;: -3.14e+100,
&#39;M&#39;: -3.14e+100,
&#39;S&#39;: -1.4652633398537678}jieba中的状态转移概率，其实就是一个嵌套的词典，数值是概率值求对数后的值，如下所示，
P={&#39;B&#39;: {&#39;E&#39;: -0.510825623765990, &#39;M&#39;: -0.916290731874155},
&#39;E&#39;: {&#39;B&#39;: -0.5897149736854513, &#39;S&#39;: -0.8085250474669937},
&#39;M&#39;: {&#39;E&#39;: -0.33344856811948514, &#39;M&#39;: -1.2603623820268226},
&#39;S&#39;: {&#39;B&#39;: -0.7211965654669841, &#39;S&#39;: -0.6658631448798212}}P[&#39;B&#39;][&#39;E&#39;]代表的含义就是从状态B转移到状态E的概率，由P[&#39;B&#39;][&#39;E&#39;] = -0.5897149736854513，表示当前状态是B，下一个状态是E的概率对数是-0.5897149736854513，对应的概率值是0.6，相应的，当前状态是B，下一个状态是M的概率是0.4，说明当我们处于一个词的开头时，下一个字是结尾的概率要远高于下一个字是中间字的概率，符合我们的直觉，因为二个字的词比多个字的词更常见。
状态发射概率，根据HMM模型中观测独立性假设，发射概率，即观测值只取决于当前状态值，也就如下所示，
P(observed,states[j]) = P(states[j]) * P(observed | states[j]) 其中，P(observed | states[j])就是从状态发射概率中获得的。
P={&#39;B&#39;: {&#39;一&#39;: -3.6544978750449433,
&#39;丁&#39;: -8.125041941842026,
&#39;七&#39;: -7.817392401429855,
...
&#39;S&#39;: {&#39;:&#39;: -15.828865681131282,
&#39;一&#39;: -4.92368982120877,
&#39;丁&#39;: -9.024528361347633,
...P[&#39;B&#39;][&#39;一&#39;]代表的含义就是状态处于&#39;B&#39;，而观测的字是‘一’的概率对数值为P[&#39;B&#39;][&#39;一&#39;] = -3.6544978750449433
Viterbi算法
Viterbi算法实际上是用动态规划求解HMM模型预测问题，即用动态规划求概率路径最大（最优路径）。这时候，一条路径对应着一个状态序列。
根据动态规划原理，最优路径具有这样的特性：如果最优路径在时刻t通过结点 ，那么这一路径从结点 到终点 的部分路径，对于从 到 的所有可能的部分路径来说，必须是最优的。因为假如不是这样，那么从 到 就有另一条更好的部分路径存在，如果把它和从 到达 的部分路径连接起来，就会形成一条比原来的路径更优的路径，这是矛盾的。简而言之，最优路径的子路径也一定是最优的。
依据这个原理，我们只需要从时刻t=1开始，递推地计算在时刻t状态i的各条部分路径的最大概率，直至得到时刻t=T状态为i的各条路径的最大概率。时刻t=T的最大概率就是最优路径的概率 ![自然语言处理1：分词 第20张图片]( "自然语言处理1：分词 第20张图片") ，最优路径的终结点 也同时得到。之后，为了找出最优路径的各个结点，从终结点 开始，由后向前逐步求得结点 ![自然语言处理1：分词 第21张图片]( "自然语言处理1：分词 第21张图片") ，最终得到最优路径 ![自然语言处理1：分词 第22张图片]( "自然语言处理1：分词 第22张图片") 。
输出分词结果
由Viterbi算法得到状态序列，也就可以根据状态序列得到分词结果。其中状态以B开头，离它最近的以E结尾的一个子状态序列或者单独为S的子状态序列，就是一个分词。以”去北京大学玩“的隐藏状态序列”SBMMES“为例，则分词为”S / BMME / S“，对应观测序列，也就是”去 / 北京大学 / 玩”。
源码
prob_start.py 存储了已经训练好的HMM模型的状态初始概率表；
prob_trans.py 存储了已经训练好的HMM模型的状态转移概率表；
prob_emit.py 存储了已经训练好的HMM模型的状态发射概率表；
HMM模型参数训练
HMM模型的参数是如何训练出来，此处可以参考jieba中Issue 模型的数据是如何生成的? ，如下是jieba的开发者的解释：
来源主要有两个，一个是网上能下载到的1998人民日报的切分语料还有一个msr的切分语料。另一个是我自己收集的一些txt小说，用ictclas把他们切分（可能有一定误差），然后用python脚本统计词频。
要统计的主要有三个概率表：1)位置转换概率，即B（开头）,M（中间),E(结尾),S(独立成词）四种状态的转移概率；2）位置到单字的发射概率，比如P(&#34;和&#34;|M)表示一个词的中间出现”和&#34;这个字的概率；3) 词语以某种状态开头的概率，其实只有两种，要么是B，要么是S。 基于HMM模型的分词流程
jieba分词会首先调用函数cut(sentence)，cut函数会先将输入句子进行解码，然后调用_cut函数进行处理。cut函数就是jieba分词中实现HMM模型分词的主函数。cut函数会首先调用viterbi算法，求出输入句子的隐藏状态，然后基于隐藏状态进行分词。
def __cut(sentence):
global emit_P
# 通过viterbi算法求出隐藏状态序列
prob, pos_list = viterbi(sentence, &#39;BMES&#39;, start_P, trans_P, emit_P)
begin, nexti = 0, 0
# print pos_list, sentence
# 基于隐藏状态序列进行分词
for i, char in enumerate(sentence):
pos = pos_list
# 字所处的位置是开始位置
if pos == &#39;B&#39;:
begin = i
# 字所处的位置是结束位置
elif pos == &#39;E&#39;:
# 这个子序列就是一个分词
yield sentence[begin:i + 1]
nexti = i + 1
# 单独成字
elif pos == &#39;S&#39;:
yield char
nexti = i + 1
# 剩余的直接作为一个分词，返回
if nexti < len(sentence):
yield sentence[nexti:]Viterbi算法
viterbi算法其实就是多步骤每步多选择模型的最优选择问题，其在每一步的所有选择都保存了前续所有步骤到当前步骤当前选择的最小总代价（或者最大价值）以及当前代价的情况下前继步骤的选择。依次计算完所有步骤后，通过回溯的方法找到最优选择路径。
首先先定义两个变量， ![自然语言处理1：分词 第23张图片]( "自然语言处理1：分词 第23张图片") 定义在时刻t状态i的所有单个路径 ![自然语言处理1：分词 第24张图片]( "自然语言处理1：分词 第24张图片") 中概率最大值为
![自然语言处理1：分词 第25张图片]( "自然语言处理1：分词 第25张图片")
由此可得变量 ![自然语言处理1：分词 第26张图片]( "自然语言处理1：分词 第26张图片") 的递推公式为，
![自然语言处理1：分词 第27张图片]( "自然语言处理1：分词 第27张图片")
![自然语言处理1：分词 第28张图片]( "自然语言处理1：分词 第28张图片")
定义在时刻t状态i的所有单个路径 ![自然语言处理1：分词 第29张图片]( "自然语言处理1：分词 第29张图片") 中概率最大的路径的第t-1个结点为，
![自然语言处理1：分词 第30张图片]( "自然语言处理1：分词 第30张图片")
Viterbi算法的大致流程：
输入：模型![自然语言处理1：分词 第31张图片]( "自然语言处理1：分词 第31张图片") 和观测序列 ![自然语言处理1：分词 第32张图片]( "自然语言处理1：分词 第32张图片") ；
输出：最优路径 ；
（1）初始化
![自然语言处理1：分词 第33张图片]( "自然语言处理1：分词 第33张图片")
![自然语言处理1：分词 第34张图片]( "自然语言处理1：分词 第34张图片")
（2）递推
![自然语言处理1：分词 第35张图片]( "自然语言处理1：分词 第35张图片")
![自然语言处理1：分词 第36张图片]( "自然语言处理1：分词 第36张图片")
（3）终止
![自然语言处理1：分词 第37张图片]( "自然语言处理1：分词 第37张图片")
![自然语言处理1：分词 第38张图片]( "自然语言处理1：分词 第38张图片")
（4）最优路径回溯，对于t=T-1，T-2，...，1，
![自然语言处理1：分词 第39张图片]( "自然语言处理1：分词 第39张图片")
最终求得最优路径 ；
jieba分词实现Viterbi算法是在viterbi(obs, states, start_p, trans_p, emit_p)函数中实现。viterbi函数会先计算各个初始状态的对数概率值，然后递推计算，每时刻某状态的对数概率值取决于上一时刻的对数概率值、上一时刻的状态到这一时刻的状态的转移概率、这一时刻状态转移到当前的字的发射概率三部分组成。
def viterbi(obs, states, start_p, trans_p, emit_p):
V = [{}] # tabular
path = {}
# 时刻t = 0，初始状态
for y in states: # init
V[0][y] = start_p[y] + emit_p[y].get(obs[0], MIN_FLOAT) //第一个字处理；因为start_p中M和E是极小值，所以和也是极小值
path[y] = [y]
# 时刻t = 1,...,len(obs) - 1
for t in xrange(1, len(obs)):
V.append({})
newpath = {}
# 当前时刻所处的各种可能的状态
for y in states:
# 获取发射概率对数
em_p = emit_p[y].get(obs[t], MIN_FLOAT)
# 分别获取上一时刻的状态的概率对数，该状态到本时刻的状态的转移概率对数，本时刻的状态的发射概率对数
# 其中，PrevStatus[y]是当前时刻的状态所对应上一时刻可能的状态
(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
# 最后一个时刻，只能是E或者S
(prob, state) = max((V[len(obs) - 1][y], y) for y in &#39;ES&#39;)
# 返回最大概率对数和最优路径
return (prob, path[state])相关优化：
- 1.将每一时刻最优概率路径记录下来，避免了第4步的最优路径回溯；
- 2.提前建立一个当前时刻的状态到上一时刻的状态的映射表，记录每个状态在前一时刻的可能状态，降低计算量；如下所示，当前时刻的状态是B，那么前一时刻的状态只可能是（E或者S），而不可能是（B或者M）；
PrevStatus = {
&#39;B&#39;: &#39;ES&#39;,
&#39;M&#39;: &#39;MB&#39;,
&#39;S&#39;: &#39;SE&#39;,
&#39;E&#39;: &#39;BM&#39;
}接下来结合具体的计算例子进一步理解代码。
两个字的情况，腾讯和腾飞
第一行打印出来的就是对“腾”作为第一个字的处理；作为B出现的概率对数是-10.4425；作为S出现的是-11.5383。因为M和E的时候收到start_p的影响，都是极小值。
接下来处理第二个字，先查出来“迅”字作为BMES出现的概率对数；然后进行计算。下面详细计算一下：
对于B的情况，只有前一个字是E或者S的情况下，‘迅’才可能作为B，所以分别计算。因为在这个例子中“腾”作为E的概率是极小值，所以可以忽略；只计算“腾”作为S的情况。此时，还需要加上从S转到B的概率，需要查询
P={&#39;B&#39;: {&#39;E&#39;: -0.510825623765990, &#39;M&#39;: -0.916290731874155},
&#39;E&#39;: {&#39;B&#39;: -0.5897149736854513, &#39;S&#39;: -0.8085250474669937},
&#39;M&#39;: {&#39;E&#39;: -0.33344856811948514, &#39;M&#39;: -1.2603623820268226},
&#39;S&#39;: {&#39;B&#39;: -0.7211965654669841, &#39;S&#39;: -0.6658631448798212}}得到是-0.7211；接下来就可以计算
迅作为B的值是
-11.5383 + -0.7211 + -11.1565 = -21.4159类似地，可以计算出其他的三种情况：
M: -10.4425 + -0.9162 + -8.5537 = -19.9124
E: -10.4425 + -0.5108 + -8.9510 = -19.9043
S: -11.5383 + -0.6658 + -8.8998 = -21.1039
以及稍长的“哈利波特和罗恩”，这里可以看出来再处理到“和”这个字的时候，是M得到的值是最小的，而M所对应的序列是BMEBM。
对于哈利波特历险记则更有趣一些：
在处理到特的时候，是把特作为B来看待的，开始处理历的时候，是E得分最低，所以此时的序列是BMEBE；开始处理险字的时候，是作为E的得分最低，此时的序列是BMEBME
当开始处理 “记”字的时候，此时的B得分最低，对应的序列是BMEBMEB，E得分第二，对应的序列是BMMEBME。
以上介绍HMM的内容可能难以理解，所以我们另外找两个例子来理解。
还是用最经典的例子，掷骰子。假设我手里有三个不同的骰子。第一个骰子是我们平常见的骰子（称这个骰子为D6），6个面，每个面（1，2，3，4，5，6）出现的概率是1/6。第二个骰子是个四面体（称这个骰子为D4），每个面（1，2，3，4）出现的概率是1/4。第三个骰子有八个面（称这个骰子为D8），每个面（1，2，3，4，5，6，7，8）出现的概率是1/8。
假设我们开始掷骰子，我们先从三个骰子里挑一个，挑到每一个骰子的概率都是1/3。然后我们掷骰子，得到一个数字，1，2，3，4，5，6，7，8中的一个。不停的重复上述过程，我们会得到一串数字，每个数字都是1，2，3，4，5，6，7，8中的一个。例如我们可能得到这么一串数字（掷骰子10次）：1 6 3 5 2 7 3 5 2 4
这串数字叫做可见状态链。但是在隐马尔可夫模型中，我们不仅仅有这么一串可见状态链，还有一串隐含状态链。在这个例子里，这串隐含状态链就是你用的骰子的序列。比如，隐含状态链有可能是：D6 D8 D8 D6 D4 D8 D6 D6 D4 D8
一般来说，HMM中说到的马尔可夫链其实是指隐含状态链，因为隐含状态（骰子）之间存在转换概率（transition probability）。在我们这个例子里，D6的下一个状态是D4，D6，D8的概率都是1/3。D4，D8的下一个状态是D4，D6，D8的转换概率也都一样是1/3。这样设定是为了最开始容易说清楚，但是我们其实是可以随意设定转换概率的。比如，我们可以这样定义，D6后面不能接D4，D6后面是D6的概率是0.9，是D8的概率是0.1。这样就是一个新的HMM。
同样的，尽管可见状态之间没有转换概率，但是隐含状态和可见状态之间有一个概率叫做输出概率（emission probability），也叫发射概率。就我们的例子来说，六面骰（D6）产生1的输出概率是1/6。产生2，3，4，5，6的概率也都是1/6。我们同样可以对输出概率进行其他定义。比如，我有一个被赌场动过手脚的六面骰子，掷出来是1的概率更大，是1/2，掷出来是2，3，4，5，6的概率是1/10。
其实对于HMM来说，如果提前知道所有隐含状态之间的转换概率和所有隐含状态到所有可见状态之间的输出概率，做模拟是相当容易的。但是应用HMM模型时候呢，往往是缺失了一部分信息的，有时候你知道骰子有几种，每种骰子是什么，但是不知道掷出来的骰子序列；有时候你只是看到了很多次掷骰子的结果，剩下的什么都不知道。如果应用算法去估计这些缺失的信息，就成了一个很重要的问题。
和HMM模型相关的算法主要分为三类，分别解决三种问题：
1）知道骰子有几种（隐含状态数量），每种骰子是什么（转换概率和发射概率），根据掷骰子掷出的结果（可见状态链），我想知道每次掷出来的都是哪种骰子（隐含状态链）。
这个问题呢，在语音识别领域呢，叫做解码问题。一种解法求最大似然状态路径，说通俗点呢，就是求一串骰子序列，这串骰子序列产生观测结果的概率最大。
2）还是知道骰子有几种（隐含状态数量），每种骰子是什么（转换概率和发射概率），根据掷骰子掷出的结果（可见状态链），我想知道掷出这个结果的概率。
看似这个问题意义不大，因为掷出来的结果很多时候都对应了一个比较大的概率。问这个问题的目的呢，其实是检测观察到的结果和已知的模型是否吻合。如果很多次结果都对应了比较小的概率，那么就说明已知的模型很有可能是错的，有人偷偷把骰子給换了。
3）知道骰子有几种（隐含状态数量），不知道每种骰子是什么（转换概率和发射概率），观测到很多次掷骰子的结果（可见状态链），我想反推出每种骰子是什么（转换概率）。
这个问题很重要，因为这是最常见的情况。很多时候我们只有可见结果，不知道HMM模型里的参数，我们需要从可见结果估计出这些参数，这是建模的一个必要步骤。
0.一个简单问题
其实这个问题实用价值不高。由于对下面较难的问题有帮助，所以先在这里提一下。
知道骰子有几种，每种骰子是什么，每次掷的都是什么骰子，根据掷骰子掷出的结果，求产生这个结果的概率。
解法无非就是概率相乘：
![自然语言处理1：分词 第48张图片]( "自然语言处理1：分词 第48张图片")
![自然语言处理1：分词 第49张图片]( "自然语言处理1：分词 第49张图片")
1.看见不可见的，破解骰子序列
举例来说，我知道我有三个骰子，六面骰，四面骰，八面骰。我也知道我掷了十次的结果（1 6 3 5 2 7 3 5 2 4），我不知道每次用了那种骰子，我想知道最有可能的骰子序列。
其实最简单而暴力的方法就是穷举所有可能的骰子序列，然后依照第零个问题的解法把每个序列对应的概率算出来。然后我们从里面把对应最大概率的序列挑出来就行了 。如果马尔可夫链不长，当然可行。如果长的话，穷举的数量太大，就很难完成了。
另外一种很有名的算法叫做Viterbi algorithm. 要理解这个算法，我们先看几个简单的列子。
首先，如果我们只掷一次骰子：
看到结果为1。对应的最大概率骰子序列就是D4，因为D4产生1的概率是1/4，高于1/6和1/8.
把这个情况拓展，我们掷两次骰子：
结果为1，6。这时问题变得复杂起来，我们要计算三个值，分别是第二个骰子是D6，D4，D8的最大概率。显然，要取到最大概率，第一个骰子必须为D4。这时，第二个骰子取到D6的最大概率是
![自然语言处理1：分词 第52张图片]( "自然语言处理1：分词 第52张图片")
![自然语言处理1：分词 第53张图片]( "自然语言处理1：分词 第53张图片")
同样的，我们可以计算第二个骰子是D4或D8时的最大概率。我们发现，第二个骰子取到D6的概率最大。而使这个概率最大时，第一个骰子为D4。所以最大概率骰子序列就是D4 D6。
继续拓展，我们掷三次骰子：
同样，我们计算第三个骰子分别是D6，D4，D8的最大概率。我们再次发现，要取到最大概率，第二个骰子必须为D6。这时，第三个骰子取到D4的最大概率是![自然语言处理1：分词 第55张图片]( "自然语言处理1：分词 第55张图片")
![自然语言处理1：分词 第56张图片]( "自然语言处理1：分词 第56张图片")
同上，我们可以计算第三个骰子是D6或D8时的最大概率。我们发现，第三个骰子取到D4的概率最大。而使这个概率最大时，第二个骰子为D6，第一个骰子为D4。所以最大概率骰子序列就是D4 D6 D4。
写到这里，大家应该看出点规律了。既然掷骰子一二三次可以算，掷多少次都可以以此类推。我们发现，我们要求最大概率骰子序列时要做这么几件事情。首先，不管序列多长，要从序列长度为1算起，算序列长度为1时取到每个骰子的最大概率。然后，逐渐增加长度，每增加一次长度，重新算一遍在这个长度下最后一个位置取到每个骰子的最大概率。因为上一个长度下的取到每个骰子的最大概率都算过了，重新计算的话其实不难。当我们算到最后一位时，就知道最后一位是哪个骰子的概率最大了。然后，我们要把对应这个最大概率的序列从后往前推出来。
上面的Viterbi算法的例子，优点是非常简单，第一次看的同学很容易获得关于HMM和Viterbi的基本概念；但是缺点是太过于简化了，可能有同学会把Viterbi理解的过于简单。
上面的例子过分简化的是三个隐含状态之间的转换概率都是相等的。导致从观测状态倒推出来的最大概率的隐含状态在之后的计算中会一直是最大概率，所以计算非常简单。如果不同隐含状态之间的转换概率不同，那么这个计算会更复杂。上面的例子，纯粹是帮助理解HMM、转换概率、发射概率等概念。
再举一个例子，来自于
从前有个村子，村民们的身体情况只有两种可能：健康或者发烧。村民对自己的身体状况只会回答正常、头晕或冷；医生通过询问村民的感觉，判断村民的病情。
假设一个村民告诉医生感觉正常。
第二天告诉医生感觉有点冷。
第三天她告诉医生感觉有点头晕。
那么如何根据这个描述，判断村民的身体状况呢？
已知条件
隐含的身体状态 = { 健康 , 发烧 }
可观察的感觉状态 = { 正常 , 冷 , 头晕 }
村民身体状态的概率分布 = { 健康：0.6 , 发烧： 0.4 }
村民身体健康状态的转换概率分布 = {
健康->健康： 0.7 ,
健康->发烧： 0.3 ,
发烧->健康：0.4 ,
发烧->发烧： 0.6
}
在相应健康状况条件下，村民的感觉的概率分布 = {
健康，正常：0.5 ，冷 ：0.4 ，头晕： 0.1 ；
发烧，正常：0.1 ，冷 ：0.3 ，头晕： 0.6
}
村民连续三天的身体感觉依次是： 正常、冷、头晕 。
问题：
村民连续三天的健康状况如何？
计算过程：
2. 求第一天的身体情况：
计算村民感觉正常的情况下最可能的身体状态。
- P(正常|初始健康) = P(正常|健康)*P(健康|初始情况) = 0.5 * 0.6 = 0.3
- P(正常|初始发烧) = P(正常|发烧)*P(发烧|初始情况) = 0.1 * 0.4 = 0.04
那么就可以认为第一天最可能的身体状态是：健康。
如果我们继续算下去，可以算出来P(第一天健康|正常)和P(第一天发烧|正常)的概率。
3. 求第二天的身体状况：
计算在村民感觉冷的情况下最可能的身体状态。
那么第二天有四种情况，由于第一天的发烧或者健康转换到第二天的发烧或者健康。
- P(正常，冷|前一天发烧，今天发烧) = P(正常|前一天发烧)*P(发烧->发烧)*P(冷|发烧) = 0.04 * 0.6 * 0.3 = 0.0072
- P(正常，冷|前一天发烧，今天健康) = P(正常|前一天发烧)*P(发烧->健康)*P(冷|健康) = 0.04 * 0.4 * 0.4 = 0.0064
- P(正常，冷|前一天健康，今天健康) = P(正常|前一天健康)*P(健康->健康)*P(冷|健康) = 0.3 * 0.7 * 0.4 = 0.084
- P(正常，冷|前一天健康，今天发烧) = P(正常|前一天健康)*P(健康->发烧)*P(冷|发烧) = 0.3 * 0.3 *.03 = 0.027
那么可以认为，第二天最可能的状态是：健康。
4.求第三天的身体状态：
第三天同样考虑四种状况，前一天（第二天）分别是健康|发烧的状态转移到当前的状况，分别计算在村民感觉头晕的情况下最可能的身体状态。
- P(冷，头晕| 发烧，发烧) = P(前一天发烧)*P(发烧->发烧)*P(头晕|发烧) = 0.027 * 0.6 * 0.6 = 0.00972
- P(冷，头晕|发烧，健康) = P(前一天发烧)*P(发烧->健康)*P(头晕|健康) = 0.027 * 0.4 * 0.1 = 0.00108
- P(冷，头晕|健康，健康) = P(前一天健康)*P(健康->健康)*P(头晕|健康) = 0.084 * 0.7 * 0.1 = 0.00588
- P(冷，头晕|健康，发烧) = P(前一天健康)*P(健康->发烧)*P(头晕|发烧) = 0.084 * 0.3 *0.6 = 0.01512
那么可以认为：第三天最可能的状态是发烧。
5.结论
根据如上计算，医生判断村民这三天身体变化的序列是：健康->健康->发烧。
维基百科的这个例子的动态图：
参考：
- https://juejin.im/post/5d2f1ff16fb9a07ed740b375 【整体介绍】
- https://www.cnblogs.com/pinard/p/6945257.html 【具体实例】
- https://www.zhihu.com/question/20962240 【形象解释】
- https://zhuanlan.zhihu.com/p/27056207 【复杂度分析】
- https://www.cnblogs.com/xlturing/p/8465965.html
- https://blog.csdn.net/shuihupo/article/details/81540433 【分词工具对比】
- https://github.com/fxsjy/jieba 【Jieba github】
- https://zhuanlan.zhihu.com/p/58848504 【结合实例讲解】
- https://zhuanlan.zhihu.com/p/59475170
- https://blog.csdn.net/chenwei825825/article/details/21383545
- https://cloud.tencent.com/developer/article/1058352 【公式】
- https://blog.csdn.net/songbinxu/article/details/80209197?depth_1-utm_source=distribute.pc_relevant.none-task&utm_source=distribute.pc_relevant.none-task
- https://blog.csdn.net/Zh823275484/article/details/87878512?depth_1-utm_source=distribute.pc_relevant.none-task&utm_source=distribute.pc_relevant.none-task
- viterbi算法：利用动态规划寻找最短路径 解释的很清楚
下面举一个比较简单的例子做说明：求S到E的最短路径。如下图（各点之间距离不相同）：
我们知道，要找到S到E之间最短路径，最容易想到的方法就是穷举法。也就是把所有可能的路径都例举出来。从S走向A层共有4种走法，从A层走向B层又有4种走法，从B层走向C层又有4种走法，然后C层走向E点只有一种选择。所以最终我们穷举出了4X4X4=64种可能。显然，这种方法必定可行。但在实际的应用当中，对于数量极其庞大的结点数和边数的图，其计算复杂度也将会变得非常大，而计算效率也会随之降低。
因此，这里选择使用一种基于动态规划的方式来寻找最佳路径。
所谓动态规划。其核心就是“动态”的概念，把大的问题细分为多个小的问题，基于每一步的结果再去寻找下一步的策略，通过每一步走过之后的局部最优去寻找全局最优。这样解释比较抽象，下面直接用回刚刚的例子说明。如下图：
首先，我们假设S到E之间存在一条最短路径（红色），且这条路径经过C2点，那么我们便一定能够确定从S到C2的64条（4X4X4=64）子路径当中，该子路径一定最短。（证明：反证法。如果S到C2之间存在一条更短的子路径，那么便可以用它来代替原先的路径，而原先的路径显然就不是最短了，这与原假设自相矛盾）。
同理，我们也可以得出从S到B2点为两点间最短子路径的结论。这时候，真相便慢慢浮出水面：既然如此，我们计算从S点出发到点C2的最短路径，是不是只要考虑从S出发到B层所有节点的最短路径就可以了？答案是肯定的！因为，从S到E的“全局最短”路径必定经过在这些“局部最短”子路径。没错！这就是上面提及到的通过局部最优的最优去寻找全局最优，问题的规模被不断缩小！
接下来，要揭晓答案了！继续看下图：
回顾之前的分析：我们计算从S起到C2点的最短路径时候只需要考虑从S出发到B层所有节点的最短路径，B层也如是。对B2来说，一共有4条路线可以到达，分别是A1→B2，A2→B2，A3→B2，A4→B2。我们需要做的就是把A2→B2这条最短路线保留，而其他3条删除掉（因为根据以上的分析，它们不可能构成全程的最短路线）。OK，来到这里，我们会发现一个小“漏洞”，这段S→A2→B2→C2→E的路线只是我一厢情愿的假设，最短路径不一定是经过以上这些点。所以，我们要把每层的每个节点都考虑进来。
以下是具体的做法：
step1：从点S出发。对于第一层的3个节点，算出它们的距离d（S,A1）,d（S,A2）,d（S,A3）,d（S,A4），因为只有一步，所以这些距离都是S到它们各自的最短距离。
step2：对于B层的所有节点（B1,B2,B3,B4），要计算出S到它们的最短距离。我们知道，对于特定的节点B2，从S到它的路径可以经过A层的任何一个节点（A1,A2,A3,A4）。对应的路径长就是d（S,B2）=d（S,Ai）+d（Ai,B2）（其中i=1,2,3,4）。由于A层有4个节点（即i有4个取值），我们要一一计算，然后找到最小值。这样，对于B层的每个节点，都需要进行4次运算，而B层有4个节点，所以共有4X4=16次运算。
step3：这一步是该算法的核心。我们从step2计算得出的结果只保留4个最短路径值（每个节点保留一个）。那么，若从B层走向C层来说，该步骤的基数已经不再是4X4，而是变成了4！也就是说，从B层到C层的最短路径只需要基于B层得出的4个结果来计算。这种方法一直持续到最后一个状态，每一步计算的复杂度为相邻两层的计算复杂度为4X4乘积的正比！再通俗点说，连接这两两相邻层的计算符合变成了“+”号，取代了原先的“X”号。用这种方法，只需进行4X4X2=32次计算！
其实上述的算法就是著名的维特比算法，事实上非常简单！
若假设整个网格的宽度为D，网格长度为N，那么若使用穷举法整个最短路径的算法复杂度为O（D^N），而使用这种算法的计算复杂度为O（N*D^2）。试想一下，若D与N都非常大，使用维特比算法的效率将会提高几个数量级！
上一篇：假如没有俄罗斯天然气，欧洲能撑多久？
下一篇：欧盟能效标签注册EPREL注册流程及申诉 |
窥视卡
雷达卡
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
千斤顶
照妖镜
