jieba 源碼解析
jieba 源碼解析
閱讀動機
jieba分詞 是Python 里面幾個比較流行的中文分詞工具之一。為了理解分詞工具的工作原理，以及實現細節對jieba進行了詳細的閱讀。
讀代碼之前，我有幾個問題是這樣的：
- 分詞工具的實現都有哪幾個步驟?
- 結巴分詞的文檔說是使用了 HMM模型 ，但是HMM 模型是如何運用在分詞工具中的？，以及模型是如何產生的？
- 幾乎所有的分詞工具都支持用戶添加詞庫，但是用戶詞庫到底在分詞過程中扮演什么角色？
簡介
jieba 分詞支持三種分詞模式，官方文檔給出了如下的Example
import jieba
seg list = jieba.cut("我來到北京清華大學", cut all=True) print("Full Mode: " + "/ ".join(seg_list)) # 全模式
seg list = jieba.cut("我來到北京清華大學", cut all=False) print("Default Mode: " + "/ ".join(seg_list)) # 精確模式
seg list = jieba.cut("他來到了網易杭研大廈") # 默認是精確模式 print(", ".join(seg list))
seg list = jieba.cut for search("小明碩士畢業于中國科學院計算所，后在日本京都大學深造") # 搜索引擎模式 print(", ".join(seg list))</code></pre>
考慮到文章篇幅的限制，我會詳細解讀默認模式也就是
jieba.cut``
方法的所有實現。 閱讀過程中會涉及一些算法原理，本文不做詳細解釋。
宏觀邏輯
上面面的流程圖很粗糙，但是很好的說明了大概的步驟。 首先使用概率無向圖，獲得最大概率路徑.概率無向圖的構建完全依賴于字典，最大概率路徑求解也是依賴字典中的詞頻。 最后使用HMM模型來解決未登錄詞(Out Of Vocabulary) ，所以在整個過程如果沒有模型也是可以的，只要你有一個很好的詞典。最大概率路徑的求解還有很多方法，記得 HanLP 的求解就有實現最短路徑。
粗分
首先會使用正則將文本切分，正則什么樣？就跟現則的是默認模式還是全模式。正則如下：
re_han_default = re.compile("([\u4E00-\u9FD5a-zA-Z0-9+#&\._]+)", re.U)
re_han_cut_all = re.compile("([\u4E00-\u9FD5]+)", re.U)
到底有什么區別：
我寫了個測試：
``
test str = u'我在重慶abc,他也在重慶? 1234你在重慶嗎' print (re han default.split(test str)) print (re han cut all.split(test
str))
輸出：
['', '我在重慶abc', ',', '他也在重慶', '? ', '1234你在重慶嗎', '']
['', '我在重慶', 'abc,', '他也在重慶', '? 1234', '你在重慶嗎', '']
``
上面輸出的list 里面每一個被成為block。
細分
對粗分產生的blok ‘abc’這樣的不能被
re.han
DAG構建
細分的第一步是構建 DAG 即有向無環圖。構建的核心代碼如下:
def get_DAG(self, sentence):
self.check_initialized() # 初始化，加載詞典
DAG = {}
N = len(sentence)
for k in xrange(N):
tmplist = []
i = k
frag = sentence[k]
while i < N and frag in self.FREQ:
if self.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: [2], 3: [3, 4], 4: [4], 5: [5, 6, 8], 6: [6, 7], 7: [7, 8], 8: [8]}
使用dict 來存儲圖數據結構。字典中的key 是沒個字對應句子的index,后面的value 是一個list就是可達的路徑。比如
{1：[1,2]}``
意思就是“來”和“來到”這兩個詞在詞典中存在。其他的類推。
圖的產生依賴于
self.FREQ
最大概率路徑求解
有了上面的DAG 下面求是求解最大概率路徑。這個問題有很多中方法，jieba 使用的是動態規劃。先不解釋動態規劃是什么，直接看代碼，
def calc(self, sentence, DAG, route):
N = len(sentence)
route[N] = (0, 0)
logtotal = log(self.total)
for idx in xrange(N - 1, -1, -1):
route[idx] = max((log(self.FREQ.get(sentence[idx:x + 1]) or 1) -
logtotal + route[x + 1][0], x) for x in DAG[idx])
真個過程就上面幾行。關鍵就在max 那一句。這個問題不在這里展開。但是有個小的技巧說下：在對很小的數據進行操作的時候，Python 也是可能向下溢出的，什么意思看下面的例子：
``
b = 0.0000001 print b**100
結果會打印
0.0``
所有有個方法就是取log 。這個方法在很多地方都是有用的。 上面還用到了連個
tuple
求解的結果如果分詞時候參數設置的不適用HMM模型，到這里就結束了。求解結果部分如下：key 同樣是對應的index.第二個就代表的是 來到 這個詞。
{0: (-32.587853155857076, 0), 1: (-27.379629658355885, 2),}
未登錄詞
上面的最大概率在一定程度上解決了歧義問題，但是在分詞里面還有另外一個問題未登錄詞問題也叫OOV(Out Of Vocabulary). jieba 使用HMM來識別未登錄詞。 比如: “我來到譽存科技” 這句話，產生的最大概率路徑是
{0: (-42.29693140266269, 0), 1: (-37.0887079051615, 2), 2: (-33.93639839927486, 2), 3: (-28.257272562332492, 3), 4: (-17.872975353951055, 4), 5: (-8.250710549196151, 6), 6: (-10.881580216048834, 6), 7: (0, 0)}
HMM
HMM 隱馬模型的定義自己可以去查，就算查完你也不一定能說清楚到底在分詞的時候怎么使用的，但是不查絕對不知道。 在分詞之前語料會被標注，標注的方式有很多中。其中比較多的是 BMES 對應的是B(begin)詞的開頭,M(Middle)詞的中間,E(End)詞的結束,S(Single)單個的詞 HMM有幾個概念，和分詞這個具體問題的對應關系如下：
- 狀態序列(state sequence)：BMES 這些狀態
- 觀測序列(observation sequence)：就是看到的需要分詞的句子，所有的字組成一個序列。
現在的問題就是一直觀測序列求狀態序列。但是第一部我們需要建立HMM模型。 HMM 有三個基本組成： 初始概率狀態概率分布A 狀態轉移矩陣pi 觀測概率分布B
如果有了上面三個元素一個HMM模型就是定好了。當然還有HMM模型有很多假設，此處省略。 jieba 是如何得到這三個變量的了。這就是HMM的學習問題 了。在標注好的語料之上。可以使用極大似然估計來估計這三個參數。這里也看到，語料是關鍵因素，語料的質量決定這三個參數。其實估計的過程不管其中的原理就是一些統計計算。jieba 把這三個元素分別存貯在三個py文件中：
prob start.py: 初始狀態概率
prob trans.py： 狀態轉移
prob_emit.py： 觀測概率分布</code></pre>
看看 prob_start:
P={'B': -0.26268660809250016,
'E': -3.14e+100,
'M': -3.14e+100,
'S': -1.4652633398537678}
-3.14e+100表示的是無窮小。意思就是第一個字不可能是E，或者M.只可能是B,S具體是多少，使用語料中的頻率做估計。
另外兩個元素用類似的方法在語料之上很容易得到。
有了上面的飲馬模型，但是如何通過觀測序列求最有可能的狀態序列?這時候就到 Viterbi algorithm 出場了。具體也不展開，反正很簡單。
到此jieba 分詞的真個過程和部分細節和原理都有了，要實現一個自己的分詞工具還會遠嗎？
來自：http://midday.me/article/003023dc3f814bc493b37c50b2a9ee71