jieba库：Tokenizer()类详解：（二）DAG词图类

2021SC@SDUSC

get_DAG(self,sentence)方法

    def get_DAG(self, sentence):self.check_initialized()DAG = {}    #DAG空字典，用来构建DAG有向无环图N = len(sentence) #赋值N词的长度for k in xrange(N): #创建N词长度的列表，进行遍历tmplist = []  #从字开始能在FREQ中的匹配到的词末尾位置所在的listi = kfrag = sentence[k] #取传入词中的值，例如k=0,frag=我while i < N and frag in self.FREQ: # 当传入的词，在FREQ中时，就给tmplist赋值，构建字开始可能去往的所有的路径列表if self.FREQ[frag]: #每个词，在FREQ中查找，查到，则将下标传入templist中tmplist.append(i)   #添加词语所在位置i += 1      #查找我，后继续查找“我们”是否也在语料库中，直到查不到推出循环frag = sentence[k:i + 1]  #截取传入值得词语，i=1,时截取 我，i=2时截取我们if not tmplist:  #当传入值，在语料库中查询不到时，tmplist.append(k)DAG[k] = tmplist  #赋值DAG 词典return DAG

calc()方法

    #动态规划查找最大概率路径def calc(self, sentence, DAG, route):N = len(sentence)route[N] = (0, 0) #route[N]:最大路径的值,(0,0):当前这个词的末尾坐标# total 为dict.txt词表中，共有多少个词，共60101967 个词语# 对概率值取对数之后的结果(可以让概率相乘的计算变成对数相加,防止相乘造成下溢)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])