Python 結巴分詞(jieba)源碼分析

閑來無事，在博客園的論壇里隨意遊盪，看到一個開源的python庫，名字叫做結巴分詞，一直很好奇這些自然語言的處理方式，但是網上的相關介紹卻少的可憐，僅有的一些博客寫介紹的比較淺。幸好代碼量不多，花了兩周的時間把代碼和設計的演算法仔細的梳理了一邊，供大家參考，也希望能夠拋磚引玉。

分詞演算法介紹

先看一下分詞用到了哪些演算法，文檔裡面如下介紹：

? 基於Trie樹結構實現高效的詞圖掃描，生成句子中漢字所有可能成詞情況所構成的有向無環圖（DAG）

? 採用了動態規劃查找最大概率路徑, 找出基於詞頻的最大切分組合

? 對於未登錄詞，採用了基於漢字成詞能力的HMM模型，使用了Viterbi演算法

實現方案

估計是我水平比較菜，反正我看完之後不知所云。廢話也不說了，下面好好來講講代碼，結巴分詞最頂層的目錄jieba下有如下文件，dict.txt是一個詞庫，裡面記錄了大約350000個詞語的詞頻和詞性，結巴分詞提供的功能介面都定義和實現在__init__.py中，finalseg文件夾中提供了隱馬爾科夫維特比演算法相關的代碼，用於文本切詞；analyse中提供了TF-IDF演算法和textrank演算法相關的實現，可以用於提取文章關鍵詞以及文本摘要；唯一讓我比較抑或的是posseg文件夾中的代碼，和finalseg極其相似，實在猜測不出添加這麼一個文件夾的意圖。

概括的講完結巴分詞的文件結構後，再詳細的講一講各個文件的內容。dict.txt的內容如下圖所示，裡面有每個詞的統計次數和詞性，在文檔中提到的演算法二中用到了詞的統計次數，但是似乎所有的演算法都沒有用到詞性，有想法的小夥伴可以嘗試改進一下。

_compat.py文件是處理python2和python3之間差異的一個文件，有一個函數strdecode專門用來將字元串轉換unicode, 感覺還蠻有用的

def strdecode(sentence): if not isinstance(sentence, text_type): try: sentence = sentence.decode(utf-8) except UnicodeDecodeError: sentence = sentence.decode(gbk, ignore) return sentence

__main__.py文件將底層的介面通過命令行的方式暴露給用戶，用戶可以設置自己的詞典，需要處理的文件，是否使用隱馬爾可夫模型，這個文件不涉及分詞的演算法，看起來沒有什麼難度，原來一直沒有搞清楚__main__.py和__init__.py這兩個文件的關係，通過萬能的度娘總算搞清楚了，這裡貼一個鏈接，http://www.tuicool.com/articles/iYRfe2 寫的非常通俗易懂。

__init__.py這個文件是結巴分詞的核心，裡面提供了分詞的介面：cut。它有三種模式：

1. 全模式，把句子中所有在詞庫中出現的詞都找出來

2. 不使用隱馬爾科夫模型的精確模式，基於最大概率路徑, 找出基於詞頻的最大切分組合

3. 同時使用最大概率路徑和隱馬爾科夫模型，對於未登錄詞也有比較好的切分效果

這三種模式都會根據字典生成句子中漢字構成的有向無環圖（DAG），實現的函數如下：

def get_DAG(sentence): global FREQ DAG = {} N = len(sentence) for k in xrange(N): tmplist = [] i = k frag = sentence[k] while i < N and frag in FREQ: if FREQ[frag]: tmplist.append(i) i += 1 frag = sentence[k:i + 1] if not tmplist: tmplist.append(k) DAG[k] = tmplist return DAG

以「但也並不是那麼出乎意料或難以置信」這句話作為輸入，生成的DAG如下，簡單的講就是把句子中詞的位置標記出來

0 [0] 但

1 [1] 也

2 [2] 並

3 [3, 4] 不是

4 [4] 是

5 [5, 6] 那麼

6 [6] 么

7 [7, 8, 10] 出乎意料

8 [8] 乎

9 [9, 10] 意料

10 [10] 料

11 [11] 或

12 [12, 13, 15] 難以置信

13 [13] 以

14 [14, 15] 置信

15 [15] 信

一、全模式 現在看一下全模式的代碼：

def __cut_all(sentence): dag = get_DAG(sentence) old_j = -1 for k, L in iteritems(dag): if len(L) == 1 and k > old_j: yield sentence[k:L[0] + 1] old_j = L[0] else: for j in L: if j > k: yield sentence[k:j + 1] old_j = j

就是把上面生成的DAG中的所有的組合顯示出來，還是以上面的句子為例，全模式切分的結果如下，是不是覺得這麼非常的easy。

但/也/並/不是/那麼/出乎/出乎意料/意料/或/難以/難以置信/置信

二、 不使用隱馬爾科夫模型的精確模式，用一個比較簡單的句子為例，輸入的句子是「難以置信」，按照全模式會輸出：難以/置信/難以置信 三個組合。作為一個將漢語的人，我們明顯知道最佳的分詞結果就是「難以置信」這一種結果。下面用最大概率的方法解釋為什麼是這個結果。子啊字典中我們可以查詢「難以置信」所有的組合以及它們出現的概率（除以所有詞出現的總次數）如下：

詞次數出現概率

難185053.08*10-4

以1361362.27*10-3

置111451.85*10-4

信111881.86*10-4

難以56819.45*10-5

置信641.06*10-6

難以置信1692.81*10-6

根據上面各詞的概率，可以算出「難以置信」所有分詞方式的概率，而最大出現的可能就是「難以置信」,而且它的概率相比其他組合高的可不是一倍兩倍。

分詞方式出現概率

難 以 置 信1.37*10-14

難以 置 信3.65*10-14

難 以 置信7.41*10-13

難以 置信1.01*10-10

難以置信2.81*10-6

實現的代碼如下，相信參考我的例子，看下面的代碼也就不是什麼大難題了，在計算概率的時候，結巴分詞用的方式是log函數

def calc(sentence, DAG, route): N = len(sentence) route[N] = (0, 0) logtotal = log(total) for idx in xrange(N - 1, -1, -1): route[idx] = max((log(FREQ.get(sentence[idx:x + 1]) or 1) - logtotal + route[x + 1][0], x) for x in DAG[idx]) def __cut_DAG_NO_HMM(sentence): DAG = get_DAG(sentence) route = {} calc(sentence, DAG, route) x = 0 N = len(sentence) buf = while x < N: y = route[x][1] + 1 l_word = sentence[x:y] if re_eng.match(l_word) and len(l_word) == 1: buf += l_word x = y else: if buf: yield buf buf = yield l_word x = y if buf: yield buf buf = 三、 同時使用最大概率路徑和隱馬爾科夫模型

由於這一部分設計到的理論知識比較多，建議先看一下相關的論文和博客。然後再通過代碼驗證對理論演算法的知識，可以更深刻的理解隱馬爾科夫模型。在這個地方中文句子作為可觀測序列，對應的隱藏狀態值集合為(B, M, E, S): {B:begin, M:middle, E:end, S:single}。分別代表每個狀態代表的是該字在詞語中的位置，B代表該字是詞語中的起始字，M代表是詞語中的中間字，E代表是詞語中的結束字，S則代表是單字成詞。

在HMM模型中文分詞中，我們的輸入是一個句子(也就是觀察值序列)，輸出是這個句子中每個字的狀態值。比如:「小明碩士畢業於中國科學院計算所」，隱藏序列為

BEBEBMEBEBMEBES，根據這個狀態序列我們可以進行切詞:BE/BE/BME/BE/BME/BE/S，所以切詞結果如下:小明/碩士/畢業於/中國/科學院/計算/所。n

finalseg中有BMES各個狀態間的轉移概率以及隱藏狀態對應於各個中文的發射概率，再根據維特比演算法，計算分詞就相當的容易了。由於對隱馬爾科夫理解有限，也就不瞎寫了，有興趣的可以看一下http://blog.csdn.net/likelet/article/details/7056068，寫的非常的贊。n

-------------------------------------

作者：腩啵兔子

出處：腩啵兔子的博客專欄

最近很多人私信問我問題，平常知乎評論看到不多，如果沒有及時回復，大家也可以加小編微信：tszhihu，進知乎大數據分析挖掘交流群，可以跟各位老師互相交流。謝謝。

推薦閱讀：