jieba 分词源代码研读(2)

上一篇文章说到结巴分词用了包装器实现了在 get_DAG 函数执行器生成了 trie 树。在这篇文章中我们要研究一下jieba分词中的 DAG(有向无环图,全称:directed acyclic graphs )。

在 cut 函数使用正则表达式把文本切分成一个一个短语和句子后,再用 __cut_DAG 函数对其进行分词。这些句子和短语就是 所谓的 sentence。每一个sentence都会生成一个DAG。作者用来表达DAG的数据结构是dict + list 。举一个例子,比如 sentence 是 "国庆节我在研究结巴分词",对应生成的DAG是这样的:

{0: [0, 1, 2], 1: [1], 2: [2], 3: [3], 4: [4], 5: [5, 6], 6: [6], 7: [7, 8], 8: [8], 9: [9, 10], 10: [10]}

其中的数字表示每个汉字在sentence中的位置,所以0:[0,1,2] 表示 在trie 树中,"国"开头的词语中对应于该 sentence 有三种匹配情况:国,国庆,国庆节;分别对应3条有向图的路径:0->1->2->3,0->2->3,0->3。结巴分词使用的是正向匹配法,这一点从字典中也可以看出。

此外补充一点在上一篇中提到的 initialize 函数除了生成了trie树外还返回了两个重要的值。在代码中分别叫 total 和 FREQ。total 是dict.txt中所有词语的词频之和。而FREQ是一个dict类型的变量,它用来保存dict.txt中每个词语的频度打分,打分的公式是 log(float(v)/total),其中v就是被打分词语的频度值。

那么剩下的目标就很明确了:我们已经有了sentence的DAG和sentence中每个词语的频度得分,要在所有的路径中找出一条路径使频度得分的总和最大,这同时也是动态规划的一个典型应用。

作者实现的代码如下:

def calc(sentence,DAG,idx,route):
    N = len(sentence)
    route[N] = (0.0,'')
    for idx in xrange(N-1,-1,-1):
        candidates = [ ( FREQ.get(sentence[idx:x+1],min_freq) + route[x+1][0],x ) for x in DAG[idx] ]
        route[idx] = max(candidates)
这是一个自底向上的动态规划,从sentence的最后一个字开始倒序遍历每个分词方式的得分(必须是倒序,正序不行,大家可以思考下为什么)。然后将得分最高的情况以(频度得分值,词语最后一个字的位置)这样的tuple保存在route中。(注:从代码上看idx是一个无用的参数~)

在这里分享一个文件,该文件保存了 用marshal序列化后默认的 trie,FREQ,total,min_freq。把这个文件解压后放到D盘根目录下,然后运行下面这段代码就可以看到任意一个sentence的route了。

# -*- coding: utf-8 -*-
# python2.7
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(sentence,DAG,idx,route):
    N = len(sentence)
    route[N] = (0.0,'')
    for idx in xrange(N-1,-1,-1):
        candidates = [ ( FREQ.get(sentence[idx:x+1],0.0) + route[x+1][0],x ) for x in DAG[idx] ]
        route[idx] = max(candidates)

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

附赠一篇讲如何判断有向图是否存在环的文章: http://blog.csdn.net/memray/article/details/8021865 。

原文地址:https://www.cnblogs.com/rav009/p/5131118.html