上一篇文章说到结巴分词用了包装器实现了在 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)在这里分享一个文件，该文件保存了 用marshal序列化后默认的 trie，FREQ，total，min_freq。把这个文件解压后放到D盘根目录下，然后运行下面这段代码就可以看到任意一个sentence的route了。
# -*- coding: utf-8 -*-
# python2.7
import marshaldef get_DAG(sentence):N = len(sentence)i,j=0,0p = trieDAG = {}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+=1if j>=N:i+=1j=ip=trieelse:p = triei+=1j=ifor i in xrange(len(sentence)):if i not in DAG:DAG[i] =[i]return DAGdef 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)#获取DAGroute={}calc(sentence,rs,0,route)#根据得分进行初步分词print route附赠一篇讲如何判断有向图是否存在环的文章: http://blog.csdn.net/memray/article/details/8021865 。