Viterbi Algorithm - Pseudocode

Pseudocode

Here is some necessary set up for the problem. Given the observation space, the state space, a sequence of observations, transition matrix of size such that stores the transition probability of transiting from state to state, emission matrix of size such that stores the probability of observing from state, an array of initial probabilities of size such that stores the probability that .We say a path is a sequence of states that generate the observations .

In this dynamic programming problem, we construct two 2-dimensional tables of size . Each element of, stores the probability of the most likely path so far with that generates . Each element of, stores of the most likely path so far for

We fill entries of two tables by increasing order of .

, and

INPUT: The observation space, the state space, a sequence of observations such that if the observation at time is, transition matrix of size such that stores the transition probability of transiting from state to state, emission matrix of size such that stores the probability of observing from state, an array of initial probabilities of size such that stores the probability that OUTPUT: The most likely hidden state sequence A01 function VITERBI( O, S,π,Y,A,B ) : X A02 for each state s_i do A03 T₁←π_iB_i A04 T₂←0 A05 end for A06 for i←2,3,...,T do A07 for each state s_j do A08 T₁← A09 T₂← A10 end for A11 end for A12 z_T← A13 x_T←s_zT A14 for i←T,T-1,...,2 do A15 z_i-1←T₂ A16 x_i-1←s_zi-1 A17 end for A18 return X A19 end function