Subversion Repositories Kolibri OS

Rev

Go to most recent revision | Blame | Last modification | View Log | RSS feed

  1. This is a quick description of the viterbi aka dynamic programing
  2. algorthm.
  3.  
  4. Its reason for existence is that wikipedia has become very poor on
  5. describing algorithms in a way that makes it useable for understanding
  6. them or anything else actually. It tends now to describe the very same
  7. algorithm under 50 different names and pages with few understandable
  8. by even people who fully understand the algorithm and the theory behind.
  9.  
  10. Problem description: (that is what it can solve)
  11. assume we have a 2d table, or you could call it a graph or matrix if you
  12. prefer
  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.  
  23. That table has edges connecting points from each column to the next column
  24. and each edge has a score like: (only some edge and scores shown to keep it
  25. readable)
  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.  
  41. Our goal is to find a path from left to right through it which
  42. minimizes 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)
  44. Similarly the minimum could be the maximum by just fliping the sign,
  45. Example 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.  
  56. The viterbi algorthm now solves this simply column by column
  57. For the previous column each point has a best path and a associated
  58. score:
  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.  
  72. To move one column forward we just need to find the best path and associated
  73. scores for the next column
  74. here 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.  
  88. Finding the new best paths and scores for each point of our new column is
  89. trivial given we know the previous column best paths 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.  
  103. the viterbi algorthm continues exactly like this column for column until the
  104. end and then just picks the path with the best score (above that would be the
  105. one with score 3)
  106.  
  107.  
  108. Author: Michael niedermayer
  109. Copyright LGPL
  110.