Mercurial > hg > nsaunier > traffic-intelligence

comparison python/utils.py @ 371:924e38c9f70e

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
work in progress
author Nicolas Saunier <nicolas.saunier@polymtl.ca>
date Tue, 16 Jul 2013 01:36:50 -0400
parents 97e8fa0ee9a1
children 349eb1e09f45
comparison
equal deleted inserted replaced
370:97e8fa0ee9a1 371:924e38c9f70e
249 249
250 eg distance(p1, p2) < epsilon 250 eg distance(p1, p2) < epsilon
251 ''' 251 '''
252 from numpy import argmax 252 from numpy import argmax
253 self.similarities(l1, l2) 253 self.similarities(l1, l2)
254 imax = argmax(self.similarityTable[:,-1]) 254 self.similarityTable = self.similarityTable[:, :min(len(l2), len(l1)+self.delta)+1]
255 jmax = argmax(self.similarityTable[-1,:])
256 if computeSubSequence: 255 if computeSubSequence:
257 if self.similarityTable[imax, -1] > self.similarityTable[-1, jmax]: 256 self.subSequenceIndices = self.subSequence(len(l1), len(l2))
258 self.similarityTable = self.similarityTable[:imax+1, :] 257 return self.similarityTable[-1,-1]
259 self.subSequenceIndices = self.subSequence(imax, len(l2))
260 else:
261 self.similarityTable = self.similarityTable[:, :jmax+1]
262 self.subSequenceIndices = self.subSequence(len(l1), jmax)
263 return self.similarityTable[-1,-1]
264 else:
265 return max(self.similarityTable[imax, -1], self.similarityTable[-1, jmax])
266 258
267 def _compute(self, _l1, _l2, computeSubSequence = False): 259 def _compute(self, _l1, _l2, computeSubSequence = False):
268 '''returns the best matching if using a finite delta by shiftinig the series alignments''' 260 '''returns the best matching if using a finite delta by shiftinig the series alignments'''
269 if self.aligned: 261 if self.aligned:
270 from numpy import argmax 262 from numpy import argmax
271 if len(_l2) < len(_l1): # l1 is the shortest 263 if len(_l2) < len(_l1): # l1 is the shortest
272 l1 = _l2 264 l1 = _l2
273 l2 = _l1 265 l2 = _l1
266 revertIndices = True
274 else: 267 else:
275 l1 = _l1 268 l1 = _l1
276 l2 = _l2 269 l2 = _l2
270 revertIndices = False
277 n1 = len(l1) 271 n1 = len(l1)
278 n2 = len(l2) 272 n2 = len(l2)
279 # for i in xrange(min(delta,n1), max(n1+n2-delta, n2+1)): # i is the alignment of the end of l1 in l2 273 # for i in xrange(min(delta,n1), max(n1+n2-delta, n2+1)): # i is the alignment of the end of l1 in l2
280 # print l1[min(-i-1,n1):] # min(n1+n2-i,n1) 274 # print l1[min(-i-1,n1):] # min(n1+n2-i,n1)
281 # print l2[max(0,i-n1):] 275 # print l2[max(0,i-n1):]
282 # print LCSS(l1[min(-i-1,n1):], l2[max(0,i-n1):], similarityFunc, delta) 276 # print LCSS(l1[min(-i-1,n1):], l2[max(0,i-n1):], similarityFunc, delta)
283 lcssValues = {} 277 lcssValues = {}
284 similarityTables = {} 278 similarityTables = {}
285 for i in xrange(min(self.delta,n1), max(n1+n2-self.delta, n2+1), max(1,self.delta)): 279 for i in xrange(min(self.delta,n1), max(n1+n2-self.delta, n2+1)):
286 print l1[min(-i-1,n1):] # min(n1+n2-i,n1) 280 #print l1[min(-i-1,n1):] # min(n1+n2-i,n1)
287 print l2[max(0,i-n1):] 281 #print l2[max(0,i-n1):]
288 lcssValues[i] = self.computeLCSS(l1[min(-i-1,n1):], l2[max(0,i-n1):]) 282 lcssValues[i] = self.computeLCSS(l1[min(-i-1,n1):], l2[max(0,i-n1):])
289 print i, lcssValues[i] 283 #print i, lcssValues[i]
290 similarityTables[i] = self.similarityTable 284 similarityTables[i] = self.similarityTable
291 imax = argMaxDict(lcssValues) 285 imax = argMaxDict(lcssValues)
292 self.similarityTable = similarityTables[imax] 286 self.similarityTable = similarityTables[imax]
293 self.subSequenceIndices = self.subSequence(self.similarityTable.shape[0]-1, self.similarityTable.shape[1]-1) 287 self.subSequenceIndices = self.subSequence(self.similarityTable.shape[0]-1, self.similarityTable.shape[1]-1)
294 self.alignmentShift = max(0,imax-n1)-min(-imax-1,n1) 288 if revertIndices:
289 self.subSequenceIndices = [(j+imax-n1,i) for i,j in self.subSequenceIndices]
290 self.alignmentShift = imax-n1
291 else:
292 self.subSequenceIndices = [(i+n1-imax,j) for i,j in self.subSequenceIndices]
293 self.alignmentShift = n1-imax
295 return lcssValues[imax] 294 return lcssValues[imax]
296 else: 295 else:
297 return self.computeLCSS(_l1, _l2, computeSubSequence) 296 return self.computeLCSS(_l1, _l2, computeSubSequence)
298 297
299 def compute(self, l1, l2, computeSubSequence = False): 298 def compute(self, l1, l2, computeSubSequence = False):