正文之前

這周二開博士沙龍，大老板對我想做的方向，很感興趣。。我他么有點害怕，聽同組師兄的女朋友，也是一個大老板門下的師姐說，在他們那一次博士沙龍，大老板對我大加褒獎，不吝溢美之詞，讓我更害怕了。這是一份沉甸甸的壓力，我自覺我還是個小菜雞，還不至于成為大老板手上的小紅人，所以我怕自己讓大老板失望，那樣就不好了。不過既然都這樣了，那就好好學吧。對吧，大老板還推薦大家都來看看《漢字》 這個紀錄片。。也就是他想讓我做的方向的一個很好地啟蒙片。。。我就推薦下吧

漢字-Bilibili 1080p國語中字

正文

最近讀了一個博客，里面簡述了一些中文分詞算法，現(xiàn)在正在深入研究維特比算法，鏈接如下 ，有興趣的朋友可以去看看全文：

淺談分詞算法（3）基于字的分詞方法（HMM）

具體的內(nèi)容不多說，下面就簡單講下我對這里面的Viterbi算法的理解。

首先需要介紹下隱馬爾科夫模型（Hidden Markov Model，HMM）：

HMM包含如下的五元組：

• 狀態(tài)值集合Q={q1,q2,...,qN}，其中N為可能的狀態(tài)數(shù)；在本文的例子中，就是漢字有可能的四個狀態(tài)（B,M,E,S），分別表示詞的開始、結(jié)束、中間（begin、end、middle）及字符獨立成詞（single）

• 觀測值集合V={v1,v2,...,vM}，其中M為可能的觀測數(shù)；觀測值就是文本中的字咯；

• 轉(zhuǎn)移概率矩陣A=[aij]，其中aij表示從狀態(tài)i轉(zhuǎn)移到狀態(tài)j的概率；這個在本中文是指從一個狀態(tài)轉(zhuǎn)移到另一個狀態(tài)的概率；

• 發(fā)射概率矩陣（也稱之為觀測概率矩陣）B=[bj(k)]，其中bj(k)表示在狀態(tài)j的條件下生成觀測vk的概率；本文中指一個字在某一狀態(tài)的可能性。這個是先驗的（就是說通過統(tǒng)計方法得到的）

• 初始狀態(tài)分布π.（初始值，內(nèi)部給定）

一般地，將HMM表示為模型λ=(A,B,π)，狀態(tài)序列為I，對應測觀測序列為O。對于這三個基本參數(shù)，HMM有三個基本問題：

• 概率計算問題，在模型λ下觀測序列O出現(xiàn)的概率；

• 學習問題，已知觀測序列O，估計模型λ的參數(shù)，使得在該模型下觀測序列P(O|λ)最大；

• 解碼（decoding）問題，已知模型λ與觀測序列O，求解條件概率P(I|O)最大的狀態(tài)序列I。

更詳細的，簡潔的說法請參見wiki吧，or有個博客講的也還算清晰，主要看以天氣和治病為例子的那些真實世界映射，骰子那個不是那么好理解wiki百科關于維特比和 ||||||||||||| 一文搞懂HMM（隱馬爾可夫模型） |||||||||||||

想象一個鄉(xiāng)村診所。村民有著非常理想化的特性，要么健康要么發(fā)燒。他們只有問診所的醫(yī)生的才能知道是否發(fā)燒。 聰明的醫(yī)生通過詢問病人的感覺診斷他們是否發(fā)燒。村民只回答他們感覺正常、頭暈或冷。

假設一個病人每天來到診所并告訴醫(yī)生他的感覺。醫(yī)生相信病人的健康狀況如同一個離散馬爾可夫鏈。病人的狀態(tài)有兩種“健康”和“發(fā)燒”，但醫(yī)生不能直接觀察到，這意味著狀態(tài)對他是“隱含”的。每天病人會告訴醫(yī)生自己有以下幾種由他的健康狀態(tài)決定的感覺的一種：正常、冷或頭暈。這些是觀察結(jié)果。 整個系統(tǒng)為一個隱馬爾可夫模型(HMM)。

醫(yī)生知道村民的總體健康狀況，還知道發(fā)燒和沒發(fā)燒的病人通常會抱怨什么癥狀。 換句話說，醫(yī)生知道隱馬爾可夫模型的參數(shù)。 這可以用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的敘述大部分來自原文，所以大家可以去看原文，結(jié)合我的看就好了

如何從HMM模型到維特比算法，還請大家移步原文看，我就不多贅述，還是上代碼加注釋會比較好，畢竟我主要的工作就是加了一些注釋。

# -*- coding: utf-8 -*-
'''
start：初始概率分布，大概就是第一個字的狀態(tài)的概率吧
tran ：狀態(tài)轉(zhuǎn)移概率，從當前狀態(tài)到下一個狀態(tài)的轉(zhuǎn)移的概率，
emit ：發(fā)射概率，表示在某一狀態(tài)下生成某個觀測狀態(tài)（在這一狀態(tài)下，這個字是這個狀態(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"
#某一個詞的狀態(tài)為key時，prevStatus表示前一個詞的狀態(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]
    # 對之后的每一個字做狀態(tài)轉(zhuǎn)移概率的分析
    for t in range(1, len(obs)):
        V.append({})
        newpath = {}
        # 考察當前字，對于上一個字的發(fā)射概率，取其中最大的那個
        for y in states:
            #獲取當前詞在y狀態(tài)下的發(fā)射概率
            em_p = emit_p[y].get(obs[t], MIN_FLOAT)
            # y狀態(tài)在prevStatus的限定后，前一個詞的限定范圍內(nèi)某一狀態(tài)y0的概率 +  y0對當前字的y狀態(tài)的轉(zhuǎn)移概率 + 當前詞在y狀態(tài)下的發(fā)射概率（其實就是這個詞是某個狀態(tài)的概率的意思）
            # state表示前一個字到當前字的y狀態(tài)的最大概率，prob表示這個概率。
            (prob, state) = max(
                [
                    (V[t - 1][y0] + trans_p[y0].get(y, MIN_FLOAT) + em_p,   y0)
                 for y0 in PrevStatus[y]
                ]
            )
            #得到了當前字的所有可能觀測狀態(tài)的最大概率值
            V[t][y] = prob
            # 更新路徑，state表示當前字的前一個字到當前字的y狀態(tài)的最大可能概率，所以是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的用法，開心`