Viterbi sequence decoding for a finite hidden Markov model

Input: A finite discrete HMM $(S,Y,\pi ,A,B)$, an observation sequence $y=(y_1,\dots ,y_T)\in Y^T$ with $T\ge 1$, and a total order on $S$.

1. Form a trellis with $V_t=S$ at every layer. Set ${\alpha }_y(s)=\pi (s)B(s,y_1)$ and terminal weights ${\beta }_y(s)=1$.
2. For every $t=2,\dots ,T$, include the edge $(r,s)$ exactly when $A(r,s)>0$ and $B(s,y_t)>0$, and give it weight $w_t(r,s)=A(r,s)B(s,y_t)$.
3. Run Max-product Viterbi decoding on a finite trellis on this trellis using the supplied state order. If it returns no admissible path, return “zero evidence; no conditional sequence MAP.” Otherwise return its path as the decoded hidden-state sequence.

Zero transition or emission factors are omitted from the trellis, so every trellis path has positive joint mass.