Is there any fast implementation of the Longest Common Subsequence algorithm for trajectory matching in Python? Ideally it would work with trajectories of different length in 2d spaces.
-
Do you have a quick link to save people from looking it up, specifically the reference you were examining – user681 Jan 25 '15 at 23:04
-
This is what I was working off of: cs.bu.edu/groups/dblab/pub_pdfs/icde02.pdf – Drew Jan 25 '15 at 23:45
-
The vertices of each matching sub sequence, are they equal? – huckfinn Jul 5 '16 at 16:52
The python module Machine Learning Python (mlpy) has an LCS method including an LCS for real series:
http://mlpy.sourceforge.net/docs/3.5/lcs.html
Perhaps you could also adapt the LCS algorithm for strings and test your own implementation against mlpy.
A quick google search results in the folloing Wikipedia page:
https://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Longest_common_subsequence#Python
I copied the content for backup purpose:
Computing the length of the LCS
def LCS(X, Y): m = len(X) n = len(Y) # An (m+1) times (n+1) matrix C = [[0] * (n + 1) for _ in range(m + 1)] for i in range(1, m+1): for j in range(1, n+1): if X[i-1] == Y[j-1]: C[i][j] = C[i-1][j-1] + 1 else: C[i][j] = max(C[i][j-1], C[i-1][j]) return C
Reading out an LCS
def backTrack(C, X, Y, i, j): if i == 0 or j == 0: return "" elif X[i-1] == Y[j-1]: return backTrack(C, X, Y, i-1, j-1) + X[i-1] else: if C[i][j-1] > C[i-1][j]: return backTrack(C, X, Y, i, j-1) else: return backTrack(C, X, Y, i-1, j)
Reading out all LCSs
def backTrackAll(C, X, Y, i, j): if i == 0 or j == 0: return set([""]) elif X[i-1] == Y[j-1]: return set([Z + X[i-1] for Z in backTrackAll(C, X, Y, i-1, j-1)]) else: R = set() if C[i][j-1] >= C[i-1][j]: R.update(backTrackAll(C, X, Y, i, j-1)) if C[i-1][j] >= C[i][j-1]: R.update(backTrackAll(C, X, Y, i-1, j)) return R
Usage example
X = "AATCC" Y = "ACACG" m = len(X) n = len(Y) C = LCS(X, Y) print "Some LCS: '%s'" % backTrack(C, X, Y, m, n) print "All LCSs: %s" % backTrackAll(C, X, Y, m, n)
It prints the following:
Some LCS: 'AAC' All LCSs: set(['ACC', 'AAC'])