Mercurial > hg > nsaunier > traffic-intelligence

comparison python/utils.py @ 285:5957aa1d69e1

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Integrating Mohamed's changes Changed the indicator interface to access values, so that the generic LCSS implementation can be used
author Nicolas Saunier <nicolas.saunier@polymtl.ca>
date Sat, 26 Jan 2013 19:02:25 -0500
parents f2cf16ad798f
children fa95796a76b3
comparison
equal deleted inserted replaced
284:f2cf16ad798f 285:5957aa1d69e1
163 163
164 ######################### 164 #########################
165 # maths section 165 # maths section
166 ######################### 166 #########################
167 167
168 def LCSS(l1, l2, threshold, distance): 168 def LCSS(l1, l2, threshold, distance, delta = float('inf')):
169 '''returns the longest common subsequence similarity 169 '''returns the longest common subsequence similarity
170 based on the threshold on distance between two elements of lists l1, l2''' 170 based on the threshold on distance between two elements of lists l1, l2
171 '''
171 from numpy import zeros, int as npint 172 from numpy import zeros, int as npint
172 m = len(l1) 173 m = len(l1)
173 n = len(l2) 174 n = len(l2)
174 similarity = zeros((m+1,n+1), dtype = npint) 175 similarity = zeros((m+1,n+1), dtype = npint)
175 for i in xrange(1,m+1): 176 for i in xrange(1,m+1):
176 for j in xrange(1,n+1): 177 for j in xrange(max(1,i-delta),min(n+1,i+delta)):
177 if distance(l1[i-1], l2[j-1])<threshold: 178 if distance(l1[i-1], l2[j-1])<threshold:
178 similarity[i][j] = similarity[i-1][j-1]+1 179 similarity[i][j] = similarity[i-1][j-1]+1
179 else: 180 else:
180 similarity[i][j] = max(similarity[i-1][j], similarity[i][j-1]) 181 similarity[i][j] = max(similarity[i-1][j], similarity[i][j-1])
181 return similarity[-1][-1] 182 return similarity[-1][-1]