jieba源碼解析（一）——中文分詞

全模式

1.第一步載入字典：

得到的字典樹存在self.FREQ中。例如對於詞"不拘一格"，在字典樹lfreq中是這樣的{"不" : 0, "不拘" : ,"不拘一" , 0, "不拘一格" : freq} 其中的freq就是在dict.txt中記錄的詞頻。

2.構造DAG：

例如:{0:[1,2,3]} 這樣一個簡單的DAG, 就是表示0位置開始, 在1,2,3位置都是詞, 就是說0~1, 0~2,0~3這三個起始位置之間的字元

詳細分析如下句子的生成

例如我來到北京清華大學

先把『我』拿出來，在字典里，key是0，表示第0開始，value是個list，先在value append(0),並且try 『我來』是否在字典，不在，那麼結束位置0尋找可能的分詞。此時

DAG的字典是 {0:[0]}

到『來』key=1，『來』在字典因此value append（1），try 『來到』 發現也在字典中， 繼續 append（2），再try『來到北』，不在，那麼結束位置1尋找可能的分詞。此時的DAG的字典是 {0:[0]，1:[1,2]}。

接著到key=2.。。。依次類推，最後形成的字典：

這邊5很有趣，結果是5,6,8 對應的是清華大學，當開始『清』，try『清華』在字典，就繼續嘗試『清華大』發現還在，可是為啥沒有append呢，因為這個append是有條件的，詞次數不為0，既然在字典，為啥會出現次數為0，前文已經解釋了，這種『清華大學』作為整體出現的，前面能獨立在其他語境出現的就統計上，不能獨立的就只能統計到最後一個字上。對應這個例子在統計語料會出現『清』字的情況，『清華學生』，『清華的食堂』。。。很多『清華』的語言，但是沒有『清華大』獨立出現的，必須『清華大學』作為一個整體出現，因此出現了『清』有次數，『清華』有次數，『清華大』無次數，『清華大學』又有次數的現象。這樣意味著，分詞的結果可以出現『清』，『清華』，清華大學』，但是絕不可能出現『清華大』。

這個就是最後的所有可能分詞：我/ 來到/ 北京/ 清華/ 清華大學/ 華大/ 大學。

這個模式在jieba稱為『全模式』。

『全模式』的關鍵代碼：

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

精確模式&no HMM：

這個主要是從後往前計算，哪種分詞可能性最大，

為啥要逆向開始？

從右往左反向計算最大概率(一些教科書上可能是從左往右, 這裡反向是因為漢語句子的重心經常落在後面, 就是落在右邊, 因為通常情況下形容詞太多, 後面的才是主幹, 因此, 從右往左計算,正確率要高於從左往右計算, 這個類似於逆向最大匹配)。

對Python中文分詞模塊結巴分詞演算法過程的理解和分析 - CSDN博客?

blog.csdn.net

還是前面的我來到北京清華大學，先進入全模式，得到如下所有可能的分詞，

從key=8開始，計算log(該詞出現的次數/整個字典所有詞出現的次數)

從key=7開始，我們可以有兩種選擇，一種是7作為一個分詞，另外一種是7,8聯合組成一個詞，我們分別計算他們的log(該詞出現的次數/整個字典所有詞出現的次數)，取個大的，得到

7&8組合會＞7，因此我們的認為7的位置只要一種可能7&8組合

類似6.

下圖是key=5，key=5有3中可能，如下就是這3種可能的概率，可以看出以8作為結尾概率最大，也即我們選則5&6&7&8的組合的作為key=5最後的答案。

經過如此計算，最後的結果，key8 認為8就是最好答案，key7 認為7&8組合是最佳，key6認為認為是6，key5認為是5&6&7&8組合，key=4認為是4，key3認為是3&4，。。。

接下來我們的認為就是將這些答案進行組合就可以了。

# route在這個模式下是沒啥用的，就是個空字典 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])

從正面組合這些答案

從key=0看是0是最好，即『我』

key=1看是1&2即『來到』

key=2跳過了

key=3認為是3&4『北京』

key=5認為是5&6&7&8 『清華大學』

關鍵代碼：

# 這代碼關鍵效果就是前面描述的 def __cut_DAG_NO_HMM(self, sentence): DAG = self.get_DAG(sentence) route = {} self.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 =

精確模式&HMM（也即是Jieba默認的模式）：

上面的模式對『他來到了網易杭研大廈』這句話的分詞結果會是：

他/ 來到/ 了/ 網易/ 杭/ 研/ 大廈

因為「杭研」並沒有在詞典中，那麼這個模式就是需要解決發現新詞的問題.

開始解析『他來到了網易杭研大廈』這句話：

1.先 生成所有可能的分詞，請注意key=6（杭），和key=7（研）【差不多就是方法一的結果】

2.然後生成每個key認為最好的分詞，請注意key=6（杭），和key=7（研）【差不多就是方法二的結果】

3.還是按方法二方式對每個key的結果從前面向後組合，

只不過這個又多了些判斷：遇到單字的地方要小心，可能與下一個單字可以組成一個新詞，

key=0，是單字『他』哎喲，要小心，我先記下，buffer下

key=1，是『來到』，那前面的擔心是多餘了，清除前面要buffer的內容，順便把前面的結果定為最後的分詞結果，到此我們已經確定下來,key=0,key=1的結果

key=2，過

key=3 是單字『了』哎喲，要小心，我先記下，buffer

key=4，是『網易』，那前面的擔心是多餘了，清除前面要buffer的內容，順便把前面的結果定為最後的分詞結果，到此我們已經確定下來,key=0,key=1的結果

key=5 過

key=6，是單字『杭』哎喲，要小心，我先記下，buffer=『杭』

key=7 是單字『研』哎喲，要小心，我先記下，buffer=『杭研』

注意buffer已經又兩個詞了

key=8 大廈，看來要先處理下key=6,和key=7，調另外一個演算法【下文分析】，處理結果是要合併

好了key=6 7 8都處理好了，得到最後分詞。

可以發現：1.只處理連續出現2個以上單字的，所以如果新詞是1個字+1個詞例如『我/ 請/ 你/ 去/ 中央財經/ 所/ 看電視』 這種就沒法了，這種就天然無法進入下個新詞發現的演算法，可能的缺陷。

Viterbi演算法

Jieba主要採用HMM的Viterbi演算法來發現新詞，這個是啥演算法

參見文字版的解釋：誰能通俗的講解下viterbi演算法？ - 李大雷的回答 -