閒來無事，在部落格園的論壇裡隨意遊蕩，看到一個開源的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/iY
Rfe2
寫的非常通俗易懂。
__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，所以切詞結果如下：小明/碩士/畢業於/中國/科學院/計算/所。
finalseg中有BMES各個狀態間的轉移機率以及隱藏狀態對應於各個中文的發射機率，再根據維特比演算法，計算分詞就相當的容易了。由於對隱馬爾科夫理解有限，也就不瞎寫了，有興趣的可以看一下http：//blog。csdn。net/likelet/article/details/7056068，寫的非常的贊。
——————————————————-
作者：腩啵兔子
出處：腩啵兔子的部落格專欄
最近很多人私信問我問題，平常知乎評論看到不多，如果沒有及時回覆，大家也可以加小編微信：tszhihu，進知乎大資料分析挖掘交流群，可以跟各位老師互相交流。謝謝。
