chap16.htm

算法导论

<h2>Characterizing a longest common subsequence</h2><P>
A brute-force approach to solving the LCS problem is to enumerate all subsequences of <I>X</I> and check each subsequence to see if it is also a subsequence of <I>Y</I>, keeping track of the longest subsequence found. Each subsequence of <I>X</I> corresponds to a subset of the indices { 1, 2, . . . , <I>m</I>} of <I>X</I>. There are 2<I><SUP>m</I></SUP> subsequences of <I>X</I>, so this approach requires exponential time, making it impractical for long sequences.<P>
<a name="0818_154f"><a name="0818_1550">The LCS problem has an optimal-substructure property, however, as the following theorem shows. As we shall see, the natural class of subproblems correspond to pairs of "prefixes" of the two input sequences. To be precise, given a sequence <I>X</I> = <img src="../images/lftwdchv.gif"><I>x</I><SUB>1</SUB>, <I>x</I><SUB>2</SUB>, . . . ,<I>x<SUB>m</I></SUB><img src="../images/wdrtchv.gif">, we define the <I>i</I>th <I><B>prefix</I></B> of <I>X</I>, for <I>i</I> = 0, 1,...,<I>m</I>, as <I>X<SUB>i</I></SUB> = <img src="../images/lftwdchv.gif"><I>x</I><SUB>1</SUB>, <I>x</I><SUB>2</SUB>, . . . , <I>x<SUB>i</I></SUB><img src="../images/wdrtchv.gif"><I>. </I>For example, if <I>X</I> = <img src="../images/lftwdchv.gif"><I>A</I>, <I>B</I>, <I>C</I>, <I>B</I>, <I>D</I>, <I>A</I>, <I>B</I><img src="../images/wdrtchv.gif">, then <I>X</I><SUB>4</SUB> = <img src="../images/lftwdchv.gif"><I>A, B, C, B</I><img src="../images/wdrtchv.gif"> and <I>X</I><SUB>0</SUB> is the empty sequence.<P>
<a name="0818_1551">Theorem 16.1<a name="0818_1551"><P>
Let <I>X</I> = <img src="../images/lftwdchv.gif"><I>x</I><SUB>1</SUB>, <I>x</I><SUB>2</SUB>, . . . , <I>x<SUB>m</I></SUB><img src="../images/wdrtchv.gif"> and <I>Y</I> = <img src="../images/lftwdchv.gif"><I>y</I><SUB>1</SUB>, <I>y</I><SUB>2</SUB>, . . . , <I>y<SUB>n</I></SUB><img src="../images/wdrtchv.gif"> be sequences, and let <I>Z = </I><img src="../images/lftwdchv.gif"><I>z</I><SUB>1</SUB>, <I>z</I><SUB>2</SUB>, . . . , <I>z<SUB>k</I></SUB><img src="../images/wdrtchv.gif"> be any LCS of <I>X</I> and <I>Y</I>.<P>
1.     If <I>x<SUB>m</I></SUB> = <I>y<SUB>n</I></SUB>, then <I>z<SUB>k</I></SUB> = <I>x<SUB>m</I></SUB> = <I>y<SUB>n</I></SUB> and <I>Z<SUB>k</I>-l </SUB>is an LCS of <I>X<SUB>m</I>-l</SUB> and <I>Y<SUB>n</I>-l</SUB>.<P>
2.     If <I>x<SUB>m</I></SUB> <img src="../images/noteq.gif"> <I>y<SUB>n</I></SUB>, then <I>z<SUB>k</I></SUB> <img src="../images/noteq.gif"><I> </I>x<SUB>m<I></SUB> implies that </I>Z<I> is an LCS of </I>X<SUB>m<I></SUB>-<SUB>1</SUB> and </I>Y<I>.</I><P>
3.     If <I>x<SUB>m</I></SUB> <img src="../images/noteq.gif"> <I>y<SUB>n</I></SUB>, then z<I><SUB>k</I></SUB> <img src="../images/noteq.gif"> <I>y<SUB>n</I></SUB> implies that <I>Z</I> is an LCS of <I>X</I> and <I>Y<SUB>n</I>-l</SUB>.<P>
<I><B>Proof     </I></B>(1) If <I>z<SUB>k</SUB> </I><img src="../images/noteq.gif"><I> x<SUB>m</I></SUB>, then we could append x<I><SUB>m</I></SUB> = <I>y<SUB>n</I></SUB> to <I>Z</I> to obtain a common subsequence of <I>X</I> and <I>Y</I> of length <I>k</I> + 1, contradicting the supposition that <I>Z</I> is a <I>longest</I> common subsequence of <I>X</I> and <I>Y</I>. Thus, we must have <I>z<SUB>k</I></SUB> = <I>x<SUB>m</I></SUB> = <I>y<SUB>n</I></SUB>. Now, the prefix <I>Z<SUB>k</I>-l</SUB> is a length-(<I>k</I> - 1)common subsequence of <I>X<SUB>m</I>-1</SUB> and <I>Y<SUB>n-</I>l</SUB>. We wish to show that it is an LCS. Suppose for the purpose of contradiction that there is a common subsequence <I>W</I> of <I>X<SUB>m</I>-l</SUB> and <I>Y<SUB>n</I>-l</SUB> with length greater than <I>k</I> - 1. Then, appending <I>x<SUB>m</I></SUB> = <I>y<SUB>n</I></SUB> to <I>W</I> produces a common subsequence of <I>X</I> and <I>Y</I> whose length is greater than <I>k</I>, which is a contradiction.<P>
(2) If <I>z<SUB>k</I></SUB> <img src="../images/noteq.gif"> <I>x<SUB>m</I></SUB>, then <I>Z</I> is a common subsequence of <I>X<SUB>m</I>-1</SUB> and <I>Y</I>. If there were a common subsequence <I>W</I> of <I>X<SUB>m</I>-l</SUB> and <I>Y</I> with length greater than <I>k</I>, then <I>W</I> would also be a common subsequence of <I>X<SUB>m</I></SUB> and <I>Y</I>, contradicting the assumption that <I>Z</I> is an LCS of <I>X</I> and <I>Y</I>.<P>
(3) The proof is symmetric to (2).      <P>
The characterization of Theorem 16.1 shows that an LCS of two sequences contains within it an LCS of prefixes of the two sequences. Thus, the LCS problem has an optimal-substructure property. A recursive solution also has the overlapping-subproblems property, as we shall see in a moment.<P>
<P>







<h2>A recursive solution to subproblems</h2><P>
Theorem 16.1 implies that there are either one or two subproblems to examine when finding an LCS of <I>X</I> = <img src="../images/lftwdchv.gif"><I>x</I><SUB>1</SUB>, <I>x</I><SUB>2</SUB>, . . . , <I>x<SUB>m</I></SUB><img src="../images/wdrtchv.gif"> and <I>Y</I> = <img src="../images/lftwdchv.gif"><I>y</I><SUB>1</SUB>, <I>y</I><SUB>2</SUB>, . . . , <I>y<SUB>n</I></SUB><img src="../images/wdrtchv.gif">. If <I>x<SUB>m</I></SUB> = <I>y<SUB>n</I></SUB> we must find an LCS of <I>X<SUB>m</I>-l</SUB> and <I>Y<SUB>n</I>-l</SUB>. Appending <I>x<SUB>m</I></SUB> = <I>y<SUB>n,</I></SUB> to this LCS yields an LCS of <I>X</I> and <I>Y</I>. If <I>x<SUB>m</I></SUB> <img src="../images/noteq.gif"> <I>y<SUB>n</I></SUB>, then we must solve two subproblems: finding an LCS of <I>X<SUB>m</I>-l</SUB> and <I>Y</I> and finding an LCS of <I>X</I> and <I>Y<SUB>n</I>-1</SUB>. Whichever of these two LCS's is longer is an LCS of <I>X</I> and <I>Y</I>.<P>
We can readily see the overlapping-subproblems property in the LCS problem. To find an LCS of <I>X</I> and <I>Y</I>, we may need to find the LCS's of <I>X</I> and <I>Y<SUB>n</I>-l</SUB> and of <I>X<SUB>m</I>-l</SUB> and <I>Y</I>. But each of these subproblems has the subsubproblem of finding the LCS of <I>X<SUB>m</I>-l</SUB> and <I>Y<SUB>n-</I>1</SUB>. Many other subproblems share subsubproblems.<P>
Like the matrix-chain multiplication problem, our recursive solution to the LCS problem involves establishing a recurrence for the cost of an optimal solution. Let us define <I>c</I>[<I>i, j</I>] to be the length of an LCS of the sequences <I>X<SUB>i</I></SUB> and <I>Y<SUB>j</I></SUB>. If either <I>i</I> = 0 or <I>j</I> = 0, one of the sequences has length 0, so the LCS has length 0. The optimal substructure of the LCS problem gives the recursive formula<P>
<img src="316_a.gif"><P>
<h4><a name="0819_0001">(16.5)<a name="0819_0001"></sub></sup></h4><P>
<P>







<h2>Computing the length of an LCS</h2><P>
Based on equation (16.5), we could easily write an exponential-time recursive algorithm to compute the length of an LCS of two sequences. Since there are only <img src="../images/bound.gif">(<I>mn</I>) distinct subproblems, however, we can use dynamic programming to compute the solutions bottom up.<P>
<a name="081a_1551">Procedure LCS-<FONT FACE="Courier New" SIZE=2>LENGTH</FONT> takes two sequences <I>X</I> = <img src="../images/lftwdchv.gif"><I>x</I><SUB>1</SUB>,<I>x</I><SUB>2</SUB>,<I>...</I>,<I>x<SUB>m</I></SUB><img src="../images/wdrtchv.gif"> and <I>Y</I> = <img src="../images/lftwdchv.gif"><I>y</I><SUB>1</SUB>,<I>y</I><SUB>2</SUB>,<I>...</I>,<I>y<SUB>n</I></SUB><img src="../images/wdrtchv.gif"> as inputs. It stores the <I>c</I>[<I>i, j</I>] values in a table <I>c</I>[0 . . <I>m,</I> 0 . . <I>n</I>] whose entries are computed in row-major order. (That is, the first row of <I>c</I> is filled in from left to right, then the second row, and so on.) It also maintains the table <I>b</I>[1 . .<I> m</I>, 1 . . <I>n</I>] to simplify construction of an optimal solution. Intuitively, <I>b</I>[<I>i, j</I>] points to the table entry corresponding to the optimal subproblem solution chosen when computing <I>c</I>[<I>i, j</I>]. The procedure returns the <I>b</I> and <I>c</I> tables; <I>c</I>[<I>m, n</I>] contains the length of an LCS of <I>X</I> and Y.<P>
<pre>LCS-LENGTH(<I>X,Y</I>)</sub></sup></pre><P>
<pre>1 <I>m</I> <img src="../images/arrlt12.gif"> <I>length</I>[<I>X</I>]</sub></sup></pre><P>
<pre>2 <I>n</I> <img src="../images/arrlt12.gif"> <I>length</I>[<I>Y</I>]</sub></sup></pre><P>
<pre>3 <B>for</B> <I>i</I> <img src="../images/arrlt12.gif"> 1 <B>to</B> <I>m</I></sub></sup></pre><P>
<pre>4      <B>do</B> <I>c</I>[<I>i</I>,0] <img src="../images/arrlt12.gif"> 0</sub></sup></pre><P>
<pre>5 <B>for</B> <I>j</I> <img src="../images/arrlt12.gif"> 0 <B>to</B> <I>n</I></sub></sup></pre><P>
<pre>6      <B>do</B> <I>c</I>[0, <I>j</I>] <img src="../images/arrlt12.gif"> 0</sub></sup></pre><P>
<pre>7 <B>for</B> <I>i</I> <img src="../images/arrlt12.gif"> 1 <B>to</B> <I>m</I></sub></sup></pre><P>
<pre>8      <B>do for </B><I>j</I> <img src="../images/arrlt12.gif"> 1 <B>to</B> <I>n</I></sub></sup></pre><P>
<pre>9             <B>do if</B> <I>x<SUB>i</I></SUB> = <I>y<SUB>j</I></sub></sup></pre><P>
<pre>10                   <B>then</B> <I>c</I>[<I>i</I>, <I>j</I>] <img src="../images/arrlt12.gif"> <I>c</I>[<I>i</I> - 1, <I>j</I> -1] + 1</sub></sup></pre><P>
<pre>11                        <I>b</I>[<I>i</I>, <I>j</I>] <img src="../images/arrlt12.gif"> &quot;<img src="../images/uplftar.gif">&quot;</sub></sup></pre><P>
<pre>12                   <B>else if</B> <I>c</I>[<I>i</I> - 1, <I>j</I>] <img src="../images/gteq.gif"> <I>c</I>[<I>i</I>, <I>j</I> - 1]</sub></sup></pre><P>
<pre>13                           <B>then</B> <I>c</I>[<I>i</I>, <I>j</I>] <img src="../images/arrlt12.gif"> <I>c</I>[<I>i</I> - 1, <I>j</I>]</sub></sup></pre><P>
<pre>14                                <I>b</I>[<I>i</I>, <I>j</I>] <img src="../images/arrlt12.gif"> &quot;<img src="../images/arrup.gif">&quot;</sub></sup></pre><P>
<pre>15                           <B>else</B> <I>c</I>[<I>i</I>, <I>j</I>] <img src="../images/arrlt12.gif"> <I>c</I>[<I>i</I>, <I>j</I> -1]</sub></sup></pre><P>
<pre>16                                <I>b</I>[<I>i</I>, <I>j</I>] <img src="../images/arrlt12.gif"> &quot;<img src="../images/arrlt12.gif">&quot;</sub></sup></pre><P>
<pre>17 <B>return</B> <I>c</I> and <I>b</I></sub></sup></pre><P>
Figure 16.3 shows the tables produced by LCS-<FONT FACE="Courier New" SIZE=2>LENGTH</FONT> on the sequences <I>X</I> = <img src="../images/lftwdchv.gif"><I>A, B, C, B, D, A, B</I><img src="../images/wdrtchv.gif"> and <I>Y</I> = <img src="../images/lftwdchv.gif"><I>B, D, C, A, B, A</I><img src="../images/wdrtchv.gif">. The running time of the procedure is <I>O</I>(<I>mn</I>), since each table entry takes <I>O</I>(1) time to compute.<P>
<P>







<h2>Constructing an LCS</h2><P>
The <I>b</I> table returned by LCS-<FONT FACE="Courier New" SIZE=2>LENGTH</FONT> can be used to quickly construct an LCS of <I>X</I> = <img src="../images/lftwdchv.gif"><I>x</I><SUB>1</SUB>,<I>x</I><SUB>2</SUB>,<I>...</I>,<I>x<SUB>m</I></SUB>) and <I>Y</I> = <img src="../images/lftwdchv.gif"><I>y</I><SUB>1</SUB>,<I>y</I><SUB>2</SUB>,...,<I>y<SUB>n</I></SUB>). We simply begin at <I>b</I>[<I>m, n</I>] and trace through the table following the arrows. Whenever we encounter a "<img src="../images/uplftar.gif"> in entry <I>b</I>[<I>i,j</I>], it implies that<I> x<SUB>i</SUB> = y<SUB>j</I></SUB> is an element of the LCS. The elements of the LCS are encountered in reverse order by this method. The following recursive procedure prints out an LCS of <I>X</I> and <I>Y </I>in the proper, forward order. The initial invocation is <FONT FACE="Courier New" SIZE=2>PRINT</FONT>-LCS(<I>b, X</I>, <I>length</I>[<I>X</I>], <I>length</I>[<I>Y</I>]).<P>
<img src="318_a.gif"><P>
<h4><a name="081b_1553">Figure 16.3 The c and b tables computed by LCS-<FONT FACE="Courier New" SIZE=2>LENGTH</FONT> on the sequences X = <img src="../images/lftwdchv.gif">A, B, C, B, D, A, B<img src="../images/wdrtchv.gif"> and Y = <img src="../images/lftwdchv.gif">B, D, C, A, B, A<img src="../images/wdrtchv.gif">. The square in row i and column j contains the value of c[i, j] and the appropriate arrow for the value of b[i, j]. The entry 4 in c[7, 6]--the lower right-hand corner of the table--is the length of an LCS <img src="../images/lftwdchv.gif">B, C, B, A<img src="../images/wdrtchv.gif"> of X and Y. For i, j &gt; 0, entry c[i, j] depends only on whether x<SUB>i</SUB> = y<SUB