正文之前
这周二开博士沙龙，大老板对我想做的方向，很感兴趣。。我他么有点害怕，听同组师兄的女朋友，也是一个大老板门下的师姐说，在他们那一次博士沙龙，大老板对我大加褒奖，不吝溢美之词，让我更害怕了。这是一份沉甸甸的压力，我自觉我还是个小菜鸡，还不至于成为大老板手上的小红人，所以我怕自己让大老板失望，那样就不好了。不过既然都这样了，那就好好学吧。对吧，大老板还推荐大家都来看看《汉字》 这个纪录片。。也就是他想让我做的方向的一个很好地启蒙片。。。我就推荐下吧
正文
最近读了一个博客，里面简述了一些中文分词算法，现在正在深入研究维特比算法，链接如下 ，有兴趣的朋友可以去看看全文：
具体的内容不多说，下面就简单讲下我对这里面的Viterbi算法的理解。
首先需要介绍下隐马尔科夫模型（Hidden Markov Model，HMM）：
HMM包含如下的五元组：
状态值集合Q={q1,q2,...,qN}，其中N为可能的状态数；在本文的例子中，就是汉字有可能的四个状态（B,M,E,S），分别表示词的开始、结束、中间（begin、end、middle）及字符独立成词（single）
观测值集合V={v1,v2,...,vM}，其中M为可能的观测数；观测值就是文本中的字咯；
转移概率矩阵A=[aij]，其中aij表示从状态i转移到状态j的概率；这个在本中文是指从一个状态转移到另一个状态的概率；
发射概率矩阵（也称之为观测概率矩阵）B=[bj(k)]，其中bj(k)表示在状态j的条件下生成观测vk的概率；本文中指一个字在某一状态的可能性。这个是先验的（就是说通过统计方法得到的）
初始状态分布π.（初始值，内部给定）
一般地，将HMM表示为模型λ=(A,B,π)，状态序列为I，对应测观测序列为O。对于这三个基本参数，HMM有三个基本问题：
概率计算问题，在模型λ下观测序列O出现的概率；
学习问题，已知观测序列O，估计模型λ的参数，使得在该模型下观测序列P(O|λ)最大；
解码（decoding）问题，已知模型λ与观测序列O，求解条件概率P(I|O)最大的状态序列I。
更详细的，简洁的说法请参见wiki吧，or有个博客讲的也还算清晰，主要看以天气和治病为例子的那些真实世界映射，骰子那个不是那么好理解wiki百科关于维特比和 ||||||||||||| 一文搞懂HMM（隐马尔可夫模型） |||||||||||||
想象一个乡村诊所。村民有着非常理想化的特性，要么健康要么发烧。他们只有问诊所的医生的才能知道是否发烧。 聪明的医生通过询问病人的感觉诊断他们是否发烧。村民只回答他们感觉正常、头晕或冷。
假设一个病人每天来到诊所并告诉医生他的感觉。医生相信病人的健康状况如同一个离散马尔可夫链。病人的状态有两种“健康”和“发烧”，但医生不能直接观察到，这意味着状态对他是“隐含”的。每天病人会告诉医生自己有以下几种由他的健康状态决定的感觉的一种：正常、冷或头晕。这些是观察结果。 整个系统为一个隐马尔可夫模型(HMM)。
医生知道村民的总体健康状况，还知道发烧和没发烧的病人通常会抱怨什么症状。 换句话说，医生知道隐马尔可夫模型的参数。 这可以用Python语言表示如下:
states = ('Healthy', 'Fever')
observations = ('normal', 'cold', 'dizzy')
start_probability = {'Healthy': 0.6, 'Fever': 0.4}
transition_probability = {
'Healthy' : {'Healthy': 0.7, 'Fever': 0.3},
'Fever' : {'Healthy': 0.4, 'Fever': 0.6},
}
emission_probability = {
'Healthy' : {'normal': 0.5, 'cold': 0.4, 'dizzy': 0.1},
'Fever' : {'normal': 0.1, 'cold': 0.3, 'dizzy': 0.6},
}
上面关于HMM的叙述大部分来自原文，所以大家可以去看原文，结合我的看就好了
如何从HMM模型到维特比算法，还请大家移步原文看，我就不多赘述，还是上代码加注释会比较好，毕竟我主要的工作就是加了一些注释。
# -*- coding: utf-8 -*-
'''
start：初始概率分布，大概就是第一个字的状态的概率吧
tran ：状态转移概率，从当前状态到下一个状态的转移的概率，
emit ：发射概率，表示在某一状态下生成某个观测状态（在这一状态下，这个字是这个状态）的概率
'''
import sys
import re
import getopt
MIN_FLOAT = -3.14e100
PROB_START_P = "prob_start.p"
PROB_TRANS_P = "prob_trans.p"
PROB_EMIT_P = "prob_emit.p"
#某一个词的状态为key时，prevStatus表示前一个词的状态的框定范围
PrevStatus = {
'B': 'ES',
'M': 'MB',
'S': 'SE',
'E': 'BM'
}
Force_Split_Words = set([])
from prob_start import P as start_P
from prob_trans import P as trans_P
from prob_emit import P as emit_P
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 range(1, len(obs)):
V.append({})
newpath = {}
# 考察当前字，对于上一个字的发射概率，取其中最大的那个
for y in states:
#获取当前词在y状态下的发射概率
em_p = emit_p[y].get(obs[t], MIN_FLOAT)
# y状态在prevStatus的限定后，前一个词的限定范围内某一状态y0的概率 + y0对当前字的y状态的转移概率 + 当前词在y状态下的发射概率（其实就是这个词是某个状态的概率的意思）
# state表示前一个字到当前字的y状态的最大概率，prob表示这个概率。
(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
# 更新路径，state表示当前字的前一个字到当前字的y状态的最大可能概率，所以是path[state]，因为要取前一个字的最大概率路径
newpath[y] = path[state] + [y]
path = newpath
# 最后一个要重新复盘,因为最后一个字只能是E or S
(prob, state) = max((V[len(obs) - 1][y], y) for y in 'ES')
for i in path:
print((i,path[i]))
for v in V:
print((v))
return (prob, path[state])
def __cut(sentence):
prob, pos_list = viterbi(sentence, 'BMES', start_P, trans_P, emit_P)
begin, nexti = 0, 0
# print pos_list, sentence
for i, char in enumerate(sentence):
pos = pos_list[i]
if pos == 'B':
begin = i
elif pos == 'E':
yield sentence[begin:i + 1]
nexti = i + 1
elif pos == 'S':
yield char
nexti = i + 1
if nexti < len(sentence):
yield sentence[nexti:]
re_han = re.compile("([\u4E00-\u9FD5]+)")
re_skip = re.compile("([a-zA-Z0-9]+(?:\.\d+)?%?)")
def cut(sentence):
sentence = sentence.strip().decode('utf-8')
blocks = re_han.split(sentence)
lseg = []
for blk in blocks:
if re_han.match(blk):
for word in __cut(blk):
if word not in Force_Split_Words:
lseg.append(word)
else:
for c in word:
lseg.append(c)
else:
tmp = re_skip.split(blk)
for x in tmp:
if x:
lseg.append(x)
return lseg
if __name__ == "__main__":
ifile = 'input.txt'
ofile = 'seg.txt'
# try:
# opts, args = getopt.getopt(sys.argv[1:], "hi:o:", ["ifile=", "ofile="])
# except getopt.GetoptError:
# print('seg_hmm.py -i <inputfile> -o <outputfile>')
# sys.exit(2)
# for opt, arg in opts:
# if opt == '-h':
# print('seg_hmm.py -i <inputfile> -o <outputfile>')
# sys.exit()
# elif opt in ("-i", "--ifile"):
# ifile = arg
# elif opt in ("-o", "--ofile"):
# ofile = arg
with open(ifile, 'rb') as inf:
for line in inf:
rs = cut(line)
print(' '.join(rs))
with open(ofile, 'a',encoding='utf8') as outf:
outf.write(' '.join(rs) + "\n")
OK，该说的都在代码上了，想要我细细道来也别想了。。麻烦，好人做到底，我再附个图,这下应该简单明了了：
----------图片上传不了。。。---------去下面看吧----------
图片来源知乎：如何通俗地讲解 viterbi 算法？
正文之后
OK，溜了，在代码中还学习到了yield和enumerate的用法，开心`
