jieba分詞算法源碼解析

jieba分詞readme

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

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

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

字首詞典

def gen_pfdict(self, f):# f 為詞典檔案
    lfreq = {} # 空字典
    ltotal = 
    f_name = resolve_filename(f) # 傳回f的檔案名
    for lineno, line in enumerate(f, ):# lineno:序号，line:f的内容,逐行讀取f的内容
        try:
            line = line.strip().decode('utf-8')
            word, freq = line.split(' ')[:]
            freq = int(freq)
            lfreq[word] = freq
            ltotal += freq # 詞頻總數
        # 擷取字首，若在詞典中則跳過，不在則加入詞典，且置頻數為0
            for ch in xrange(len(word)): 
                wfrag = word[:ch + ]
                if wfrag not in lfreq:
                    lfreq[wfrag] = 
        except ValueError:
            raise ValueError(
                'invalid dictionary entry in %s at Line %s: %s' % (f_name, lineno, line))
    f.close()
    return lfreq, ltotal # 傳回字首詞典，詞彙總數

　　傳回了一個字典lfreq，形式為{word:freq}，其中不僅有原詞典中的詞和頻數，還有原詞典中詞語的字首，其頻數為0，這就是字首詞典。

生成有向無環圖(DAG)

def get_DAG(self, sentence):
    self.check_initialized() # 初始化
    DAG = {} # 生成空字典
    N = len(sentence) # 句子長度
    for k in xrange(N):
        tmplist = []
        i = k
        frag = sentence[k] # 句子中第k個字
        while i < N and frag in self.FREQ: # self.FREQ即字首詞典，frag在字首詞典中
            if self.FREQ[frag]:#  frag的頻數不為0，即frag出現在原詞典中
                tmplist.append(i) # 将frag末尾位置加入tmplist
            i += 
            frag = sentence[k:i + ]
        if not tmplist:
            tmplist.append(k)
        DAG[k] = tmplist # 記錄了從k位置到句尾的所有能成詞的詞語的尾字在句中的位置
    return DAG

最大機率路徑

def calc(self, sentence, DAG, route):# DAG 有向無環圖,求解最大機率路徑,動态規劃
    N = len(sentence)
    route[N] = (, ) # route為字典dict
    logtotal = log(self.total)
    for idx in xrange(N - , -, -): # 從後往前周遊每個分詞
    # 取log防止向下溢出,取過log後除法變為減法
        route[idx] = max((log(self.FREQ.get(sentence[idx:x + ]) or ) -
                          logtotal + route[x + ][], x) for x in DAG[idx])

　　for循環中，idx為句末往句首倒推。

　　route為字典，key為idx，value為含有兩個元素的元組，元組的第一個元素為：以idx為開頭，第二個元素x位置為結尾組成的詞語，在詞典中成詞的機率(取max後結果為x周遊，idx到x，以及x到句尾的分詞方式最大機率，也就是idx到句尾的最大機率分詞方式)。元組的第二個元素x為DAG[idx]的value周遊。當idx=0時，可得到句首到句尾的最大分詞方式。

　　這裡采用從後往前的計算方式，其原因有兩種說法：

1. 有向無環圖是從前指向後，對于一個節點，DAG中存儲了此節點指向後面哪些節點，但沒有存儲前面有哪些節點指向此節點。舉個例子：’ABCD’，從後往前計算，我們可以在’C’節點先知道P(‘CD’)，到’A’節點時，就可以比較P(‘ABCD’)與P(‘AB’)*P(‘CD’)的大小了，但如果是從前往後計算就不行，在A節點我們知道P(‘AB’)和P(‘ABCD’)，但是不知道P(‘CD’)，會加大程式的複雜性。

2. 漢語句子的重心經常落在後面，就是落在右邊，因為通常情況下形容詞太多，後面的才是主幹，是以，從右往左計算，正确率要高于從左往右計算，這個類似于逆向最大比對。這條原因中關于正确率要高于從左往右計算未做實際驗證，也沒有從理論上去推論。

Viterbi算法

函數在

jieba\finalseg\__init\__.py

中

def viterbi(obs, states, start_p, trans_p, emit_p):
    '''
    :param obs: 觀測序列 obs = sentence
    :param states: 隐藏狀态集合 states = 'BMES'
    :param start_p: 初始狀态機率向量
    :param trans_p: 狀态轉移矩陣
    :param emit_p: 觀測機率矩陣(發射矩陣)
    :return:
    '''
    V = [{}]  # tabular,字典清單
    path = {}
    for y in states:  # init 初始化，初始機率*觀測機率 states = 'BMES'
        # V[0][y]為V清單第一個元素:一個key為y的字典，y為'BMES'，V清單隻有一個元素，有4個Key的字典
        V[][y] = start_p[y] + emit_p[y].get(obs[], MIN_FLOAT) # 初始機率*觀測機率，已經求過np.log了，乘法變為加法
        path[y] = [y] # path為4個key的字典，path['B'] = ['B'], path['E'] = ['E'], path['M'] = ['M'], path['S'] = ['S']
    for t in xrange(, len(obs)):# 遞推步
        V.append({}) # 給V添加一個字典，句子幾個字，V多長
        newpath = {}
        for y in states: # states = 'BMES'
            em_p = emit_p[y].get(obs[t], MIN_FLOAT) # y狀态下，觀測到第t個字的機率，b(o)，即目前字觀測機率
            # 乘法轉加法，V[t-1][y0]前一個字，狀态為y0的機率，trans_p[y0].get(y)：y0狀态轉移到y狀态的機率
            # 求出了由y0的四個狀态轉到目前y狀态的最大機率，及當時y0的狀态，動态規劃
            (prob, state) = max([(V[t - ][y0] + trans_p[y0].get(y, MIN_FLOAT) + em_p, y0) for y0 in PrevStatus[y]])
            V[t][y] = prob # 記錄下y0的四個狀态轉到每個y狀态的最大機率
            newpath[y] = path[state] + [y] # 記錄下前面最大機率路徑和y的狀态，并存到字典newpath[y]中，newpath[y]有4個key
        path = newpath # 更新path，path還是為4個key的字典，value為目前key狀态的最大機率路徑

    # 終止步，最後一個元素，狀态為E或S，取機率大的那個
    (prob, state) = max((V[len(obs) - ][y], y) for y in 'ES')

    return (prob, path[state])

　　Viterbi算法分為4步：

1. 初始化：第一個

for

循環；

2. 遞推：第二個

for

循環；

3. 終止：

(prob, state) = max((V[len(obs) - 1][y], y) for y in 'ES')

，句子最後隻可能是狀态’E’或’S’；

4. 回溯：每個遞推步記錄了到目前位置4種狀态的最大機率路徑。

　　其中，作者在遞推步中加上了

ewpath[y] = path[state] + [y]

，記錄下了y狀态下的最大機率路徑，避免了進行一次最優路徑回溯。

jieba分詞算法源碼解析