[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
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
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
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
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):
114
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
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
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
145
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
<!--
expandto(location.href);
// -->

```

 Generated by Epydoc 3.0.1 on Thu Jun 16 20:03:15 2011 http://epydoc.sourceforge.net