How jieba works, part 1

有做過中文自然語言處理 (natural language processing, NLP) 的夥伴們一定都會面對中文分詞的問題：要怎麼把一個句子切成多個詞彙讓電腦理解一個句子的組成。

例如『我昨天去上海交通大學與老師討論量子力學』可以被分詞成『我』『昨天』『去』『上海』『交通』『大學』『與』『老師』『討論』『量子』『力學』。但這要如何實現呢？

結巴是一個由 Python 實現的中文分詞工具。除了分詞以外也支援關鍵字抽取 (TF-IDF keyword extraction) 與詞性標記 (part-of-speech tagging)。本文章會著重在分詞的功能上。

結巴方便好用，但它到底是怎麼分詞的？

以下是針對結巴演算法的白話解釋。

簡短解釋

從知識與經驗中我們知道某些字 (character) 經常一起出現，例如『大』與『學』、『老』與『師』。這些字的組合我們稱為單字，或是詞 (word)。而許多詞的收集就是辭典或詞彙 (dictionary or vocabulary)。

『從知識與經驗中我們知道某些字經常一起出現』是一個關鍵：我們對於詞的分辨來自於知識與經驗。知識是我們的辭典，而經驗是我們從日常生活中歸納出的統計規則，用來分辨沒有看過的詞。

知識 == 辭典
經驗 == 統計

結巴也是用同樣的方式分詞。

結巴 Github 上有這樣的解釋：

算法

基于前缀词典实现高效的词图扫描，生成句子中汉字所有可能成词情况所构成的有向无环图 (DAG)

采用了动态规划查找最大概率路径, 找出基于词频的最大切分组合

对于未登录词，采用了基于汉字成词能力的 HMM 模型，使用了 Viterbi 算法

什麼意思？我們一行一行看。

第一點：

前綴字典 (Trie; prefix dictionary) 是一種資料結構，由詞的開頭字(前綴)作為起點，剩下的字都是向下延伸的節點。

結巴會產生這樣的辭典資料結構讓電腦可以快速檢索 (實做上是一個 Python dict)。
結巴再逐字檢索前綴字典，找出可能成詞的選項並建構出一個『有向無環圖』(directed acyclic graph, DAG. 實做上也是一個 Python dict) ：

『有向』(directed) 指有方向的，以範例來說是從上往下。『無環』(acyclic) 指這個圖的流程沒有迴圈。上面的兩張圖皆是『有向無環圖』。

第二點：

從前面建構的有向無環圖 (DAG) 中找出最佳分詞點是用動態規劃 (dynamic programming) 。而最佳分詞點的評分方法就是該路徑的詞頻。這主要是針對一些可切也可不切的詞。例如『交通大學』可以分成『交通』+『大學』，也可以不分開。究竟該如何分詞會用詞頻判斷。

第一點與第二點都是執行知識的部份：把句子中的字與前綴字典做比對，找出分詞點。而下面的第三點則是經驗的實現。

第三點：

未登錄詞是沒有記載在前綴字典內的詞。
『基於漢字成詞能力的 Hidden Markov model (HMM) 模型』是一個用大量的已分詞文本所訓練的統計模型。模型登錄中文每個字位於詞頭、詞中、詞尾、或是單獨存在的分佈統計機率。結巴作者有提到訓練文本來源包括 PFR 人民日報標注語料庫，還有一些網路小說。
Viterbi 演算法會從 HMM 模型中找出最大機率的組合。舉例：假設『大學』是未登錄詞。先從 HMM 計算『大』與『學』位於詞頭、詞中、詞尾、或是單獨存在的機率組合，再使用 Viterbi 演算法得出『大』位於『詞頭』、『學』位於『詞尾』的組合，所以將『大學』視為一個詞。如果這兩個字得出的組合都是『單獨存在』，那麼『大學』則會被分詞成『大』、『學』。

接下來會透過一個範例詳細地解釋結巴如何使用這些資料結構與演算法。

詳細解釋

當我們用結巴分詞『我昨天去上海交通大學與老師討論量子力學』時...

from jieba import cut

tokens = cut("我昨天去上海交通大學與老師討論量子力學", HMM=True)

for t in tokens:
    print(t)

會有下列輸出：

Building prefix dict from the default dictionary ...
Dumping model to file cache /tmp/jieba.cache
Loading model cost 0.500 seconds.
Prefix dict has been built successfully.
我
昨天
去
上海
交通
大學
與
老師
討論
量子
力學

發生了什麼事？

第一步：初始化

先從 debug 訊息看：

Building prefix dict from the default dictionary ...

這裡的 default dictionary 指的是結巴內建的辭典檔案，位於 site-packages/jieba/dict.txt (線上瀏覽)。部份內容如下：

AT&T 3 nz
B超 3 n
c# 3 nz
C# 3 nz
c++ 3 nz
C++ 3 nz
T恤 4 n
A座 3 n
A股 3 n
A型 3 n
...

內建辭典總共有 349,046 列 (rows)，每列以空格分三個欄位：

詞：獨特、不重複。
詞頻：這個次數是結巴作者在收集大量文本後所統計出來的數字。
詞性標記：自然語法上的類別，例如動詞 (v)、名詞 (n) 等分類。分類標籤是參照1998人民日報標注語料庫 (PFR)。

結巴從這個辭典建構出一個 prefix dict，也就是上面第一點提到的前綴字典。

在建構前綴字典的時候結巴會逐列地蒐集每一個詞與它的詞頻。此外，每一個詞的前綴也會加入前綴字典。以內建辭典的前三個詞為範例，在建構前綴字典後會有下列內容：

{
    "A": 0,
    "AT": 0,
    "AT&": 0,
    "AT&T": 3,
    "B": 0,
    "B超": 3,
    "c": 0,
    "c#": 3,
    ...
}

AT&T 被拆解成 ["A", "AT", "AT&", "AT&T"] ，其他詞也以此類推。

這個前綴字典總共有 498,113 個 key 。而所有的詞頻加總為 60,101,967。

建構前綴字典的程式碼位於 Tokenize.genpfdict() 。

Tokenizer.genpfdict() 執行完畢後會把前綴字典存在 Tokenizer 物件的 self.FREQ 變數內、把字典的詞頻加總存在 self.total 變數內。

Dumping model to file cache /tmp/jieba.cache

self.FREQ (前綴字典) 與 self.total (所有詞頻的加總) 接下來會以 Python tuple 的格式用 marshal 模組匯出 (serialize) 成一個檔案，存在 /tmp/jieba.cache 。結巴在初始化的時候會試著讀取這個檔案，如果存在就不用再耗時建構一次前綴字典。

Loading model cost 0.500 seconds.
Prefix dict has been built successfully.

結巴在此完成了初始化。共花了 0.5 秒。

接下來才要開始分詞。

第二步：逐字檢索前綴字典，建構『有向無環圖』(directed acyclic graph, DAG)

剛剛建構好的前綴字典在這派上用場。

以句子的每個字為起點，從前綴字典中查詢字與它後面的N個字是否有在字典內且詞頻大於零。若有，則在 DAG 上加入字與第N字的 index 。沒有的話就只加入字的 index 。

字與它的 index:

我  0
昨  1
天  2
去  3
上  4
...
量  15
子  16
力  17
學  18

從前綴字典中查詢『我』
- 存在且記數大於零： DAG[0] 加入 0 (我)

從前綴字典中查詢『我昨』
- 不存在或記數不大於零：查下一個字

從前綴字典中查詢『昨』
- 存在且記數大於零： DAG[1] 加入 1 (昨)

從前綴字典中查詢『昨天』
- 存在且記數大於零： DAG[1] 加入 2 (昨天)

從前綴字典中查詢『昨天去』
- 不存在或記數不大於零：查下一個字

從前綴字典中查詢『天』
- 存在且記數大於零： DAG[2] 加入 2 (天)

從前綴字典中查詢『天去』
- 不存在或記數不大於零：查下一個字

從前綴字典中查詢『去』
- 存在且記數大於零： DAG[3] 加入 3 (去)

...(以此類推)

利用前綴字典我們建構了一個潛在詞的 DAG ：

{
    0: [0],        # 我
    1: [1, 2],     # 昨, 昨天
    2: [2],        # 天
    3: [3],        # 去
    4: [4, 5],     # 上, 上海
    5: [5],        # 海
    6: [6, 7],     # 交, 交通
    7: [7],        # 通
    8: [8],        # 大
    9: [9],        # 學
    10: [10],      # 與
    11: [11],      # 老
    12: [12],      # 師
    13: [13],      # 討
    14: [14],      # 論
    15: [15, 16],  # 量, 量子
    16: [16, 17],  # 子, 子力
    17: [17],      # 力
    18: [18],      # 學
}

建構 DAG 的程式碼位於 Tokenizer.get_DAG() 。

在這一步中，我們找出了幾個潛在的分詞點：

昨天
上海
交通
量子
子力

『昨』與『天』應該被分開嗎？『量子』跟『子力』有互相重疊的字，該選哪個做分詞呢？下一步就是要找出最適合的詞(路徑)。

第三步：找出最大概率路徑

我們從上一步的 DAG 中找出了多個潛在分詞點，接下來會用詞頻找出最大概率路徑，比較它們分開與不分開的機率。

計算路徑概率可以從句子頭往句子尾算，或是從句子尾往句子頭算。結巴是採用後者，因為中文句子的重心通常落在後面，所以正確率會高於從頭到尾計算。

計算最大路徑概率的方法如下：

根據詞頻計算每個字的機率
走最高的機率的字(分支)

每個字的機率是它的詞頻除以前綴字典所有詞頻的總和，再乘以前字的機率：

字_機率= (字_詞頻/ 詞頻總和) * 前字_機率

若前字不只一個，則取最大機率的前字。

計算最大概率路徑的程式碼位於 Tokenizer.calc() 內。

首先計算『學』的機率：

總數 = 60,101,967
學_詞頻 = 6
學_機率 = (學_詞頻 / 總數) * 前字_機率
學_機率 = (6 / 60,101,967) * 1.0
學_機率 = 0.0000000998303433230396666

因為『學』在路徑的起點，所以前字_機率用 1.0 作為替代值（提醒：我們是從句子尾巴往頭的方向計算，所以這裡的前後指的是句子尾首的方向）。

在繼續下去之前要先解決一個問題：某些字的詞頻很低，除以一個很大的分母會得出很小的機率。多個低機率小數點相乘所可能會算術下溢而歸零。為了避免下溢，結巴作者將所有的數據轉成 log 數字，再計算 log 機率。在此之後的所有機率運算都是 log 機率。

獨立事件的機率原本應要相乘，轉成 log 機率後要相加。除法則要相減：

總數 = log(60,101,967)
總數 = 17.91155312775522
學_詞頻 = log(6)
學_詞頻 = 1.791759469228055
前字_機率 = log(1)
前字_機率 = 0.0

學_機率 = (學_詞頻 - 總數) + 前字_機率
學_機率 = (1.791759469228055 - 17.91155312775522) + 0.0
學_機率 = -16.119793658527165

接下來算『力』的機率：

總數 = 17.91155312775522
前字_機率 = 學_機率
前字_機率 = -16.119793658527165
力_詞頻 = log(10,777)
力_詞頻 = 9.285169512596832

力_機率 = (力_詞頻 - 總數) + 前字_機率
力_機率 = (9.285169512596832 - 17.91155312775522) + -16.119793658527165
力_機率 = -24.746177273685554

接下來的『子』與『子力』要特別注意：『子』的前字是『力』，而『子力』的前字是『學』。

前字_機率 = 力_機率
前字_機率 = -24.746177273685554
子_詞頻 = log(19,089)
子_詞頻 = 9.856867531900901
子_機率 = (子_詞頻 - 總數) + 前字_機率
子_機率 = (9.856867531900901 - 17.91155312775522) + -24.746177273685554
子_機率 = -32.80086286953987

前字_機率 = 學_機率
前字_機率 = -16.119793658527165
子力_詞頻 = log(12)
子力_詞頻 = 2.4849066497880004
子力_機率 = (子力_詞頻 - 總數) + 前字_機率
子力_機率 = (2.4849066497880004 - 17.91155312775522) + -16.119793658527165
子力_機率 = -31.546440136494383

接下來計算『量』與『量子』。但是『量』有兩個前字：『子』與『子力』。在計算『量』時應取兩個前字的的最大值，也就是子力_機率。

前字_機率 = 子力_機率
前字_機率 = -31.546440136494383
量_詞頻 = log(10,182)
量_詞頻 = 9.228376734462282
量_機率 = (量_詞頻 - 總數) + 前字_機率
量_機率 = (9.228376734462282 - 17.91155312775522) + -31.546440136494383
量_機率 = -40.22961652978732

前字_機率 = 力_機率
前字_機率 = -24.746177273685554
量子_詞頻 = log(617)
量子_詞頻 = 6.424869023905388
量子_機率 = (量子_詞頻 - 總數) + 前字_機率
量子_機率 = (6.424869023905388 - 17.91155312775522) + -24.746177273685554
量子_機率 = -36.232861377535386

在計算『論』時應取兩個前字的最大值，也就是量子_機率。『論』在這的詞頻是 1 因為它沒有出現在前綴字典內。

前字_機率 = 量子_機率
前字_機率 = -36.232861377535386
論_詞頻 = log(1)
論_詞頻 = 0.0
論_機率 = (論_詞頻 - 總數) + 前字_機率
論_機率 = (0.0 - 17.91155312775522) + -36.232861377535386
論_機率 = -54.144414505290605

接下來的『討』、『師』、『老』、『與』、『學』、『大』、『通』、『交』、『交通』的計算方式與上面一樣，所以就不再贅述。

在計算『海』與『上海』時，從他們的兩個前字『交』與『交通』取最大機率，『交通』勝出。

前字_機率 = 交通_機率
前字_機率 = -139.2252963306866
海_詞頻 = log()
海_詞頻 = 9.177403871729918
海_機率 = (海_詞頻 - 總數) + 前字_機率
海_機率 = (9.177403871729918 - 17.91155312775522) + -139.2252963306866
海_機率 = -147.9594455867119

上海_詞頻 = log()
上海_詞頻 = 9.703633190449867
上海_機率 = (上海_詞頻 - 總數) + 前字_機率
上海_機率 = (9.703633190449867 - 17.91155312775522) + -139.2252963306866
上海_機率 = -147.43321626799195

剩下路徑的算法都與上述一樣，所以就不再贅述。

到這，我們找出了所有 DAG 的各個路徑機率：

Tokenizer.calc() 在這會把最佳路徑存入 Tokenizer 物件的 self.route 變數內：

route = {
    19: (0, 0),
    18: (-16.119793658527165, 18), # 學
    17: (-24.746177273685554, 17), # 力
    16: (-31.546440136494383, 17), # 子力
    15: (-36.232861377535386, 16), # 量子
    14: (-54.144414505290605, 14), # 論
    13: (-72.05596763304582, 13),  # 討
    12: (-85.13123885384957, 12),  # 師
    11: (-92.62579241687736, 11),  # 老
    10: (-108.45790400295274, 10), # 與
    9: (-124.5776976614799, 9),    # 學
    8: (-130.61099494689685, 8),   # 大
    7: (-139.3501172757491, 7),    # 通
    6: (-139.2252963306866, 7),    # 交通
    5: (-147.9594455867119, 5),    # 海
    4: (-147.43321626799195, 5),   # 上海
    3: (-153.62156679796965, 3),   # 去
    2: (-161.04242921182504, 2),   # 天
    1: (-163.07631388432372, 2),   # 昨天
    0: (-168.28453738182492, 0),   # 我
}

有了所有路徑的概率，我們就可以找出從句子頭到句子尾的最大概率路徑：

使用前綴字典分詞執行到這裡結束。目前分詞結果有這些：

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

回憶一開始呼叫結巴分詞時有指定參數 HMM=True:

tokens = cut("我昨天去上海交通大學與老師討論量子力學", HMM=True)

如果 HMM=False ，結巴會在這一步結束分詞並回傳上述的分詞結果。

如果 HMM=True ，結巴會把尚未分詞的單一字交給一個『隱藏式馬可夫模型』分詞，進入下一個步驟。

但在進入下一個步驟前，先了解何謂『馬可夫模型』、『隱藏式馬可夫模型』、與 Viterbi 演算法。

結巴分詞解析三部曲, 第一集