维特比算法 Viterbi algorithm

维特比算法是一种动态规划算法,其被用于寻找最可能产生观测事件序列的维特比路径——隐含状态序列,尤其是马尔科夫信息源上下文和隐马尔科夫模型中。例如在统计句法分析中,动态规划算法可被用于发现最可能的上下文派生字符串,其也被称为 「维特比分析」。

维特比算法由安德鲁·维特比(Andrew Viterbi)于 1967 年提出,主要用在数字通信链路中解卷积以消除噪音。这种算法被广泛应用于 CDMA 和 GSM 数字蜂窝网络、调制解调器、卫星、深空通信和 802.11 无线网络中,主要用于解卷积码,其现在也常被用于语音识别、关键字识别、计算语言学和生物信息学。

语音识别中,声音信号可作为观察到的时间序列,文本字符串则被看作是隐含的原因,因此,可基于声音信号采用维特比算法,并以此寻找最有可能的文本字符串。