CSCE 411 Lecture 13

Lecture Slides

« previous | Monday, September 24, 2012 | next »

Longest Common Subsequence

Suppose you have a sequence $X=⟨x_1,x_2,\dots ,x_m⟩$ of elements over a finite set $S$.

A sequence $Z=⟨z_1,z_2,\dots z_k⟩$ over $S$ is called a subsequence of $X$ iff it can be obtained from $X$ by deleting elements.

Put differently, there exist indices $i_1<i_2<\dots <i_k$ such that $z_a=x_{i_a}$ for all $1\le a\le k$

For example, $⟨A,C,D,F⟩$ is a subsequence of $⟨A,B,C,D,E,F⟩$

Suppose $Y=⟨y_1,y_2,\dots ,y_n⟩$ is also a sequence over $S$.

We call $Z$ a common subsequence of $X$ and $Y$ iff it is a subsequence of $X$ and a subsequence of $Y$

For example, $⟨A,C,D,F⟩$ is a common subsequence of $⟨A,B,C,D,E,F⟩$ and $⟨A,A,C,B,A,D,F⟩$.

Given two sequences $X$ and $Y$ over a set $S$, what is the longest common subsequence $Z$ between them?

Naïve Solution: Brute Force

There are $2^m$ subsequences of $X$. We could check every one of them, filtering them by whether they are subsequences of $Y$ (this would take $O(n)$ time), and then determine the longest one. Overall, this takes $O(n{2}^m)$ time.

Dynamic Approach

If $X=⟨x_1,x_2,\dots ,x_m⟩$ is a sequence, let $X_i=⟨x_1,x_2,\dots ,x_i⟩$ be the $i$^th prefix of $X$ such that $1\le i\le m$.

Let $\mathrm{L}\mathrm{C}\mathrm{S}(X,Y)$ be the longest common subsequence between $X$ and $Y$.

Let $X=⟨x_1,x_2,\dots ,x_m⟩$ and $Y=⟨y_1,y_2,\dots ,y_n⟩$. Let $Z=⟨z_1,z_2,\dots ,z_k⟩$.

1. If $x_m=y_n$, then certainly $x_m=y_n=z_k$ and $Z_{k-1}$ is in $\mathrm{L}\mathrm{C}\mathrm{S}(X_{m-1},Y_{n-1})$.
2. If $x_m\ne y_n$, then $x_m\ne z_k$ implies that $Z$ is in $\mathrm{L}\mathrm{C}\mathrm{S}(X_{m-1},Y)$.
3. If $x_m\ne y_n$, then $y_m\ne z_k$ implies that $Z$ is in $\mathrm{L}\mathrm{C}\mathrm{S}(X,Y_{n-1}$.

(2) and (3) indicate overlapping subproblems of choosing the larger common subsequence of each of the two cases.

Recursive Solution

Let $C_{ij}$ be the length of an element in $\mathrm{L}\mathrm{C}\mathrm{S}(X_i,Y_j)$. $C_{ij}=\{\begin{array}{ll}0& i=0\vee j=0\\ C_{i-1,j-1}+1& i,j>0\wedge x_i=y_j\\ \max (C_{i,j-1},C_{i-1,j})& i,j>0\wedge x_i\ne y_j\end{array}$

Dynamic Programming Solution

Start our $C$ table by initializing the first row and column to 0 since the length of a common subsequence of [sequences of length 0] is 0.

Calculate $C_{1j}$ for $1\le j\le n$.

Calculate $C_{2j}$ for $1\le j\le n$. (etc.)

Return $C_{mn}$.

The complexity of computing this solution has been reduced to $O(mn)$.

In computing $C_{ij}$, this particular solution depends on the cells directly above, to the right, and diagonally from it.

Whenever we satisfy case (1), choosing the diagonal solution, we know that we have grabbed the $i$^th element from the end of $X_i$.

Keep track of the direction toward the optimal solution chosen (up, left, or diagonal)

To reconstruct the solution, start in $C_{mn}$ and follow arrows, taking $X_i$ whenever $C_{ij}$ has a "diagonal pointer".

Example

For sequences $X=⟨A,B,C,B⟩$ $Y=⟨B,D,C,A⟩$

	$y_j$	B	D	C	A
$x_j$	0	0	0	0	0
A	0	↑ 0	↑ 0	↑ 0	↖ 1
B	0	↖ 1	← 1	← 1	↑ 1
C	0	↑ 1	↑ 1	↖ 2	← 2
B	0	↑ 1	↑ 1	↑ 2	↑ 2

To construct the soluion, follow arrows and obtain "BC"