Longest Common Subsequence (LCS)

Standard LCS

mlpy.lcs_std(x, y)

Standard Longest Common Subsequence (LCS) algorithm as described in [Cormen01].

The elements of sequences must be coded as integers.

Parameters :

x : 1d integer array_like object (N)

first sequence

y : 1d integer array_like object (M)

second sequence

Returns :

length : integer

length of the LCS of x and y

path : tuple of two 1d numpy array (path_x, path_y)

path of the LCS

Example

Reproducing the example in figure 15.6 of [Cormen01], where sequence X = (A, B, C, B, D, A, B) and Y = (B, D, C, A, B, A).

>>> import mlpy
>>> x = [0,1,2,1,3,0,1] # (A, B, C, B, D, A, B)
>>> y = [1,3,2,0,1,0] # (B, D, C, A, B, A)
>>> length, path = mlpy.lcs_std(x, y)
>>> length
4
>>> path
(array([1, 2, 3, 5]), array([0, 2, 4, 5]))   

[Cormen01]

(1, 2) H Cormen et al.. Introduction to Algorithms, Second Edition. The MIT Press, 2001.

LCS for real series

mlpy.lcs_real(x, y, eps, delta)

Longest Common Subsequence (LCS) for series composed by real numbers as described in [Vlachos02].

Parameters :

x : 1d integer array_like object (N)

first sequence

y : 1d integer array_like object (M)

second sequence

eps : float (>=0)

matching threshold

delta : int (>=0)

controls how far in time we can go in order to match a given point from one series to a point in another series

Returns :

length : integer

length of the LCS of x and y

path : tuple of two 1d numpy array (path_x, path_y)

path of the LCS

[Vlachos02]

M Vlachos et al.. Discovering Similar Multidimensional Trajectories. In Proceedings of the 18th international conference on data engineering, 2002