参考文章：blog.csdn.net/yuanlisky

在看完前面的文章：

梦里寻梦：（八）通俗易懂理解——jieba中的HMM中文分词原理

再来看这篇文章会恍然大悟的感觉，不然原来还是懵懵的。

jieba分词

  • 基于前缀词典实现高效的词图扫描，生成句子中汉字所有可能成词情况所构成的有向无环图 (DAG)
  • 采用了动态规划查找最大概率路径, 找出基于词频的最大切分组合
  • 对于未登录词，采用了基于汉字成词能力的 HMM 模型，使用了 Viterbi 算法

前缀词典

def gen_pfdict(self, f):# f 为词典文件
    lfreq = {} # 空字典
    ltotal = 0
    f_name = resolve_filename(f) # 返回f的文件名
    for lineno, line in enumerate(f, 1):# lineno:序号，line:f的内容,逐行读取f的内容
        try:
            line = line.strip().decode('utf-8')
            word, freq = line.split(' ')[:2]
            freq = int(freq)
            lfreq[word] = freq
            ltotal += freq # 词频总数
        # 获取前缀，若在词典中则跳过，不在则加入词典，且置频数为0
            for ch in xrange(len(word)): 
                wfrag = word[:ch + 1]
                if wfrag not in lfreq:
                    lfreq[wfrag] = 0
        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 += 1
            frag = sentence[k:i + 1]
        if not tmplist:
            tmplist.append(k)
        DAG[k] = tmplist # 记录了从k位置到句尾的所有能成词的词语的尾字在句中的位置
    return DAG

最大概率路径

def calc(self, sentence, DAG, route):# DAG 有向无环图,求解最大概率路径,动态规划
    N = len(sentence)
    route[N] = (0, 0) # route为字典dict
    logtotal = log(self.total)
    for idx in xrange(N - 1, -1, -1): # 从后往前遍历每个分词
    # 取log防止向下溢出,取过log后除法变为减法
        route[idx] = max((log(self.FREQ.get(sentence[idx:x + 1]) or 1) -
                          logtotal + route[x + 1][0], 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[0][y] = start_p[y] + emit_p[y].get(obs[0], 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(1, 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 - 1][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) - 1][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状态下的最大概率路径，避免了进行一次最优路径回溯。