How jieba works, part 3

本篇將用 Part 2 介紹的隱藏式馬可夫模型與 Viterbi 演算法將剩下的字 (大、學、與、老、師、討、論、力、學) 分詞。

字的隱藏狀態

一個人的身體可以有健康、生病的隱藏狀態。那一個字可以有幾種？結巴的程式碼定義了四種隱藏狀態：詞首、詞中、詞尾、以及單獨存在，分別用 B, M, E, S 標示。這四種狀態其實就是字位於詞的不同位置。

例如：

• 我: S
  • 『我』只有一個字，所以標示 S 單獨存在。
• 的: S
  • 『的』只有一個字，所以標示 S 單獨存在。
• 晚餐: BE
  • 『晚』位於詞首，標示 B 。『餐』位於詞尾，標示 E 。
• 三國誌: BME
  • 『三』位於詞首，標示 B 。『國』位於詞中，標示 M 。『誌』位於詞尾，標示 E 。
• 澳大利亞: BMME
  • 『澳』位於詞首，標示 B 。『大』位於詞中，標示 M 。『利』位於詞中，標示 M 。『亞』位於詞尾，標示 E 。

為了統計中文字的狀態數據(初始機率、狀態轉移機率、發射機率)，結巴作者收集了一些已分詞的語料庫與未分詞的網路小說。已分詞的語料庫包含微軟亞洲研究院語料庫 (MSR)與1998人民日報標注語料庫 (PFR)。未分詞的網路小說則是用 ICTCLAS 免費版分詞。

這些統計數據存放在 jieba/finalseg 中：

• prob_start: 初始機率
• prob_trans: 狀態轉移機率
• prob_emit: 發射機率

.p 結尾的檔案是 Python pickle 模組 serialize 之後的檔案，內容皆是一個 Python dict 。 .py 結尾的檔案是以明文 Python dict 的資料結構儲存。兩種檔案的內容是一樣的。所有的數字都是 log 機率。

prob_start 的內容如下：

P = {
    'B': -0.26268660809250016,
    'M': -3.14e+100,
    'E': -3.14e+100,
    'S': -1.4652633398537678
}

這組機率的 B 與 S 最大， E 與 M 則非常小。一個句子的開頭字位於詞首或單獨存在的機率最高，不會是詞中或是詞尾，符合直覺。

prob_trans 的內容如下：

P = {
    # 從 B 轉移到 E 的機率、從 B 轉移到 M 的機率
    'B': {'E': -0.510825623765990, 'M': -0.916290731874155},

    # 從 M 轉移到 E 的機率、從 M 轉移到 M 的機率
    'M': {'E': -0.33344856811948514, 'M': -1.2603623820268226},

    # 從 E 轉移到 B 的機率、從 E 轉移到 S 的機率
    'E': {'B': -0.5897149736854513, 'S': -0.8085250474669937},

    # 從 S 轉移到 B 的機率、從 S 轉移到 S 的機率
    'S': {'B': -0.7211965654669841, 'S': -0.6658631448798212}
}

比較 B->E 與 B->M 的機率，前者大於後者，因為中文有許多只有兩個字組成的詞，符合直覺。B 對應的轉換狀態只有 E 與 M ，因為詞首的後面只會有詞尾或詞中。

prob_emit 的部份內容如下：

P = {
    'B': { # 6,857 items
        '一': -3.6544978750449433,
        '丁': -8.125041941842026,
        '七': -7.817392401429855,
        # ...
        '龚': -9.557108305917183,
        '龜': -10.895131537474946,
        '龟': -10.895131537474946,
    },
    'M': { # 6,409 items
        '一': -4.428158526435913,
        '丁': -7.932945687598502,
        '七': -6.559715525951586,
        # ...
        '龚': -14.14915250738439,
        '龜': -11.058110054026073,
        '龟': -11.058110054026073,
    },
    'E': { # 7,439 items
        '一': -6.044987536255073,
        '丁': -9.075800412310807,
        '七': -9.198842005220659,
        # ...
        '龚': -12.729311722586953,
        '龜': -10.574067217491615,
        '龟': -10.574067217491615,
    },
    'S': { # 14,519 items
        ':': -15.828865681131282,
        '一': -4.92368982120877,
        '丁': -9.024528361347633,
        '丂': -16.522012861691227,
        '七': -8.269436469795775,
        # ...
        '龛': -11.807988270791054,
        '龜': -10.409437488834186,
        '龟': -10.409437488834186,
        '龠': -15.605722129817071,
        '龢': -10.61937952828986,
    },
}

這個 dict 包括了中文字與它們位於詞首、詞中、詞尾、以及單獨存在的發射機率。

• B 組中最高機率的五個字:
  • ('一', -3.6544978750449433)
  • ('不', -4.274262055936421)
  • ('中', -4.596743315282086)
  • ('大', -4.615103716830059)
  • ('人', -4.673338450394872)
• M 組中最高機率的五個字:
  • ('民', -3.8365863831702627)
  • ('大', -3.8459362685920344)
  • ('国', -4.1246250064725185)
  • ('國', -4.1246250064725185)
  • ('人', -4.374134892559791)
• E 組中最高機率的五個字:
  • ('国', -4.505006128890268)
  • ('國', -4.505006128890268)
  • ('个', -4.601848094892821)
  • ('個', -4.601848094892821)
  • ('人', -4.711845968270672)
• S 組中最高機率的五個字:
  • ('的', -2.2401766800588425)
  • ('了', -3.5233618135136173)
  • ('是', -3.626561376888877)
  • ('在', -3.717220480130881)
  • ('和', -3.9869692581995793)

這些數據反應了原始資料的特性。

我們要分詞的字剩下大、學、與、老、師、討、論、力、學。找出這些字的隱藏狀態並規劃路線。

第一步：算出第一字的初始隱藏狀態

第一個字『大』：

大(B) = start(B) + emit(B|大)
大(B) = -0.26268660809250016 + -4.615103716830059
大(B) = -4.877790324922559

大(M) = start(M) + emit(M|大)
大(M) = -3.14e+100 + -3.8459362685920344
大(M) = -3.14e+100

大(E) = start(E) + emit(E|大)
大(E) = -3.14e+100 + -5.4677215287335095
大(E) = -3.14e+100

大(S) = start(S) + emit(S|大)
大(S) = -1.4652633398537678 + -5.336904199912897
大(S) = -6.802167539766665

第二步：找出從第一字到第二字的最佳路徑

為了方便計算，結巴作者把抵達每個隱藏狀態的路徑起點放在 PrevStatus 的變數中：

PrevStatus = {
    'B': 'ES',
    'M': 'MB',
    'E': 'BM',
    'S': 'SE',
}

抵達於 B 狀態的路徑可能源自於前一字的狀態 E 或狀態 S ，以此類推。

第二個字『學』：

『學』的每個隱藏狀態都有兩條潛在路徑：

• 抵達 學(B)
  • 路徑1: 大(E) --> 學(B)
  • 路徑2: 大(S) --> 學(B)
• 抵達 學(M)
  • 路徑3: 大(M) --> 學(M)
  • 路徑4: 大(B) --> 學(M)
• 抵達 學(E)
  • 路徑5: 大(B) --> 學(E)
  • 路徑6: 大(M) --> 學(E)
• 抵達 學(S)
  • 路徑7: 大(S) --> 學(S)
  • 路徑8: 大(E) --> 學(S)

從每一個組合中挑出最高機率路徑：

路徑 = 前字狀態機率 + 轉換機率(前狀態->現狀態)

路徑1 = 大(E) + trans(E->B)
路徑1 = -3.14e+100 + -0.5897149736854513
路徑1 = -3.14e+100

路徑2 = 大(S) + trans(S->B)
路徑2 = -6.802167539766665 + -0.7211965654669841
路徑2 = -7.523364105233649

路徑2勝出: 大(S) -> 學(B)


路徑3 = 大(M) + trans(M->M)
路徑3 = -3.14e+100 + -1.2603623820268226
路徑3 = -3.14e+100

路徑4 = 大(B) + trans(B->M)
路徑4 = -4.877790324922559 + -0.916290731874155
路徑4 = -5.794081056796714

路徑4勝出: 大(B) -> 學(M)


路徑5 = 大(B) + trans(B->E)
路徑5 = -4.877790324922559 + -0.51082562376599
路徑5 = -5.388615948688549

路徑6 = 大(M) + trans(M->E)
路徑6 = -3.14e+100 + -0.33344856811948514
路徑6 = -3.14e+100

路徑5勝出: 大(B) -> 學(E)


路徑7 = 大(S) + trans(S->S)
路徑7 = -6.802167539766665 + -0.6658631448798212
路徑7 = -7.468030684646486

路徑8 = 大(E) + trans(E->S)
路徑8 = -3.14e+100 + -0.8085250474669937
路徑8 = -3.14e+100

路徑7勝出: 大(S) -> 學(S)

從第一字到第二字(大->學)的可能路徑如下：

抵達『學』的各個隱藏狀態是較有可能是來自大(B)與大(S)。從大(M)與大(E)出發的路徑因為機率較低而被淘汰。

第三步：計算第二字的隱藏狀態機率

現在我們知道來自『大』的路徑，可以著手計算『學』隱藏狀態機率。

學(B) = max(路徑1, 路徑2) + emit(B|學)
學(B) = -7.523364105233649 + -5.575266840863322
學(B) = -13.098630946096971

學(M) = max(路徑3, 路徑4) + emit(M|學)
學(M) = -5.794081056796714 + -4.878752378980544
學(M) = -10.672833435777259

學(E) = max(路徑5, 路徑6) + emit(E|學)
學(E) = -5.388615948688549 + -5.428427109257772
學(E) = -10.817043057946321

學(S) = max(路徑7, 路徑8) + emit(S|學)
學(S) = -7.468030684646486 + -7.446232983110739
學(S) = -14.914263667757226

第四步：重複第二、三步來算出剩下的路徑與隱藏狀態

找出從『學』到『與』的路徑

『與』的每個隱藏狀態都有兩條潛在路徑：

• 抵達 與(B)
  • 路徑1: 學(E) --> 與(B)
  • 路徑2: 學(S) --> 與(B)
• 抵達 與(M)
  • 路徑3: 學(M) --> 與(M)
  • 路徑4: 學(B) --> 與(M)
• 抵達 與(E)
  • 路徑5: 學(B) --> 與(E)
  • 路徑6: 學(M) --> 與(E)
• 抵達 與(S)
  • 路徑7: 學(S) --> 與(S)
  • 路徑8: 學(E) --> 與(S)

從每一個組合中挑出最高機率路徑：

路徑 = 前字狀態機率 + 轉換機率(前狀態->現狀態)

路徑1 = 學(E) + trans(E->B)
路徑1 = -10.817043057946321 + -0.5897149736854513
路徑1 = -11.406758031631773

路徑2 = 學(S) + trans(S->B)
路徑2 = -14.914263667757226 + -0.7211965654669841
路徑2 = -15.63546023322421

路徑1勝出: 學(E) -> 與(B)


路徑3 = 學(M) + trans(M->M)
路徑3 = -10.672833435777259 + -1.2603623820268226
路徑3 = -11.933195817804082

路徑4 = 學(B) + trans(B->M)
路徑4 = -13.098630946096971 + -0.916290731874155
路徑4 = -14.014921677971126

路徑3勝出: 學(M) -> 與(M)


路徑5 = 學(B) + trans(B->E)
路徑5 = -13.098630946096971 + -0.51082562376599
路徑5 = -13.609456569862962

路徑6 = 學(M) + trans(M->E)
路徑6 = -10.672833435777259 + -0.33344856811948514
路徑6 = -11.006282003896743

路徑6勝出: 學(M) -> 與(E)


路徑7 = 學(S) + trans(S->S)
路徑7 = -14.914263667757226 + -0.6658631448798212
路徑7 = -15.580126812637047

路徑8 = 學(E) + trans(E->S)
路徑8 = -10.817043057946321 + -0.8085250474669937
路徑8 = -11.625568105413315

路徑8勝出: 學(E) -> 與(S)

從『學』到『與』的可能路徑如下：

抵達『與』的各個隱藏狀態是較有可能是來自學(M)與學(E)。從學(B)與學(S)出發的路徑因為機率較低而被淘汰。

計算『與』的隱藏狀態

與(B) = max(路徑1, 路徑2) + emit(B|與)
與(B) = -11.406758031631773 + -8.355569307500769
與(B) = -19.76232733913254

與(M) = max(路徑3, 路徑4) + emit(M|與)
與(M) = -11.933195817804082 + -8.445370032728189
與(M) = -20.37856585053227

與(E) = max(路徑5, 路徑6) + emit(E|與)
與(E) = -11.006282003896743 + -8.355821418935358
與(E) = -19.3621034228321

與(S) = max(路徑7, 路徑8) + emit(S|與)
與(S) = -11.625568105413315 + -5.226099782104967
與(S) = -16.851667887518282

找出從『與』到『老』的路徑

『老』的每個隱藏狀態都有兩條潛在路徑：

• 抵達 老(B)
  • 路徑1: 與(E) --> 老(B)
  • 路徑2: 與(S) --> 老(B)
• 抵達 老(M)
  • 路徑3: 與(M) --> 老(M)
  • 路徑4: 與(B) --> 老(M)
• 抵達 老(E)
  • 路徑5: 與(B) --> 老(E)
  • 路徑6: 與(M) --> 老(E)
• 抵達 老(S)
  • 路徑7: 與(S) --> 老(S)
  • 路徑8: 與(E) --> 老(S)

從每一個組合中挑出最高機率路徑：

路徑 = 前字狀態機率 + 轉換機率(前狀態->現狀態)

路徑1 = 與(E) + trans(E->B)
路徑1 = -19.3621034228321 + -0.5897149736854513
路徑1 = -19.951818396517552

路徑2 = 與(S) + trans(S->B)
路徑2 = -16.851667887518282 + -0.7211965654669841
路徑2 = -17.572864452985264

路徑2勝出: 與(S) -> 老(B)


路徑3 = 與(M) + trans(M->M)
路徑3 = -20.37856585053227 + -1.2603623820268226
路徑3 = -21.638928232559092

路徑4 = 與(B) + trans(B->M)
路徑4 = -19.76232733913254 + -0.916290731874155
路徑4 = -20.678618071006696

路徑4勝出: 與(B) -> 老(M)


路徑5 = 與(B) + trans(B->E)
路徑5 = -19.76232733913254 + -0.51082562376599
路徑5 = -20.27315296289853

路徑6 = 與(M) + trans(M->E)
路徑6 = -20.37856585053227 + -0.33344856811948514
路徑6 = -20.712014418651755

路徑5勝出: 與(B) -> 老(E)


路徑7 = 與(S) + trans(S->S)
路徑7 = -16.851667887518282 + -0.6658631448798212
路徑7 = -17.517531032398104

路徑8 = 與(E) + trans(E->S)
路徑8 = -19.3621034228321 + -0.8085250474669937
路徑8 = -20.170628470299093

路徑7勝出: 與(S) -> 老(S)

從『與』到『老』的可能路徑如下：

抵達『老』的各個隱藏狀態是較有可能是來自與(B)和與(S)。從與(M)和與(E)出發的路徑因為機率較低而被淘汰。

計算『老』的隱藏狀態

老(B) = max(路徑1, 路徑2) + emit(B|老)
老(B) = -17.572864452985264 + -6.115270002288356
老(B) = -23.68813445527362

老(M) = max(路徑3, 路徑4) + emit(M|老)
老(M) = -20.678618071006696 + -7.104247390255019
老(M) = -27.782865461261714

老(E) = max(路徑5, 路徑6) + emit(E|老)
老(E) = -20.27315296289853 + -8.062200135058678
老(E) = -28.335353097957206

老(S) = max(路徑7, 路徑8) + emit(S|老)
老(S) = -17.517531032398104 + -6.798160477523745
老(S) = -24.315691509921848

以此類推

剩下的字都是同樣的步驟，先找出潛在路徑再計算隱藏狀態。

到最後的路徑與隱藏狀態機率如下：

『論』因為在這段句子的尾巴，所以只會是 E (詞尾) 或是 S (單一存在) 隱藏狀態：

論E和論S中，E 的隱藏機率較高所以論E勝出。由此回朔即可知道最有可能的路徑：

使用 Viterbi 演算法分詞結果如下：

值得注意的是，在計算路徑時，我們並不是單純地取每個字最高的隱藏狀態。如果這麼做我們會得到錯誤結果：B M S B E B E

(最高機率用粗體表示)

第二個字『學』的最高隱藏狀態是 M ，但是如果選擇 M ，那以『大』為首的詞就沒有結尾了。 M 代表詞中，後面應該要緊跟著另一個詞中 (M) 或一個詞尾 (E) 。單純取最高隱藏狀態會忽略已被捨棄的路徑，造成錯誤。

結語

到這為止我們已經將『我昨天去上海交通大學與老師討論量子力學』做了部份分詞：

我  昨天  去  上海  交通  大學  與  老師  討論  量子  力  學

最後面的『力』和『學』因為沒有在前綴字典內，所以結巴會用本篇敘述的方式分詞。詳細算法就留給讀到這的你當練習作業囉。

參考

• jieba issue #2 请问这个库的授权
• jieba issue #7 模型的数据是如何生成的?
• jieba issue #49 关于利用动态规划求解最大概率路径
• jieba 分词的原理
• THULAC 与代表性分词软件的性能对比
• 英汉翻译实用教程 第十一章 128頁, 清华大学出版社
• 1998人民日报标注语料库 (PFR)
• 微软亚洲研究院语料库 (MSR)
• Chinese Treebank 8.0
• A Contrastive Study of Chinese Text Segmentation Tools in Marketing
• Wikipedia: Markov model
• Wikipedia: Markov chain
• Wikipedia: Hidden Markov model
• Wikipedia: Viterbi algorithm