Commit | Line | Data |
---|---|---|

dc7d978a MN |
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 pathes and scores for each point of our new column is | |

89 | trivial 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 | ||

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 |