wiki:

ViterbiAlgorithm


Version 1 (modified by llogan, 3 years ago) (diff)

make initial page from "doc/viterbi.txt"

This is a quick description of the Viterbi algorithm, aka dynamic programming algorithm.

Assume we have a 2D table:

    O   O   O   O   O   O   O

    O   O   O   O   O   O   O

    O   O   O   O   O   O   O

    O   O   O   O   O   O   O

That table has edges connecting points from each column to the next column and each edge has a score (only some edge and scores shown to keep it readable):

    O--5--O-----O-----O-----O-----O
     2   / 7   / \   / \   / \   /
      \ /   \ /   \ /   \ /   \ /
    O7-/--O--/--O--/--O--/--O--/--O
     \/ \/ 1/ \/ \/ \/ \/ \/ \/ \/
     /\ /\ 2\ /\ /\ /\ /\ /\ /\ /\
    O3-/--O--/--O--/--O--/--O--/--O
      / \   / \   / \   / \   / \
     1   \ 9   \ /   \ /   \ /   \
    O--2--O--1--O--5--O--3--O--8--O

Our goal is to find a path from left to right through it which minimizes the sum of the score of all edges. Of course left/right is just a convention here as it could be top/down too. Similarly the minimum could be the maximum by just flipping the sign.

Example of a path with scores:

    O   O   O   O   O   O   O

>---O.  O   O  .O-2-O   O   O
      5.     .7      .
    O   O-1-O   O   O 8 O   O
                       .
    O   O   O   O   O   O-1-O---> (sum here is 24)

The Viterbi algorithm simply solves column by column. For the previous column each point has a best path and a associated score:

    O-----5     O
     \
      \
    O  \  1     O
        \/
        /\
    O  /  2     O
      /
     /
    O-----2     O