doc: delete viterbi.txt
authorTimothy Gu <timothygu99@gmail.com>
Sat, 9 Nov 2013 23:36:37 +0000 (15:36 -0800)
committerStefano Sabatini <stefasab@gmail.com>
Mon, 11 Nov 2013 09:45:19 +0000 (10:45 +0100)
The description has been moved to the FFmpeg wiki:
https://trac.ffmpeg.org/wiki/ViterbiAlgorithm

Signed-off-by: Timothy Gu <timothygu99@gmail.com>
doc/viterbi.txt [deleted file]

diff --git a/doc/viterbi.txt b/doc/viterbi.txt
deleted file mode 100644 (file)
index 9782546..0000000
+++ /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