最近我在學習自然語言處理，相信大家都知道NLP的第一步就是學分詞，但分詞≠自然語言處理?，F如今分詞工具及如何使用網上一大堆。我想和大家分享的是結巴分詞核心內容，一起探究分詞的本質。

(1)、基于前綴詞典實現高效的詞圖掃描，生成句子中漢字所有可能成詞情況所構成的有向無環圖

什么是DAG(有向無環圖)？

例如，句子“去北京大學玩”對應的DAG為{0:[0], 1:[1,2,4], 2:[2], 3:[3,4], 4:[4], 5:[5]}。DAG中{0:[0]}就表示0位置對應的是詞，就是說0~0，即“去”這個詞在Dict(詞典庫，里面記錄每個詞的頻次)中是詞條。DAG中{1:[1,2,4]}，就是表示從1位置開始，在1，2，4位置都是詞，就是說1~1、1~2、1~4即“北”“北京”“北京大學”這三個也是詞，出現在Dict中。句子“去北京大學玩”的DAG畢竟比較短可以一眼看出來，現在來了另外一個句子“經常有意見分歧”，如何得到它的DAG呢？這時候就得通過代碼來實現了。

Dict= {"經常":0.1,"經":0.05,"有":0.1, "常":0.001,"有意見":0.1, "歧":0.001,"意見":0.2,"分歧":0.2,"見":0.05,"意":0.05,"見分歧":0.05,"分":0.1}

def DAG(sentence):

DAG = {} #DAG空字典，用來構建DAG有向無環圖

N = len(sentence)

for k in range(N):

tmplist = []

i = k

frag = sentence[k]

while i < N:

if frag in Dict:

tmplist.append(i)

i += 1

frag = sentence[k:i + 1]

if not tmplist:

tmplist.append(k)

DAG[k] = tmplist

return DAG

print(DAG("經常有意見分歧"))

輸出：

{0: [0, 1], 1: [1], 2: [2, 4], 3: [3, 4], 4: [4, 6], 5: [5, 6], 6: [6]}

根據dict及其每個詞出現的概率，可以得到所有可能出現路徑(分詞情況)，如下圖：

DAG的圖表示

只要出現的詞，就可以分，像“經常有”這個詞沒出現，就不能把它當做單獨一個詞分開了，通過運行代碼，我們可以得到“經常有意見分歧”的DAG

{0: [0, 1], 1: [1], 2: [2, 4], 3: [3, 4], 4: [4, 6], 5: [5, 6], 6: [6]}

，便于直觀理解DAG，我們把問題轉化成尋找路徑的過程，就如上圖表示，從開始到結束，比如我照最上面紅線的路徑走，可以得到[經常|有|意見|分歧]的分詞情況，如果把它們每一步的概率值加起來就是該路徑的得分S=0.1+0.1+0.2+0.2=0.6，同理我走其他的路徑[經|常|有意見|分歧]，它的得分就是S=0.05+.0.001+0.1+0.2=0.351。這就是我們的第一步，通過代碼構建出一個sentence的DAG。

(2)采用動態規劃查找最大概率路徑，找出基于詞頻的最大切分組合。

通過第一步，得到了DAG，同樣也可以得到每條路徑的得分S，從中找到得分最大的，也就是概率值最大的情況，就是我們要找的分詞情況。如果用遍歷所有路徑的話，找到每個路徑然后求出每個S，取出最大的S，當然可以得到我們想要的，但比較蠻力。我們可以試著用動態規劃的思路，維特比算法，直接上圖

維特比算法的順序解法

給每個節點編號1~8，開始到結束，f(a)代表該節點的所有得分值，每一步單個的箭頭都有其對應的概率值，c(a~b)代表的是a節點到b節點的值，如c(1~3)是“經常”的概率值，為什么有的節點如f(6)有三個值？那是因為6這個節點有三個箭頭指向它，也就是說有多少個箭頭指向該節點，該節點就有多少個得分值，如分f(3)有2個值、f(4)有一個值......。按1~8的順序，計算出每個節點的所有得分值，計算后面節點的時候要用到前面節點得分值都取(max)最大的，以保證最后計算到f(8)時是全局的最大值，例如計算f(4)中f(3)取的就是0.1。算到最后,我們知道f(8)=f(6) +c(6~8) =0.4+0.2=0.6 (max)，接著把f(6)展開，f(8)=f(4) +c(4~6) +c(6~8) ，同理，把所有的f()換成c(),f(8)=c(1~3) +c(3~4) +c(4~6) +c(6~8) 。直到等式右邊沒有f()，c(1~3)、c(3~4)、c(4~6)、c(6~8)分別代表啥各位看圖去吧。

回到開始，假如用蠻力一個一個列出所有路徑，不累死也得列的頭暈，用動態規劃的思想可以把一個大問題拆分到每一步的小問題，下一步的小問題只需要在之前的小問題上再進一步，動態規劃的思想就像是小問題站巨人肩膀上，然后大問題莫名其妙就解決了。剛說的是從開始到結束的順序解法，要是從8節點到1節點逆序解法怎么解？

維特比算法的逆序解法

發現沒，最后最大都是0.6=f(1)=c(1~3) +c(3~4) +c(4~6) +c(6~8)，而且直接都是看出來了，再一次說明了最大的路徑就是這條路徑。說了這么多，上代碼

sentence ="經常有意見分歧"

N=len(sentence)

route={}

route[N] = (0, 0)

DAG={0: [0, 1], 1: [1], 2: [2, 4], 3: [3, 4], 4: [4, 6], 5: [5, 6], 6: [6]}

for idx in range(N - 1, -1, -1):

distance = (((Dict.get(sentence[idx:x + 1]) or 0) + route[x + 1][0], x) for x in DAG[idx])

route[idx] = max(distance)

# 列表推倒求最大概率對數路徑

# route[idx] = max([ (概率值，詞語末字位置) for x in DAG[idx] ])

# 以idx:(概率最大值，詞語末字位置)鍵值對形式保存在route中)

# route[x+1][0] 表示 詞路徑[x+1,N-1]的最大概率值,

# [x+1][0]即表示取句子x+1位置對應元組(概率對數，詞語末字位置)的概率對數

print(route)

輸出結果：

{7: (0, 0), 6: (0.001, 6), 5: (0.2, 6), 4: (0.25, 4), 3: (0.4, 4), 2: (0.5, 2), 1: (0.501, 1), 0: (0.6, 1)}

這是一個自底向上的動態規劃(逆序的解法)，從sentence的最后一個字開始倒序遍歷每個分詞方式的得分。然后將得分最高的情況以(概率得分值，詞語最后一個字的位置)這樣的tuple保存在route中?？磖oute的0: (0.6, 1)中的0.6，不就是我們求到的f(1)的max, 1: (0.501, 1)中的0.501不就是f(2)......后面大家對著看圖找規律吧。最后小操作一波，就可以把我們要的分詞結果打印出來了，結果和手推的是一樣的c(1~3) +c(3~4) +c(4~6) +c(6~8)。

x = 0

segs = []

while x < N:

y = route[x][1] + 1

word = sentence[x:y]

segs.append(word)

x = y

print(segs)

#輸出結果：['經常', '有', '意見', '分歧']

上面只是一些核心的思路，好多地方可以繼續優化的，比如把概率值轉換成-log(概率值)，目的是為了防止下溢問題，只是我舉例的概率值比較大，如果是一個超大的Dict,為了保證所有詞的概率之和約等于1，那每個詞對應的概率值會特別小。

(3)中文分詞以后得攻克的難點

1、分詞的規范，詞的定義還不明確，沒有一個公認的、權威的標準。

2、歧義詞的切分。這也從側面證實了中華文化博大精深。

3、未登錄的新詞。就是咱們的Dict里沒有的詞，對于3這個比2對分詞的影響大多了，目前結巴分詞對此采取的方法是：基于漢字成詞能力的HMM模型，使用維特比算法。

參考：

1、貪心學院nlp

2、自然語言處理理論與實戰 唐聃

總結

以上是生活随笔為你收集整理的维特比算法 python_维特比算法 实现中文分词 python实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。