Viterbi 介绍

维特比算法（Viterbi algorithm）是一种动态规划算法。它用于寻找最有可能产生观测事件序列的维特比路径——隐含状态序列，特别是在马尔可夫信息源上下文和隐马尔可夫模型中。

维特比算法由安德鲁·维特比（Andrew Viterbi）于1967年提出，用于在数字通信链路中解卷积以消除噪音。

维特比（1935年3月9日~），美国电机工程师和企业家，高通公司的共同创建者之一。

此算法被广泛应用于CDMA和GSM数字蜂窝网络、拨号调制解调器、卫星、深空通信和802.11无线网络中解卷积码。

现今也被常常用于语音识别、关键字识别、计算语言学和生物信息学中。例如在语音（语音识别）中，声音信号做为观察到的事件序列，而文本字符串，被看作是隐含的产生声音信号的原因，因此可对声音信号应用维特比算法寻找最有可能的文本字符串。

算法简介

Viterbi算法实际上是最优路径算法的一种。下图是Viterbi算法的动画示意。

简单介绍下：

从开始状态之后每走一步，就记录下到达该状态的所有路径的概率最大值，然后以此最大值为基准继续向后推进。

显然，如果这个最大值都不能使该状态成为最大似然状态路径上的结点的话，那些小于它的概率值（以及对应的路径）就更没有可能了。

代码展示数据集准备开始编码

tag2id, id2tag = {}, {}word2id, id2word = {}, {}with open('./mytraindata.txt') as f:  lines = f.readlines()  for line in lines:      param = line.strip().split(r'/')      if tag2id.get(param[1]) is None:          tag2id[param[1]] = len(tag2id)          id2tag[len(tag2id)-1] = param[1]      if word2id.get(param[0]) is None:          word2id[param[0]] = len(word2id)          id2word[len(word2id)-1] = param[0]

import numpy as npN = len(tag2id)M = len(word2id)pi = np.zeros(N)     # pi[i] 词性i作为句子开头的概率，可以看作是语言模型的第一个概率A = np.zeros((N, M)) # A[i][j] 词性i下出现单词j的概率B = np.zeros((N, N)) # B[i][j] 一句话中词性i的下一个是词性j的概率

# 求参数pi，A，Bpre_word = '.'for line in open('./mytraindata.txt'):  param = line.strip().split(r'/')  if pre_word == '.':      pi[tag2id[param[1]]] += 1      A[tag2id[param[1]]][word2id[param[0]]] += 1  else:      A[tag2id[param[1]]][word2id[param[0]]] += 1      B[tag2id[pre_word]][tag2id[param[1]]] += 1  pre_word = param[1].rstrip()

# 归一化pi = pi/sum(pi)for i in range(N):  A[i] = A[i]/sum(A[i])  B[i] = B[i]/sum(A[i])    

def log(v):  if v == 0:      return np.log(v+0.000001)  return np.log(v)

# Viterbi 算法def viterbi(sentence, pi, A, B):  s = [word2id[w] for w in sentence]  # 求出集合s的长度  l = len(s)  dp = np.zeros((N, l))  path = np.zeros((N, l))  for i in range(N):      dp[i][0] = log(pi[i]) + log(A[i][s[0]])     for i in range(1, l):      for j in range(N):          dp[j][i] = -9999          for k in range(N):              if dp[k][i-1] + log(B[k][j]) + log(A[j][s[i]]) > dp[j][i]:                  dp[j][i] = dp[k][i-1] + log(B[k][j]) + log(A[j][s[i]])                  path[j][i] = k                 best_seq = []  best_seq.append(np.argmax(dp[:,l-1]))  for i in range(l-2, -1, -1):      best_seq.append(int(path[best_seq[-1]][i+1]))  best_seq = best_seq[::-1]      best_seq = [id2tag[t] for t in best_seq]         print(best_seq)

x = "CM5 63L A160S 2P"x = [word for word in x.split(" ")]viterbi(x, pi, A, B)

['系列名', '壳架电流', '壳架电流', '极数']