1 """Viterbi search."""
2
3 from gmisclib import Num
4
5
6 HUGE = 1e30
7
8
9
10
11 -def path(nodecost, linkcost, extra_info, N, T):
12 """This function returns a tuple of the cost of the best path
13 and the best path, shown as an array: (cost, [j])
14
15 nodecost(t, extra_info) -> ([j-j0], j0, jn) at time t, pitch=j
16 All nodes with j<j0 or j>=jn have infinite cost.
17 linkcost(t, extra_info) -> ([j1, j2-j0], j0, jn) this is the
18 cost to go from (t,j1) to (t+1,j2),
19 where j=pitch. Note the first index spans from 0 to N.
20 All links that have either j1 or j1 outside of [j0,jn) have infinite cost.
21 The extra_info argument isn't used by this function;
22 it is simply passed down to the nodecost() and linkcost
23 functions.
24 T=number of time steps
25 N = Largest possible pitch
26 """
27
28 bestpathto = []
29 tmp, j0, jn = nodecost(0, extra_info)
30 assert j0>=0 and j0<=jn and jn<=N
31 cost = Num.zeros((N,), Num.Float) + HUGE
32 cost[j0:jn] = tmp
33 bestpathto = [ (j, None) for j in range(N) ]
34
35 for t in range(1,T):
36 nbp = []
37 ncost = Num.zeros((N,), Num.Float)
38 nbp = Num.zeros((N,), Num.PyObject)
39 nodecost_t, j0, jn = nodecost(t, extra_info)
40 assert j0>=0 and j0<=jn and jn<=N
41 linkcost_t, jj0, jjn = linkcost(t, extra_info)
42 jjj0 = max(j0, jj0)
43 jjjn = min(jn, jjn)
44 for j in range(0, jjj0):
45 ncost[j] = HUGE
46 nbp[j] = None
47 for j in range(jjj0, jjjn):
48 cc = cost + linkcost_t[:,j-jj0]
49 o = Num.argmin(cc)
50 ncost[j] = cc[o] + nodecost_t[j-j0]
51 nbp[j] = (j, bestpathto[o])
52 for j in range(jjjn, N):
53 ncost[j] = HUGE
54 nbp[j] = None
55 bestpathto = nbp
56 cost = ncost
57
58 jj = Num.argmin(cost)
59
60 return (cost[jj], _unwind(bestpathto[jj]))
61
62
64 """Converts the intermediate nested tuple representation to a linear list."""
65 o = []
66 while 1:
67 id, prev = path
68 o.append(id)
69 if prev is None:
70 o.reverse()
71 return o
72 path = prev
73
74
75
77 return (xtra[0][t,:], 0, len(xtra[0][t,:]))
78
80 return (xtra[1], 0, len(xtra[1][0,:]))
81
83 T = 10
84 N = 7
85 noc = Num.zeros((T,N), Num.Float) + 5
86 noc[:,3] = 1
87 linkc = Num.zeros((N,N), Num.Float) + 2
88
89 c, p = path(_test_nodecost, _test_linkcost, (noc, linkc), N, T)
90 assert abs(c - (10*1 + 9*2)) < 0.0001
91 assert p == [3]*T
92
94 T = 10
95 N = 7
96 noc = Num.zeros((T,N), Num.Float) + 5
97 for i in range(T):
98 noc[i,i%N] = 1
99 linkc = Num.zeros((N,N), Num.Float) + 2
100
101 c, p = path(_test_nodecost, _test_linkcost, (noc, linkc), N, T)
102 assert abs(c - (10*1 + 9*2)) < 0.0001
103 assert p == [0,1,2,3,4,5,6,0,1,2]
104
105
107 T = 10
108 N = 7
109 noc = Num.zeros((T,N), Num.Float) + 1
110 noc[0,0] = 0
111 linkc = Num.zeros((N,N), Num.Float) + 2
112 for i in range(N):
113 linkc[i,(i+1)%N] = 1
114
115 c, p = path(_test_nodecost, _test_linkcost, (noc, linkc), N, T)
116 assert abs(c - (0+9*1 + 9*1)) < 0.0001
117 assert p == [0,1,2,3,4,5,6,0,1,2]
118
120 a, j0, jn = _test_nodecost(t, xtra)
121 return (a[2:-1], 2, len(a)-1)
122
124 T = 10
125 N = 7
126 noc = Num.zeros((T,N), Num.Float) + 5
127 noc[:,3] = 1
128 linkc = Num.zeros((N,N), Num.Float) + 2
129
130 c, p = path(_test_nodecost3, _test_linkcost, (noc, linkc), N, T)
131 assert abs(c - (10*1 + 9*2)) < 0.0001
132 assert p == [3]*T
133
135 a, j0, jn = _test_linkcost(t, xtra)
136 return (a[:,2:-1], 2, a.shape[1]-1)
137
139 T = 10
140 N = 7
141 noc = Num.zeros((T,N), Num.Float) + 5
142 noc[:,3] = 1
143 linkc = Num.zeros((N,N), Num.Float) + 2
144 linkc[3,3] = 1
145
146 c, p = path(_test_nodecost3, _test_linkcost3, (noc, linkc), N, T)
147 assert abs(c - (10*1 + 9*2 - (T-1)*1)) < 0.0001
148 assert p == [3]*T
149
150
151 if __name__ == '__main__':
152 _test1()
153 _test2()
154 _test3()
155 _test4()
156 _test5()
157