| 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 pathes and scores for each point of our new column is |
| trivial given we know the previous column best pathes 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 |
| |