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