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

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