diff options
Diffstat (limited to 'doc/viterbi.txt')
-rw-r--r-- | doc/viterbi.txt | 110 |
1 files changed, 110 insertions, 0 deletions
diff --git a/doc/viterbi.txt b/doc/viterbi.txt new file mode 100644 index 0000000000..d9d924f621 --- /dev/null +++ b/doc/viterbi.txt @@ -0,0 +1,110 @@ +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 + |