Iterative Viterbi Decoding - The Algorithm

The Algorithm

A basic (non-optimized) version, finding the sequence s with the smallest normalized distance from some subsequence of t is:

// input is placed in observation s, template t, // and ] d // remaining elements in matrices are solely for internal computations (int, int, int) AverageSubmatchDistance(char s, char t, int d) { // score, subsequence start, subsequence end declare int e, B, E t' := t' := s' := s' := 'e' e := random do e' := e for i := 1 to n do d' := d' := e (e, B, E) := ViterbiDistance(s', t', d') e := e/(E-B+1) until (e == e') return (e, B, E) }

The ViterbiDistance procedure returns the tuple (e, B, E), i.e., the Viterbi score "e" for the match of t and the selected entry (B) and exit (E) points from it. "B" and "E" have to be recorded using a simple modification to Viterbi.

A modification that can be applied to CYK tables, proposed by Antoine Rozenknop, consists in subtracting e from all elements of the initial matrix d.