Tutorial notes for the Viterbi Algorithm problem This problem is stated in CLR 15-5. In pra ti e, Viterbi algorithm is used for spee h re ognition. 6
d
2
You are given a dire ted graph G = (V; E ) in whi h every b edge is labeled by a letter from a nite alphabet , that a a is there is a fun tion (u; v) that gives a label for the edge 3 (u; v) for every pair (u; v) 2 E . You are also given a distin1 guished vertex v0 and a string s =< l1 ; :::; l > of symbols b c from . Design a DP algorithm to he k whether there is a path starting at v0 labeled with s. a For example, let = fa; b; ; d; eg, v0 = 1 and s = ab 4 and onsider the following graph. It has a path f1; 5; 4; 2g 5 b labeled with s. Now we want to design a dynami programming algorithm for nding whether there is a path from v0 labeled with s. Step 1: Let 0 i k and 1 v n (that is, i indexes the letters of s and v the verti es). Then de ne A(i; v) = 1 if there is a path from v0 to v labeled with the pre x of length i of s, and A(i; v) = 0 otherwise. The nal answer is \yes" if there is v su h that A(k; v) = 1. Step 2: Initialize with A(0; v0 ) = 1 and for v 6= v0 A(0; v) = 0. Now the re urren e be omes: k
A(i; v) = maxfA(i
1; u)j(u; v) 2 E and (u; v) = l g That is, to set the value of A(i; v) we he k whether The array for the example above there is an edge labeled with l leading to A(i; v) from a is: vertex that was rea hed in the previous step. If there is inv 1 2 3 4 5 6 u su h that A(i 1; u) = 1, then it is possible to arrive to u by a path labeled with the pre x of length i 1 of s; 0 1 0 0 0 0 0 the ondition (u; v) 2 E states that (u; v) is an edge and 2 0 1 0 0 1 0 the ondition (u; v) = l states that this edge is labeled 2 0 0 1 1 0 0 with l . Note that there an be several paths leading to 3 0 1 0 0 0 0 a vertex, but we are only interested in an existen e of a path, not their number. This is why the re urren e has So there is a path from vertex max in it: if there is a path, A(i; v) be omes 1, otherwise 1 labeled with s whi h ends at vertex 2. A(i; v) = 0. Skipped. As usual, just ompute the array and then nd a non-zero value in the last row. If su
eed, output \path exists", otherwise output \no path" . For this problem, it is simplest to en ode the graph by its adja en y matrix with labels instead of 0/1 (that is, if a matrix M en odes the graph, M (u; v) = (u; v) if there is an edge (u; v), and some spe ial symbol not in if there is no edge (u; v) in the graph.) Suppose now that there is a path, and we want to output the verti es that onstitute the path. The idea is just to retra e the steps. That is, starting with a non-zero entry in the last row, nd an edge with the orre t label that leads to a vertex v for whi h A(i 1; v). The most straightforward algorithm outputs verti es in reverse order; make a re ursive pro edure in style of P rintOpt in the notes for s heduling to output the verti es in the orre t order. i
i
i
i
Step 3:
Step 4:
1