Module dyn_prog_pitch
[frames] | no frames]

Source Code for Module dyn_prog_pitch

  1  """Viterbi search.""" 
  2   
  3  from gmisclib import Num 
  4   
  5   
  6  HUGE = 1e30 
  7   
  8   
  9  # The internal representation of a path is a linked list of tuples: state: (state_id, prev_state) 
 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
63 -def _unwind(path):
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
76 -def _test_nodecost(t, xtra):
77 return (xtra[0][t,:], 0, len(xtra[0][t,:]))
78
79 -def _test_linkcost(t, xtra):
80 return (xtra[1], 0, len(xtra[1][0,:]))
81
82 -def _test1():
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
93 -def _test2():
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
106 -def _test3():
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
119 -def _test_nodecost3(t, xtra):
120 a, j0, jn = _test_nodecost(t, xtra) 121 return (a[2:-1], 2, len(a)-1)
122
123 -def _test4():
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
134 -def _test_linkcost3(t, xtra):
135 a, j0, jn = _test_linkcost(t, xtra) 136 return (a[:,2:-1], 2, a.shape[1]-1)
137
138 -def _test5():
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