中文分詞算法之HMM和Viterbi(維特比)算法理解

正文之前

這周二開博士沙龍,大老板對我想做的方向养篓,很感興趣秃流。。我他么有點害怕柳弄,聽同組師兄的女朋友舶胀,也是一個大老板門下的師姐說,在他們那一次博士沙龍碧注,大老板對我大加褒獎嚣伐,不吝溢美之詞,讓我更害怕了萍丐。這是一份沉甸甸的壓力纤控,我自覺我還是個小菜雞,還不至于成為大老板手上的小紅人碉纺,所以我怕自己讓大老板失望船万,那樣就不好了刻撒。不過既然都這樣了,那就好好學吧耿导。對吧声怔,大老板還推薦大家都來看看《漢字》 這個紀錄片。舱呻。也就是他想讓我做的方向的一個很好地啟蒙片醋火。。箱吕。我就推薦下吧

漢字-Bilibili 1080p國語中字

正文

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

淺談分詞算法(3)基于字的分詞方法(HMM)

具體的內容不多說,下面就簡單講下我對這里面的Viterbi算法的理解怎栽。


首先需要介紹下隱馬爾科夫模型(Hidden Markov Model丽猬,HMM):

HMM包含如下的五元組:

  • 狀態(tài)值集合Q={q1,q2,...,qN},其中N為可能的狀態(tài)數熏瞄;在本文的例子中脚祟,就是漢字有可能的四個狀態(tài)(B,M,E,S),分別表示詞的開始强饮、結束由桌、中間(begin、end邮丰、middle)及字符獨立成詞(single)

  • 觀測值集合V={v1,v2,...,vM}沥寥,其中M為可能的觀測數;觀測值就是文本中的字咯柠座;

  • 轉移概率矩陣A=[aij]邑雅,其中aij表示從狀態(tài)i轉移到狀態(tài)j的概率;這個在本中文是指從一個狀態(tài)轉移到另一個狀態(tài)的概率妈经;

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

  • 初始狀態(tài)分布π.(初始值骤星,內部給定)

一般地,將HMM表示為模型λ=(A,B,π)爆哑,狀態(tài)序列為I洞难,對應測觀測序列為O。對于這三個基本參數揭朝,HMM有三個基本問題:

  • 概率計算問題队贱,在模型λ下觀測序列O出現(xiàn)的概率色冀;

  • 學習問題,已知觀測序列O柱嫌,估計模型λ的參數锋恬,使得在該模型下觀測序列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)決定的感覺的一種:正常、冷或頭暈架诞。這些是觀察結果拟淮。 整個系統(tǒng)為一個隱馬爾可夫模型(HMM)。

醫(yī)生知道村民的總體健康狀況谴忧,還知道發(fā)燒和沒發(fā)燒的病人通常會抱怨什么癥狀很泊。 換句話說,醫(yī)生知道隱馬爾可夫模型的參數沾谓。 這可以用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:初始概率分布隶债,大概就是第一個字的狀態(tài)的概率吧
tran :狀態(tài)轉移概率,從當前狀態(tài)到下一個狀態(tài)的轉移的概率饮潦,
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)轉移概率的分析
    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的限定后稀并,前一個詞的限定范圍內某一狀態(tài)y0的概率 +  y0對當前字的y狀態(tài)的轉移概率 + 當前詞在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的用法弊知,開心`

最后編輯于
?著作權歸作者所有,轉載或內容合作請聯(lián)系作者
  • 序言:七十年代末阻逮,一起剝皮案震驚了整個濱河市,隨后出現(xiàn)的幾起案子秩彤,更是在濱河造成了極大的恐慌夺鲜,老刑警劉巖,帶你破解...
    沈念sama閱讀 206,839評論 6 482
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件呐舔,死亡現(xiàn)場離奇詭異币励,居然都是意外死亡,警方通過查閱死者的電腦和手機珊拼,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 88,543評論 2 382
  • 文/潘曉璐 我一進店門食呻,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人,你說我怎么就攤上這事仅胞∶勘伲” “怎么了?”我有些...
    開封第一講書人閱讀 153,116評論 0 344
  • 文/不壞的土叔 我叫張陵干旧,是天一觀的道長渠欺。 經常有香客問我,道長椎眯,這世上最難降的妖魔是什么挠将? 我笑而不...
    開封第一講書人閱讀 55,371評論 1 279
  • 正文 為了忘掉前任,我火速辦了婚禮编整,結果婚禮上舔稀,老公的妹妹穿的比我還像新娘。我一直安慰自己掌测,他們只是感情好内贮,可當我...
    茶點故事閱讀 64,384評論 5 374
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著汞斧,像睡著了一般夜郁。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上粘勒,一...
    開封第一講書人閱讀 49,111評論 1 285
  • 那天竞端,我揣著相機與錄音,去河邊找鬼仲义。 笑死婶熬,一個胖子當著我的面吹牛剑勾,可吹牛的內容都是我干的埃撵。 我是一名探鬼主播,決...
    沈念sama閱讀 38,416評論 3 400
  • 文/蒼蘭香墨 我猛地睜開眼虽另,長吁一口氣:“原來是場噩夢啊……” “哼暂刘!你這毒婦竟也來了?” 一聲冷哼從身側響起捂刺,我...
    開封第一講書人閱讀 37,053評論 0 259
  • 序言:老撾萬榮一對情侶失蹤谣拣,失蹤者是張志新(化名)和其女友劉穎,沒想到半個月后族展,有當地人在樹林里發(fā)現(xiàn)了一具尸體森缠,經...
    沈念sama閱讀 43,558評論 1 300
  • 正文 獨居荒郊野嶺守林人離奇死亡,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內容為張勛視角 年9月15日...
    茶點故事閱讀 36,007評論 2 325
  • 正文 我和宋清朗相戀三年仪缸,在試婚紗的時候發(fā)現(xiàn)自己被綠了贵涵。 大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點故事閱讀 38,117評論 1 334
  • 序言:一個原本活蹦亂跳的男人離奇死亡,死狀恐怖宾茂,靈堂內的尸體忽然破棺而出瓷马,到底是詐尸還是另有隱情,我是刑警寧澤跨晴,帶...
    沈念sama閱讀 33,756評論 4 324
  • 正文 年R本政府宣布欧聘,位于F島的核電站,受9級特大地震影響端盆,放射性物質發(fā)生泄漏怀骤。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點故事閱讀 39,324評論 3 307
  • 文/蒙蒙 一爱谁、第九天 我趴在偏房一處隱蔽的房頂上張望晒喷。 院中可真熱鬧,春花似錦访敌、人聲如沸凉敲。這莊子的主人今日做“春日...
    開封第一講書人閱讀 30,315評論 0 19
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽爷抓。三九已至,卻和暖如春阻塑,著一層夾襖步出監(jiān)牢的瞬間蓝撇,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 31,539評論 1 262
  • 我被黑心中介騙來泰國打工陈莽, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留氢卡,地道東北人。 一個月前我還...
    沈念sama閱讀 45,578評論 2 355
  • 正文 我出身青樓畏纲,卻偏偏與公主長得像筛武,于是被迫代替她去往敵國和親。 傳聞我的和親對象是個殘疾皇子私植,可洞房花燭夜當晚...
    茶點故事閱讀 42,877評論 2 345

推薦閱讀更多精彩內容