CSCE 411 Lecture 13

Lecture Slides

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

Longest Common Subsequence

Suppose you have a sequence $X=\left\langle x_{1},x_{2},\ldots ,x_{m}\right\rangle$ of elements over a finite set $S$.

A sequence $Z=\left\langle z_{1},z_{2},\ldots z_{k}\right\rangle$ 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\leq a\leq k$

For example, $\left\langle A,C,D,F\right\rangle$ is a subsequence of $\left\langle A,B,C,D,E,F\right\rangle$

Suppose $Y=\left\langle y_{1},y_{2},\ldots ,y_{n}\right\rangle$ 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, $\left\langle A,C,D,F\right\rangle$ is a common subsequence of $\left\langle A,B,C,D,E,F\right\rangle$ and $\left\langle A,A,C,B,A,D,F\right\rangle$.

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(n2^{m})$ time.

Dynamic Approach

If $X=\left\langle x_{1},x_{2},\ldots ,x_{m}\right\rangle$ is a sequence, let $X_{i}=\left\langle x_{1},x_{2},\ldots ,x_{i}\right\rangle$ be the $i$^th prefix of $X$ such that $1\leq i\leq m$.

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

Let $X=\left\langle x_{1},x_{2},\ldots ,x_{m}\right\rangle$ and $Y=\left\langle y_{1},y_{2},\ldots ,y_{n}\right\rangle$. Let $Z=\left\langle z_{1},z_{2},\ldots ,z_{k}\right\rangle$.

1. If $x_{m}=y_{n}$, then certainly $x_{m}=y_{n}=z_{k}$ and $Z_{k-1}$ is in $\mathrm {LCS} (X_{m-1},Y_{n-1})$.
2. If $x_{m}\neq y_{n}$, then $x_{m}\neq z_{k}$ implies that $Z$ is in $\mathrm {LCS} (X_{m-1},Y)$.
3. If $x_{m}\neq y_{n}$, then $y_{m}\neq z_{k}$ implies that $Z$ is in $\mathrm {LCS} (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 {LCS} (X_{i},Y_{j})$. $C_{ij}={\begin{cases}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}\neq y_{j}\end{cases}}$

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\leq j\leq n$.

Calculate $C_{2j}$ for $1\leq j\leq 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=\left\langle A,B,C,B\right\rangle$ $Y=\left\langle B,D,C,A\right\rangle$

	$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"