维特比算法是一种动态规划算法，用于识别能够产生给定观测事件序列的最可能的隐藏状态序列。由此得到的序列通常被称为维特比路径。它最常应用于隐马尔可夫模型（HMM），其中底层状态不可直接观测，但会影响观测结果。例如，医生连续几天观察患者的症状，可以使用该算法推断出导致这些症状的最可能的潜在健康状况序列。
该算法在解码卷积码方面得到了普遍应用，这些卷积码用于CDMA和GSM数字蜂窝网络、拨号调制解调器、卫星和深空通信，以及802.11无线局域网。它也被广泛用于语音识别、语音合成、说话人日志、关键词检测、计算语言学和生物信息学。在语音转文本系统中，声学信号作为观测序列，而文本字符串是隐藏原因；维特比算法在给定声学信号的情况下找到最可能的文本。
历史
维特比算法以安德鲁·维特比的名字命名，他于1967年提出该算法，作为噪声数字通信链路上卷积码的解码算法。它具有多次独立发明的历史，至少有七次独立发现，包括维特比、尼德勒曼和翁施，以及瓦格纳和费舍尔的贡献。它早在1987年就被引入自然语言处理领域，作为词性标注的方法。
“维特比路径”和“维特比算法”已成为涉及概率的最大化问题中动态规划方法的标准术语。在统计句法分析中，动态规划算法可以发现字符串的单个最可能的上下文无关推导（句法分析），通常称为“维特比句法分析”。另一个应用是目标跟踪，其中算法计算对观测序列赋予最大似然的轨迹。
算法概述
给定一个隐马尔可夫模型，其中包含一组隐藏状态S、一组可能的发射（观测）M，以及一个长度为T的观测序列o0, o1, ..., oT-1，维特比算法找到能够产生这些观测的最可能的隐藏状态序列。在每个时间步t，算法解决仅考虑截至ot的观测的子问题。
构建两个大小为T × |S|的矩阵。矩阵Pt,s包含在观测t时结束于状态s的最大概率，该概率来自所有可能的前导状态序列。矩阵Qt,s跟踪在此最大概率状态序列中s之前使用的先前状态。
设πs和ar,s分别为初始概率和转移概率，bs,o为在状态s观测到o的概率。那么P的值由递推关系给出。在时间t = 0时，Pt,s等于πs乘以bs,o0。对于t > 0，Pt,s等于所有先前状态r上的最大值（Pt-1,r × ar,s × bs,ot）。填充矩阵后，算法从最终时间步具有最高概率的状态开始，使用Q矩阵回溯以重建最可能的状态序列。
在通信中的应用
该算法是现代数字通信的基石。它解码卷积码，这些纠错码用于许多无线和有线系统。在CDMA和GSM蜂窝网络中，维特比算法有助于在噪声和干扰下恢复传输数据。拨号调制解调器、卫星链路和深空通信系统也依赖它。802.11无线局域网标准包含维特比解码，以确保可靠的数据传输。
该算法的效率来自其动态规划特性：它通过存储中间概率并使用最优性原理，避免了对所有可能状态序列的穷举枚举。这使得即使在资源受限的设备上，也能实时解码长序列。
在语音和语言中的应用
在语音识别中，维特比算法将声学特征与音素或单词模型对齐。声学信号是观测序列，文本字符串是隐藏原因。该算法在给定声学信号的情况下找到最可能的文本字符串，从而实现准确的转录。它也用于语音合成，以选择最自然的语音单元序列，并用于说话人日志，以确定谁在何时说话。
在计算语言学中，该算法应用于词性标注，其中隐藏状态是语法类别，观测是单词。它还支持统计句法分析，为句子找到最可能的句法分析树。在生物信息学中，它有助于比对生物序列和预测基因结构，将DNA或蛋白质序列视为观测，将功能元件视为隐藏状态。
相关技术
维特比算法与其他动态规划方法密切相关，例如前向-后向算法，后者计算所有可能状态序列上的概率，而不仅仅是计算最可能的一个。它也与Beam Search共享概念基础，这是一种用于序列生成的启发式搜索技术。在现代Machine learning和Artificial intelligence系统中，尤其是涉及Sequence-to-Sequence (Seq2Seq)模型和Large language model的系统，由于涉及的状态空间较大，通常优先使用束搜索而不是精确的维特比解码。
尽管Neural network方法兴起，维特比算法在混合系统中仍然具有相关性。例如，它可以用于解码语音识别中Neural network声学模型的输出，或在Natural language processing任务中强制执行结构约束。其数学清晰性和效率确保其在经典和当代应用中持续使用。