NLP之jieba分詞原理簡析

一、jieba介紹

jieba庫是一個簡單實用的中文自然語言處理分詞庫。

jieba分詞屬于機率語言模型分詞。機率語言模型分詞的任務是：在全切分所得的所有結果中求某個切分方案S，使得P(S)最大。

jieba支援三種分詞模式：

• 全模式，把句子中所有的可以成詞的詞語都掃描出來, 速度非常快，但是不能解決歧義；
• 精确模式，試圖将句子最精确地切開，适合文本分析；
• 搜尋引擎模式，在精确模式的基礎上，對長詞再次切分，提高召回率，适合用于搜尋引擎分詞。

接下來我們針對此進行切分算法原理分析。

二、jieba分詞原理

1.基于字首詞典實作高效的詞圖掃描，生成句子中漢字所有可能成詞情況所構成的有向無環圖 (DAG)

 1. 根據dict.txt生成trie樹，字典在生成trie樹的同時, 把每個詞的出現次數轉換為頻率（jieba自帶一個dict.txt的詞典, 裡面有2萬多條詞, 包含了詞條出現的次數和詞性(作者基于人民日報語料等資源訓練得出來)。trie樹結構的詞圖掃描, 說的就是把這2萬多條詞語, 放到一個trie樹中, trie樹是有名的字首樹, 也就是說一個詞語的前面幾個字一樣, 就表示他們具有相同的字首, 就可以使用trie樹來存儲, 具有查找速度快的優勢）。

2.對待分詞句子, 根據dict.txt生成的trie樹, 生成DAG, 通俗的講, 就是将句子根據給定的詞典進行查詞典操作, 生成所有可能的句子切分。jieba在DAG中記錄的是句子中某個詞的開始位置, 從0到n-1(n為句子的長度), 每個開始位置作為字典的鍵, value是個list, 其中儲存了可能的詞語的結束位置(通過查字典得到詞, 開始位置+詞語的長度得到結束位置）

2.動态規劃查找最大機率路徑, 找出基于詞頻的最大切分組合

1.查找待分詞句子中已經切分好的詞語（全模式下的分詞list）, 得出查找該詞語出現的頻率(次數/總數), 如果沒有該詞(基于詞典一般都是有的), 就把詞典中出現頻率最小的那個詞語的頻率作為該詞的頻率。

2.根據動态規劃查找最大機率路徑的方法, 對句子從右往左反向計算最大機率(這裡反向是因為漢語句子的重心經常落在後面（右邊）, 因為通常情況下形容詞太多, 後面的才是主幹。是以, 從右往左計算, 正确率要高于從左往右計算, 這裡類似于逆向最大比對), P(NodeN)=1.0, P(NodeN-1)=P(NodeN)*Max(P(倒數第一個詞))…依次類推, 最後得到最大機率路徑, 得到最大機率的切分組合。

3.對于未登入詞，采用了基于漢字成詞能力的 HMM 模型，使用了 Viterbi 算法

1.利用HMM模型将中文詞彙按照BEMS四個狀态來标記, B是開始begin位置, E是end結束位置, M是middle中間位置, S是singgle單獨成詞的位置。jieba采用(B,E,M,S)這四種狀态來标記中文詞語, 比如北京可以标注為 BE, 即 北/B 京/E, 表示北是開始位置, 京是結束位置, 中華民族可以标注為BMME, 就是開始, 中間, 中間, 結束.

2.作者利用大量語料進行訓練, 得到了三個機率表。分别是1)位置轉換機率，即B（開頭）,M（中間),E(結尾),S(獨立成詞）四種狀态的轉移機率，P(E|B) = 0.851, P(M|B) = 0.149，說明當我們處于一個詞的開頭時，下一個字是結尾的機率要遠高于下一個字是中間字的機率，符合我們的直覺，因為二個字的詞比多個字的詞更常見。2）位置到單字的發射機率，比如P(“和”|M)表示一個詞的中間出現”和”這個字的機率；3) 詞語以某種狀态開頭的機率，其實隻有兩種，要麼是B，要麼是S。這個就是起始向量, 就是HMM系統的最初模型狀态。實際上, BEMS之間的轉換有點類似于2元模型, 就是2個詞之間的轉移。二進制模型考慮一個單詞後出現另外一個單詞的機率，是N元模型中的一種。

給定一個待分詞的句子, 就是觀察序列, 對HMM(BEMS)四種狀态的模型來說, 就是為了找到一個最佳的BEMS序列, 這個就需要使用viterbi算法來得到這個最佳的隐藏狀态序列。通過訓練得到的機率表和viterbi算法, 就可以得到一個機率最大的BEMS序列, 按照B打頭, E結尾的方式, 對待分詞的句子重新組合, 就得到了分詞結果. 比如 對待分詞的句子 ‘全世界都在學中國話’ 得到一個BEMS序列 [S,B,E,S,S,S,B,E,S], 通過把連續的BE湊合到一起得到一個詞, 單獨的S放單, 就得到一個分詞結果了。

三、jieba分詞過程

1. 加載字典, 生成trie樹。

2. 給定待分詞的句子, 使用正則擷取連續的 中文字元和英文字元, 切分成 短語清單, 對每個短語使用DAG(查字典)和動态規劃, 得到最大機率路徑, 對DAG中那些沒有在字典中查到的字, 組合成一個新的片段短語, 使用HMM模型進行分詞, 也就是作者說的識别未登入詞。

3. 使用python的yield 文法生成一個詞語生成器, 逐詞語傳回。

四、jieba分詞的不足

1.dict.txt字典占用的記憶體為140多M, 占用記憶體過多。jieba中詞典的使用是為了彌補HMM在識别多字詞方面能力欠佳的問題, 是以詞典中儲存的是3 ,4 個字的詞語。專業化的詞典生成不友善，怎麼訓練自己的專用機率表沒有提供工具。

2.HMM識别新詞在時效性上是不足的, 并且隻能識别2個字的詞, 對于3個字的新詞, 相對能力有限。

3.詞性标注效果不夠好，句法分析, 語義分析也都是沒有的。

4.命名實體識别效果不夠好。

參考文章

jieba分詞的原理

對Python中文分詞子產品結巴分詞算法過程的了解和分析

jieba官方文檔