0,0 → 1,109 |
This is a quick description of the viterbi aka dynamic programing |
algorthm. |
|
Its reason for existence is that wikipedia has become very poor on |
describing algorithms in a way that makes it useable for understanding |
them or anything else actually. It tends now to describe the very same |
algorithm under 50 different names and pages with few understandable |
by even people who fully understand the algorithm and the theory behind. |
|
Problem description: (that is what it can solve) |
assume we have a 2d table, or you could call it a graph or matrix if you |
prefer |
|
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 like: (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. |
(and of course left/right is just a convention here it could be top down too) |
Similarly the minimum could be the maximum by just fliping 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 algorthm now solves this simply 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 |
|
|
To move one column forward we just need to find the best path and associated |
scores for the next column |
here are some edges we could choose from: |
|
|
O-----5--3--O |
\ \8 |
\ \ |
O \ 1--9--O |
\/ \3 |
/\ \ |
O / 2--1--O |
/ \2 |
/ \ |
O-----2--4--O |
|
Finding the new best paths and scores for each point of our new column is |
trivial given we know the previous column best paths and scores: |
|
O-----0-----8 |
\ |
\ |
O \ 0----10 |
\/ |
/\ |
O / 0-----3 |
/ \ |
/ \ |
O 0 4 |
|
|
the viterbi algorthm continues exactly like this column for column until the |
end and then just picks the path with the best score (above that would be the |
one with score 3) |
|
|
Author: Michael niedermayer |
Copyright LGPL |