ビタビアルゴリズム
これらは、状態から3つ組 (prob, v_path, v_prob) へのマッピングであり、prob は初期状態から現在状態までの全経路の確率、v_path は現在状態までのビタビ経路、v_prob は現在状態までのビタビ経路の確率である。マッピング T は与えられた時点 t についてのこの情報を保持し、メインループで構築する U は t+1 の時点についての同様の情報を保持する。マルコフ性があるため、t 以前の時点に関する情報は不要である。
このアルゴリズムでは、まず T を初期の確率で初期化する。ある状態の全体確率は単にその状態の初期の確率となる。初期状態へのビタビ経路は、その状態のみを含むシングルトン経路である。ビタビ経路の確率は、初期の確率と等しい。
メインループでは、y から順に観測結果を取り出す。T はそこまでの時点での正しい情報を含むが、現在の観測時点に関する情報は含まない。このアルゴリズムでは次に、考えられる次の状態についての3つ組 (prob, v_path, v_prob) を計算する。与えられた次の状態の全体確率 total は、その状態に到達する全経路の確率の総和によって得られる。より正確に言えば、このアルゴリズムは考えられる全ての元の状態について繰り返している。それぞれの元の状態について T は、その状態に到達する全経路の全体確率を保持している。この確率に、その状態で現在の観測値が得られる確率と次の状態に遷移する確率をかける。それによって得られる確率 prob を total に加算する。ビタビ経路の確率も同様に求められるが、その場合は全経路の総和を計算するのではなく、最大値を持つ経路を選択する。初期状態では、最大値 valmax はゼロに設定されている。