维特比算法:从众多路径中，挑出最优的那条，他和隐马尔可夫没有强关联
语料库 => 标注 => 训练得到三数组 => 归一化算概率
预测 => 标注 => 维特比
中文分词任务
语料库 => 训练集
初始、转移、发射矩阵 => 训练过程
维特比算法，得到真正结果
训练的时候，是用不到维特比算法的，只有分词时才会使用
示例不考虑训练集中不存在的数据
算法思想
维特比（Viterbi）算法属于一种动态规划算法，目标在于寻找最优路径。
预测 “今天的天气不错 ” => BESBEBE
动态规划
用动态规划来解决隐马尔可夫的预测问题，即用动态规划求概率最大路径（最优路径）。这时一条路径对应着一个状态序列
选中一条最优的路径，把节点标注出来，根据标注的节点状态序列就可以得到分词的结果了
预测 “今天 的 天气 不错 ” => BE S BE BE => 图中绿色线
- 开始
0.667，今 第一个字没有转移矩阵，到发射矩阵 B 里面找 今0.142 - 天 转移矩阵 BE =>
0.857, 到发身矩阵 E 里面找天0.142 - 的 转移矩阵，E往S转移 ES =>
0.715, 到发身矩阵 S 里面找天0.142 - ...
7个字，就有 4^7 次计算，计算量相当大，所以预测后会引入 维特比算法
维特比算法
从众多路径中，迅速选出最优路径
核心思想：边计算边删除，舍弃那些概率比较小的路径。
初始矩阵，人眼知道，有2个是0，ME不可能出现，但计算机不知道，也不确定某条路径就是最做优的，武断的选择B，有可能后面的概率就是0了
所以初始矩阵的4条路径，都是候选路径，
如果从B出发的话，有4条路径经过B，并且有一条最优，假设3是最优的，保存最优路径3，其它的全部删除
同理，到达M点。也是有4条路径，假设2是最优的，就把其它几条删除
从天到的
到 B 有四条，到 M 也有4条
每到达一个字都只会有4条路径，在4条路径中，选择最优的，则可得到状态序列分词结束
每个状态下连线很多，结果只有4条
代码
def viterbi_t(text, hmm): states = hmm.index_to_states emit_p = hmm.emit_matrix trans_p = hmm.transfer_matrix start_p = hmm.init_matrix V = [{}] path = {} for y in states: V[0][y] = start_p[hmm.states_to_index[y]] * emit_p[y].get(text[0], 0) path[y] = [y] for t in range(1, len(text)): V.append({}) newpath = {} # 检验训练的发射概率矩阵中是否有该字 neverSeen = text[t] not in emit_p['S'].keys() and \ text[t] not in emit_p['M'].keys() and \ text[t] not in emit_p['E'].keys() and \ text[t] not in emit_p['B'].keys() for y in states: emitP = emit_p[y].get(text[t], 0) if not neverSeen else 1.0 # 设置未知字单独成词 temp = [] for y0 in states: if V[t - 1][y0] > 0: temp.append((V[t - 1][y0] * trans_p[hmm.states_to_index[y0], hmm.states_to_index[y]] * emitP, y0)) (prob, state) = max(temp) # (prob, state) = max([(V[t - 1][y0] * trans_p[hmm.states_to_index[y0],hmm.states_to_index[y]] * emitP, y0) for y0 in states if V[t - 1][y0] > 0]) V[t][y] = prob newpath[y] = path[state] + [y] path = newpath (prob, state) = max([(V[len(text) - 1][y], y) for y in states]) # 求最大概念的路径 result = "" # 拼接结果 for t, s in zip(text, path[state]): result += t if s == "S" or s == "E": # 如果是 S 或者 E 就在后面添加空格 result += " " return result
