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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle C_{2j}} for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1 \le j \le n} . (etc.)

Return Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle C_{mn}} .

The complexity of computing this solution has been reduced to Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(mn)} .

In computing Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} ^th element from the end of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X_i} .

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

To reconstruct the solution, start in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle C_{mn}} and follow arrows, taking Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X_i} whenever Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle C_{ij}} has a "diagonal pointer".

Example

For sequences Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X = \left\langle A, B, C, B \right\rangle} Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Y = \left\langle B, D, C, A \right\rangle}

	Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y_j}	B	D	C	A
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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"