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.