2021SC@SDUSC
__cut_DAG_NO_HMM()
re_eng = re.compile('[a-zA-Z0-9]', re.U)
def __cut_DAG_NO_HMM(self, sentence):# 构建有向无环图DAG = self.get_DAG(sentence)route = {}# 计算最大概率路径self.calc(sentence, DAG, route)x = 0N = len(sentence)buf = ''# 使用最大概率路径进行分词while x < N:y = route[x][1] + 1# 选择最大概率路劲的词汇l_word = sentence[x:y]# 如果匹配到字母或数字或词汇长度为1,则添加到buf中if re_eng.match(l_word) and len(l_word) == 1:buf += l_wordx = y# 否则向迭代器返回非空的buf/将词汇传给迭代器else:if buf:yield bufbuf = ''yield l_wordx = y# 若最后buf非空返回给迭代器,buf置空if buf:yield bufbuf = ''例子：
_cut_DAG()
源码：
def __cut_DAG(sentence):# 构建有向无环图DAG = jieba.get_DAG(sentence)route = {}# 计算最大概率路径jieba.calc(sentence, DAG, route)x = 0N = len(sentence)buf = ''# 使用最大概率路径进行分词while x < N:y = route[x][1] + 1l_word = sentence[x:y]# l_word长度为一，将词汇添加到bufif y - x == 1:buf += l_wordelse:if buf:# buf长度为1，向迭代器返回buf，buf置空if len(buf) == 1:yield bufbuf = ''else:# buf长度大于1# 如果没在词频字典中找到，使用finalseg.cut切分，结果逐个返回给迭代器if not jieba.dt.FREQ.get(buf):recognized = jieba.finalseg.cut(buf)for t in recognized:yield telse:# buf在词频字典中，则逐个返回给迭代器for elem in buf:yield elembuf = ''#此时buf为空，将l_word返回给迭代器yield l_wordx = y# 处理完成后避免buf中还有词汇，再次操作一次。if buf:if len(buf) == 1:yield bufelif not jieba.dt.FREQ.get(buf):recognized = jieba.finalseg.cut(buf)for t in recognized:yield telse:for elem in buf:yield elem其中recognized变量使用 finalseg.cut()进行分词的结果，看到finalseg。
finalseg是基于HMM模型的中文分词，使用了viterbi算法。
def cut(sentence):sentence = strdecode(sentence)# 切割句子blocks = re_han.split(sentence)for blk in blocks:# 处理中文if re_han.match(blk):for word in __cut(blk):if word not in Force_Split_Words:yield wordelse:for c in word:yield c#处理英文、数字else:tmp = re_skip.split(blk)for x in tmp:if x:yield x可以看到finalseg.cut()对中文进行了切分、分词（使用__cut()方法）
def __cut(sentence):global emit_Pprob, pos_list = viterbi(sentence, 'BMES', start_P, trans_P, emit_P)begin, nexti = 0, 0# print pos_list, sentencefor i, char in enumerate(sentence):pos = pos_list[i]if pos == 'B':begin = ielif pos == 'E':yield sentence[begin:i + 1]nexti = i + 1elif pos == 'S':yield charnexti = i + 1if nexti < len(sentence):yield sentence[nexti:]__cut()方法主要是对viterbi算法的结果进行一些处理，对sentence的每个字符进行了处理后返回给迭代器。
viterbi：
def viterbi(obs, states, start_p, trans_p, emit_p):V = [{}] # tabularpath = {}# 时刻t = 0，初始状态for y in states: # initV[0][y] = start_p[y] + emit_p[y].get(obs[0], MIN_FLOAT)path[y] = [y]# 时刻t = 1,...,len(obs) - 1for t in xrange(1, len(obs)):V.append({})newpath = {}# 当前时刻所处的各种可能的状态for y in states:# 获取发射概率em_p = emit_p[y].get(obs[t], MIN_FLOAT)# 分别获取上一时刻的状态的概率，该状态到本时刻的状态的转移概率，本时刻的状态的发射概率# 其中，PrevStatus[y]是当前时刻的状态所对应上一时刻可能的状态(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# 将上一时刻最优的状态 + 这一时刻的状态newpath[y] = path[state] + [y]path = newpath# 最后一个时刻(prob, state) = max((V[len(obs) - 1][y], y) for y in 'ES')# 返回最大概率对数和最优路径return (prob, path[state])维特比算法
维特比算法的基础可以概括成下面三点：
1.如果概率最大的路径p(或者说最短路径)经过某个点，比如图中的X22，那么这条路径上的起始点S到X22的这段子路径Q，一定是S到X22之间的最短路径。否则，用S到X22的最短路径R替代Q，便构成一条比P更短的路径，这显然是矛盾的。证明了满足最优性原理。
2.从S到E的路径必定经过第i个时刻的某个状态，假定第i个时刻有k个状态，那么如果记录了从S到第i个状态的所有k个节点的最短路径，最终的最短路径必经过其中一条，这样，在任意时刻，只要考虑非常有限的最短路即可。
3. 结合以上两点，假定当我们从状态i进入状态i+1时，从S到状态i上各个节的最短路径已经找到，并且记录在这些节点上，那么在计算从起点S到第i+1状态的某个节点Xi+1的最短路径时，只要考虑从S到前一个状态i所有的k个节点的最短路径，以及从这个节点到Xi+1，j的距离即可。