Mercurial > hg > nsaunier > traffic-intelligence

comparison python/utils.py @ 322:28661c5887d3

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Corrected a major bug for LCSS Added functions to test all alignments when computing the LCSS with a finite delta
author Nicolas Saunier <nicolas.saunier@polymtl.ca>
date Tue, 07 May 2013 18:43:40 +0200
parents 6c068047edbf
children efd4dd4665ac
comparison
equal deleted inserted replaced
321:a5e40bd04cf4 322:28661c5887d3
177 def LCSS(l1, l2, threshold, distance, delta = float('inf')): 177 def LCSS(l1, l2, threshold, distance, delta = float('inf')):
178 '''returns the longest common subsequence similarity 178 '''returns the longest common subsequence similarity
179 based on the threshold on distance between two elements of lists l1, l2 179 based on the threshold on distance between two elements of lists l1, l2
180 ''' 180 '''
181 from numpy import zeros, int as npint 181 from numpy import zeros, int as npint
182 m = len(l1) 182 n1 = len(l1)
183 n = len(l2) 183 n2 = len(l2)
184 similarity = zeros((m+1,n+1), dtype = npint) 184 similarity = zeros((n1+1,n2+1), dtype = npint)
185 for i in xrange(1,m+1): 185 for i in xrange(1,n1+1):
186 for j in xrange(max(1,i-delta),min(n+1,i+delta)): 186 for j in xrange(max(1,i-delta),min(n2+1,i+delta+1)):
187 if distance(l1[i-1], l2[j-1])<=threshold: 187 if distance(l1[i-1], l2[j-1])<=threshold:
188 similarity[i][j] = similarity[i-1][j-1]+1 188 similarity[i][j] = similarity[i-1][j-1]+1
189 else: 189 else:
190 similarity[i][j] = max(similarity[i-1][j], similarity[i][j-1]) 190 similarity[i][j] = max(similarity[i-1][j], similarity[i][j-1])
191 return similarity[-1][-1] 191 return max(max(similarity[:,-1]), max(similarity[-1,:]))
192
193 def normalizedLCSS(l1, l2, threshold, distance, delta = float('inf'), lengthMethod = min):
194 ''' compute the normalized LCSS
195 ie, the LCSS divided by the min or mean of the indicator lengths (using lengthMethod)
196 lengthMethod = lambda x,y:float(x,y)/2'''
197 return float(LCSS(l1, l2, threshold, distance, delta))/lengthMethod(len(l1), len(l2))
198
199 def DLCSS(l1, l2, threshold, distance, delta = float('inf'), lengthMethod = min):
200 ''' compute the LCSS distance'''
201 return 1-normalizedLCSS(l1, l2, threshold, distance, delta, lengthMethod)
202
203 def alignedLCSS(_l1, _l2, threshold, distance, delta):
204 '''returns the best matching if using a finite delta by shiftinig the series alignments'''
205 if len(_l2) < len(_l1): # l1 is the shortest
206 l1 = _l2
207 l2 = _l1
208 else:
209 l1 = _l1
210 l2 = _l2
211 n1 = len(l1)
212 n2 = len(l2)
213 # for i in xrange(delta, n1+n2-delta): # i is the alignment of the end of l1 in l2
214 # print l1[min(-i-1,n1):] # min(n1+n2-i,n1)
215 # print l2[max(0,i-n1):]
216 # print LCSS(l1[min(-i-1,n1):], l2[max(0,i-n1):], threshold, distance, delta)
217 lcss = [LCSS(l1[min(-i-1,n1):], l2[max(0,i-n1):], threshold, distance, delta) for i in xrange(delta, n1+n2-delta)]
218 return max(lcss)
219
220 def normalizedAlignedLCSS(l1, l2, threshold, distance, delta, lengthMethod = min):
221 return float(alignedLCSS(l1, l2, threshold, distance, delta))/lengthMethod(len(l1), len(l2))
222
223 def alignedDLCSS(l1, l2, threshold, distance, delta, lengthMethod = min):
224 return 1-normalizedAlignedLCSS(l1, l2, threshold, distance, delta, lengthMethod)
192 225
193 def framesToTime(nFrames, frameRate, initialTime = (0.,0.,0.)): 226 def framesToTime(nFrames, frameRate, initialTime = (0.,0.,0.)):
194 'returns hour, minutes and seconds' 227 'returns hour, minutes and seconds'
195 from math import floor 228 from math import floor
196 from datetime import time 229 from datetime import time