正文之前
這周二開(kāi)博士沙龍，大老板對(duì)我想做的方向，很感興趣。。我他么有點(diǎn)害怕，聽(tīng)同組師兄的女朋友，也是一個(gè)大老板門(mén)下的師姐說(shuō)，在他們那一次博士沙龍，大老板對(duì)我大加褒獎(jiǎng)，不吝溢美之詞，讓我更害怕了。這是一份沉甸甸的壓力，我自覺(jué)我還是個(gè)小菜雞，還不至于成為大老板手上的小紅人，所以我怕自己讓大老板失望，那樣就不好了。不過(guò)既然都這樣了，那就好好學(xué)吧。對(duì)吧，大老板還推薦大家都來(lái)看看《漢字》 這個(gè)紀(jì)錄片。。也就是他想讓我做的方向的一個(gè)很好地啟蒙片。。。我就推薦下吧
正文
最近讀了一個(gè)博客，里面簡(jiǎn)述了一些中文分詞算法，現(xiàn)在正在深入研究維特比算法，鏈接如下 ，有興趣的朋友可以去看看全文：
具體的內(nèi)容不多說(shuō)，下面就簡(jiǎn)單講下我對(duì)這里面的Viterbi算法的理解。
首先需要介紹下隱馬爾科夫模型（Hidden Markov Model，HMM）：
HMM包含如下的五元組：
狀態(tài)值集合Q={q1,q2,...,qN}，其中N為可能的狀態(tài)數(shù)；在本文的例子中，就是漢字有可能的四個(gè)狀態(tài)（B,M,E,S），分別表示詞的開(kāi)始、結(jié)束、中間（begin、end、middle）及字符獨(dú)立成詞（single）
觀測(cè)值集合V={v1,v2,...,vM}，其中M為可能的觀測(cè)數(shù)；觀測(cè)值就是文本中的字咯；
轉(zhuǎn)移概率矩陣A=[aij]，其中aij表示從狀態(tài)i轉(zhuǎn)移到狀態(tài)j的概率；這個(gè)在本中文是指從一個(gè)狀態(tài)轉(zhuǎn)移到另一個(gè)狀態(tài)的概率；
發(fā)射概率矩陣（也稱(chēng)之為觀測(cè)概率矩陣）B=[bj(k)]，其中bj(k)表示在狀態(tài)j的條件下生成觀測(cè)vk的概率；本文中指一個(gè)字在某一狀態(tài)的可能性。這個(gè)是先驗(yàn)的（就是說(shuō)通過(guò)統(tǒng)計(jì)方法得到的）
初始狀態(tài)分布π.（初始值，內(nèi)部給定）
一般地，將HMM表示為模型λ=(A,B,π)，狀態(tài)序列為I，對(duì)應(yīng)測(cè)觀測(cè)序列為O。對(duì)于這三個(gè)基本參數(shù)，HMM有三個(gè)基本問(wèn)題：
概率計(jì)算問(wèn)題，在模型λ下觀測(cè)序列O出現(xiàn)的概率；
學(xué)習(xí)問(wèn)題，已知觀測(cè)序列O，估計(jì)模型λ的參數(shù)，使得在該模型下觀測(cè)序列P(O|λ)最大；
解碼（decoding）問(wèn)題，已知模型λ與觀測(cè)序列O，求解條件概率P(I|O)最大的狀態(tài)序列I。
更詳細(xì)的，簡(jiǎn)潔的說(shuō)法請(qǐng)參見(jiàn)wiki吧，or有個(gè)博客講的也還算清晰，主要看以天氣和治病為例子的那些真實(shí)世界映射，骰子那個(gè)不是那么好理解wiki百科關(guān)于維特比和 ||||||||||||| 一文搞懂HMM（隱馬爾可夫模型） |||||||||||||
想象一個(gè)鄉(xiāng)村診所。村民有著非常理想化的特性，要么健康要么發(fā)燒。他們只有問(wèn)診所的醫(yī)生的才能知道是否發(fā)燒。 聰明的醫(yī)生通過(guò)詢問(wèn)病人的感覺(jué)診斷他們是否發(fā)燒。村民只回答他們感覺(jué)正常、頭暈或冷。
假設(shè)一個(gè)病人每天來(lái)到診所并告訴醫(yī)生他的感覺(jué)。醫(yī)生相信病人的健康狀況如同一個(gè)離散馬爾可夫鏈。病人的狀態(tài)有兩種“健康”和“發(fā)燒”，但醫(yī)生不能直接觀察到，這意味著狀態(tài)對(duì)他是“隱含”的。每天病人會(huì)告訴醫(yī)生自己有以下幾種由他的健康狀態(tài)決定的感覺(jué)的一種：正常、冷或頭暈。這些是觀察結(jié)果。 整個(gè)系統(tǒng)為一個(gè)隱馬爾可夫模型(HMM)。
醫(yī)生知道村民的總體健康狀況，還知道發(fā)燒和沒(méi)發(fā)燒的病人通常會(huì)抱怨什么癥狀。 換句話說(shuō)，醫(yī)生知道隱馬爾可夫模型的參數(shù)。 這可以用Python語(yǔ)言表示如下:
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},
}
上面關(guān)于HMM的敘述大部分來(lái)自原文，所以大家可以去看原文，結(jié)合我的看就好了
如何從HMM模型到維特比算法，還請(qǐng)大家移步原文看，我就不多贅述，還是上代碼加注釋會(huì)比較好，畢竟我主要的工作就是加了一些注釋。
# -*- coding: utf-8 -*-
'''
start：初始概率分布，大概就是第一個(gè)字的狀態(tài)的概率吧
tran ：狀態(tài)轉(zhuǎn)移概率，從當(dāng)前狀態(tài)到下一個(gè)狀態(tài)的轉(zhuǎn)移的概率，
emit ：發(fā)射概率，表示在某一狀態(tài)下生成某個(gè)觀測(cè)狀態(tài)（在這一狀態(tài)下，這個(gè)字是這個(gè)狀態(tài)）的概率
'''
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"
#某一個(gè)詞的狀態(tài)為key時(shí)，prevStatus表示前一個(gè)詞的狀態(tài)的框定范圍
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 獲取這一句子的初始狀態(tài)分布
V[0][y] = start_p[y] + emit_p[y].get(obs[0], MIN_FLOAT)
path[y] = [y]
# 對(duì)之后的每一個(gè)字做狀態(tài)轉(zhuǎn)移概率的分析
for t in range(1, len(obs)):
V.append({})
newpath = {}
# 考察當(dāng)前字，對(duì)于上一個(gè)字的發(fā)射概率，取其中最大的那個(gè)
for y in states:
#獲取當(dāng)前詞在y狀態(tài)下的發(fā)射概率
em_p = emit_p[y].get(obs[t], MIN_FLOAT)
# y狀態(tài)在prevStatus的限定后，前一個(gè)詞的限定范圍內(nèi)某一狀態(tài)y0的概率 + y0對(duì)當(dāng)前字的y狀態(tài)的轉(zhuǎn)移概率 + 當(dāng)前詞在y狀態(tài)下的發(fā)射概率（其實(shí)就是這個(gè)詞是某個(gè)狀態(tài)的概率的意思）
# state表示前一個(gè)字到當(dāng)前字的y狀態(tài)的最大概率，prob表示這個(gè)概率。
(prob, state) = max(
[
(V[t - 1][y0] + trans_p[y0].get(y, MIN_FLOAT) + em_p, y0)
for y0 in PrevStatus[y]
]
)
#得到了當(dāng)前字的所有可能觀測(cè)狀態(tài)的最大概率值
V[t][y] = prob
# 更新路徑，state表示當(dāng)前字的前一個(gè)字到當(dāng)前字的y狀態(tài)的最大可能概率，所以是path[state]，因?yàn)橐∏耙粋€(gè)字的最大概率路徑
newpath[y] = path[state] + [y]
path = newpath
# 最后一個(gè)要重新復(fù)盤(pán),因?yàn)樽詈笠粋€(gè)字只能是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，該說(shuō)的都在代碼上了，想要我細(xì)細(xì)道來(lái)也別想了。。麻煩，好人做到底，我再附個(gè)圖,這下應(yīng)該簡(jiǎn)單明了了：
----------圖片上傳不了。。。---------去下面看吧----------
圖片來(lái)源知乎：如何通俗地講解 viterbi 算法？
正文之后
OK，溜了，在代碼中還學(xué)習(xí)到了yield和enumerate的用法，開(kāi)心`
