jieba分詞流程及部分原始碼解讀(一)

jieba分詞流程及部分原始碼解讀(一)

首先我們來看一下jieba分詞的流程圖:

結巴中文分詞簡介

   1)支援三種分詞模式:

精確模式:將句子最精確的分開,適合文字分析

全模式:句子中所有可以成詞的詞語都掃描出來,速度快,不能解決歧義

搜尋引擎模式:在精確的基礎上,對長詞再次切分,提高召回

   2)支援繁體分詞

   3)支援自定義詞典

   4)基於Trie樹結構實現高效的詞圖掃描,生成句子漢字所有可能成詞情況所構成的有向無環圖(DAG)

   5)  採用了動態規劃查詢最大概率路徑,找出基於詞頻的最大切分組合 6)對於詞庫中不存在的詞,也就是未登入詞,採用了基於漢字成詞能力的HMM模型,使用了Viterbi演算法

接下來我們從原始碼分析一下:

從github上下載原始碼後,開啟 資料夾 jieba,找到__init__.py,結巴分詞最主要的函式 cut 就定義在這個檔案中。

__cut_DAG 函式呼叫了 get_DAG(sentence),這是用來生成每一塊(sentence)的有向無環圖DAG。要生成DAG就必須有語料庫的輔助了,所以在 同樣在 資料夾 jieba 下,可以找到一個檔案:dict.txt。語料庫的有3列,第一列是詞,第二列是詞頻,第三列是詞性。在程式中初始化語料庫的動作在函式  initialize(DICTIONARY) 中,它通過一個包裝器 require_initialized 在 get_DAG 函式被呼叫的時候才執行。程式碼如下:

def require_initialized(fn):
@wraps(fn) #wraps的作用是保留被包裝函式的一些屬性,比如__doc__
def wrapped(*args, **kwargs):
global initialized
if initialized:
return fn(*args, **kwargs)
else:
initialize(DICTIONARY)
return fn(*args, **kwargs)
return wrapped

有向無環圖構建

語料庫Trie樹載入完畢後,接下來我們來介紹如何進行DAG分詞

以“正在學習大資料中的結巴分詞”為例,作為待分詞的輸入文字。

jieba.__init__.py中實現了jieba分詞介面函式cut(self, sentence, cut_all=False, HMM=True)。

jieba分詞介面主入口函式,會首先將輸入文字解碼為Unicode編碼,然後根據入參,選擇不同的切分方式,本文主要以精確模式進行講解,因此cut_all和HMM這兩個入參均為預設值;

 

分詞中get_DAG函式實現如下

# -*- coding: utf-8 -*-
import marshal
def get_DAG(sentence):
N = len(sentence)
i,j=0,0
p = trie
DAG = {}
while i<N:
c = sentence[j]
if c in p:
p = p[c]
if '' in p:
if i not in DAG:
DAG[i]=[]
DAG[i].append(j)
j =1
if j>=N:
i =1
j=i
p=trie
else:
p = trie
i =1
j=i
for i in xrange(len(sentence)):
if i not in DAG:
DAG[i] =[i]
return DAG
#動態規劃,計算最大概率的切分組合
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([ (概率對數,詞語末字位置) for x in DAG[idx] ])
# 以idx:(概率對數最大值,詞語末字位置)鍵值對形式儲存在route中
# route[x 1][0] 表示 詞路徑[x 1,N-1]的最大概率對數,
# [x 1][0]即表示取句子x 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])
if __name__=='__main__':
sentence=u'正在學習大資料中的結巴分詞'
trie,FREQ,total,min_freq = marshal.load(open(u'D:\jieba.cache','rb'))#使用快取載入重要變數
rs=get_DAG(sentence)#獲取DAG
route={}
calc(sentence,rs,0,route)#根據得分進行初步分詞
print route

基於詞頻最大切分組合(從上面get_DAG中部分程式碼詳解)

我們已經有了詞庫(dict.txt)的字首字典和待分詞句子sentence的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([ (概率對數,詞語末字位置) for x in DAG[idx] ])
# 以idx:(概率對數最大值,詞語末字位置)鍵值對形式儲存在route中
# route[x 1][0] 表示 詞路徑[x 1,N-1]的最大概率對數,
# [x 1][0]即表示取句子x 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])

從程式碼中可以看出calc是一個自底向上的動態規劃(重疊子問題、最優子結構),它從sentence的最後一個字(N-1)開始倒序遍歷sentence的字(idx)的方式(為什麼倒敘遍歷,不懂的可以留言或是找我小豬),計運算元句sentence[isdx~N-1]概率對數得分(這裡利用DAG及歷史計算結果route實現)。然後將概率對數得分最高的情況以(概率對數,詞語最後一個字的位置)這樣的tuple儲存在route中。 

那麼登陸詞部分解釋完畢,下來就是未登陸詞,利用Viterbi演算法來解決未登入詞的處理方法,後續更新