ビタビアルゴリズム
「ビタビ経路; Viterbi path」および「ビタビアルゴリズム」という用語は、観測結果について1つの最も尤もらしい説明を与える動的計画法のアルゴリズムに関して使われる。例えば、動的計画法のアルゴリズムを使った統計的構文解析は、文字列について1つの最も尤もらしい解析結果を生じる。そのため、これを「ビタビ構文解析; Viterbi parse」と呼ぶこともある。
ビタビアルゴリズムは、アンドリュー・ビタビがノイズのあるデジタル通信経路における誤り検出訂正手法として生み出したものである。CDMAやGSMといったデジタル携帯電話、ダイヤルアップ接続用モデム、通信衛星、宇宙探査での通信、IEEE 802.11 無線LAN などの畳み込み符号の復号に広く利用されている。また、音声認識、自然言語処理、計算言語学、バイオインフォマティクスなどにも使われている。例えば、音声認識では、音声信号を観測された事象の系列として扱い、それを文字に変換したものがその音声信号に対応した「隠された原因」と見なされる。ビタビアルゴリズムは、与えられた音声信号から最も尤もらしい文字列を見つけ出す。
事象に対応した増分は、ある状態から別の状態への遷移確率に依存して決定される。例えばデータ通信において、シンボルの半分を奇数の状態のときに送り、残る半分を偶数の状態のときに送るということも可能である。さらに、多くの場合、状態遷移図は完全に連結されてはいない。単純な例として、自動車は、前進、停止、後退という3つの状態を持つとしたとき、前進から後退への直接の遷移は不可能であり、常に一旦は停止状態になる必要がある。増分と状態値の組合せを計算すると、最良値のみが残り、他の経路は捨てられる。基本アルゴリズムの変形として、後方探索だけでなく前方探索も許すものもある。
経路履歴を記録する必要がある。エンコーダの開始時の状態が既知の状態で、全経路を保持できるだけのメモリがあるなら、経路履歴は有限である。そうでない場合、リソースが限られているため、何らかのプログラム上の解決策を必要とする。1つの例として畳み込み符号化がある。その場合、性能を許容可能なレベルに維持しつつ、デコーダの履歴の深さを制限できる。ビタビアルゴリズムは非常に効率的だが、さらに計算負荷を削減する変形版も存在する。メモリ使用量は一定となる傾向がある。