1This is a quick description of the viterbi aka dynamic programing 2algorthm. 3 4Its reason for existence is that wikipedia has become very poor on 5describing algorithms in a way that makes it useable for understanding 6them or anything else actually. It tends now to describe the very same 7algorithm under 50 different names and pages with few understandable 8by even people who fully understand the algorithm and the theory behind. 9 10Problem description: (that is what it can solve) 11assume we have a 2d table, or you could call it a graph or matrix if you 12prefer 13 14 O O O O O O O 15 16 O O O O O O O 17 18 O O O O O O O 19 20 O O O O O O O 21 22 23That table has edges connecting points from each column to the next column 24and each edge has a score like: (only some edge and scores shown to keep it 25readable) 26 27 28 O--5--O-----O-----O-----O-----O 29 2 / 7 / \ / \ / \ / 30 \ / \ / \ / \ / \ / 31 O7-/--O--/--O--/--O--/--O--/--O 32 \/ \/ 1/ \/ \/ \/ \/ \/ \/ \/ 33 /\ /\ 2\ /\ /\ /\ /\ /\ /\ /\ 34 O3-/--O--/--O--/--O--/--O--/--O 35 / \ / \ / \ / \ / \ 36 1 \ 9 \ / \ / \ / \ 37 O--2--O--1--O--5--O--3--O--8--O 38 39 40 41Our goal is to find a path from left to right through it which 42minimizes the sum of the score of all edges. 43(and of course left/right is just a convention here it could be top down too) 44Similarly the minimum could be the maximum by just fliping the sign, 45Example of a path with scores: 46 47 O O O O O O O 48 49>---O. O O .O-2-O O O 50 5. .7 . 51 O O-1-O O O 8 O O 52 . 53 O O O O O O-1-O---> (sum here is 24) 54 55 56The viterbi algorthm now solves this simply column by column 57For the previous column each point has a best path and a associated 58score: 59 60 O-----5 O 61 \ 62 \ 63 O \ 1 O 64 \/ 65 /\ 66 O / 2 O 67 / 68 / 69 O-----2 O 70 71 72To move one column forward we just need to find the best path and associated 73scores for the next column 74here are some edges we could choose from: 75 76 77 O-----5--3--O 78 \ \8 79 \ \ 80 O \ 1--9--O 81 \/ \3 82 /\ \ 83 O / 2--1--O 84 / \2 85 / \ 86 O-----2--4--O 87 88Finding the new best pathes and scores for each point of our new column is 89trivial given we know the previous column best pathes and scores: 90 91 O-----0-----8 92 \ 93 \ 94 O \ 0----10 95 \/ 96 /\ 97 O / 0-----3 98 / \ 99 / \ 100 O 0 4 101 102 103the viterbi algorthm continues exactly like this column for column until the 104end and then just picks the path with the best score (above that would be the 105one with score 3) 106 107 108Author: Michael niedermayer 109Copyright LGPL 110 111