Longest common subsequence - Revision history

166.137.10.116: /* Time */

2011-05-31T05:07:03Z

‎Time

Brian: Distingiush|Longest common substring

2011-03-18T21:45:46Z

Distingiush|Longest common substring

Brian: applications

2011-03-18T21:42:29Z

applications

Brian: reductions

2011-03-02T21:26:05Z

reductions

Brian: CSS

2011-03-02T21:09:19Z

CSS

Brian: CSS

2011-03-02T21:06:42Z

CSS

Brian: references

2011-03-02T21:02:36Z

references

Brian: /* References */

2011-03-02T20:56:40Z

‎References

Brian at 20:56, 2 March 2011

2011-03-02T20:56:18Z

Show changes

Brian: Created page with "The '''longest common subsequence''' problem is the problem of finding a sequence of maximal length that is a subsequence of two input sequences. Formally, given two sequence..."

2010-11-16T07:06:12Z

Created page with "The '''longest common subsequence''' problem is the problem of finding a sequence of maximal length that is a subsequence of two input sequences. Formally, given two sequence..."

New page

The '''longest common subsequence''' problem is the problem of finding a sequence of maximal length that is a [[subsequence]] of two input sequences. Formally, given two sequences <math>[x_1, x_2, ..., x_m]</math> and <math>[y_1, y_2, ..., y_n]</math>.

@@ Line 66: / Line 66: @@
 The function <math>\operatorname{LCS\_len}</math> defined above takes constant time to transition from one state to another, and there are <math>(m+1)(n+1)</math> states, so the time taken overall is <math>\Theta(mn)</math>.
-The function <math>\operatorname{LCS}</math> as written above may take longer to compute if we naively store an array of strings where each entry is the longest common subsequence of some subinstance, because then a lot of string copying occurs during transitions, and this presumably takes more than constant time. If we actually wish to reconstruct a longest common subsequence, we may compute the <math>\operatorname{LCS\_len}</math> table first, making a note of "what happened" when each value was computed (\emph{i.e.}, which subinstance's solution was used) and then backtrack once <math>\operatorname{LCS\_len}(m,n)</math> is known. This then also takes <math>\Theta(mn)</math> time.
+The function <math>\operatorname{LCS}</math> as written above may take longer to compute if we naively store an array of strings where each entry is the longest common subsequence of some subinstance, because then a lot of string copying occurs during transitions, and this presumably takes more than constant time. If we actually wish to reconstruct a longest common subsequence, we may compute the <math>\operatorname{LCS\_len}</math> table first, making a note of "what happened" when each value was computed (''i.e.'', which subinstance's solution was used) and then backtrack once <math>\operatorname{LCS\_len}(m,n)</math> is known. This then also takes <math>\Theta(mn)</math> time.
 Using the recursive definition of <math>\operatorname{LCS\_len}</math> as written may be faster (provided memoization is used), because we may not have to compute all values that we would compute in the dynamic solution. The runtime is then <math>O(mn)</math> (no improvement is seen in the worst case).
 In the dynamic solution, if we desire only the length of the LCS, we notice that we only need to keep two rows of the table at any given time, since we will never be looking back at <math>p</math>-values less than the current <math>p</math> minus one. In fact, keeping only two rows at any given time may be more cache-optimal, and hence result in a constant speedup.
 ====Memory====
 The memory usage is <math>\Theta(mn)</math> for the dynamic solution. The recursive solution may use less memory if hashing techniques are used to implement memoization.

← Older revision		Revision as of 21:45, 18 March 2011
Line 1:		Line 1:
		+	{{Distinguish\|Longest common substring}}
		+
	The '''longest common subsequence''' (LCS) problem is the problem of finding a sequence of maximal length that is a [[subsequence]] of two finite input sequences. Formally, given two sequences <math>x = [x_1, x_2, ..., x_m]</math> and <math>y = [y_1, y_2, ..., y_n]</math>, we would like to find two sets of indices <math>i_1 < i_2 < ... < i_k</math> and <math>j_1 < j_2 < ... < j_k</math> such that <math>x_{i_p} = y_{j_p}</math> for all <math>1 \leq p \leq k</math> and <math>k</math> is maximized.		The '''longest common subsequence''' (LCS) problem is the problem of finding a sequence of maximal length that is a [[subsequence]] of two finite input sequences. Formally, given two sequences <math>x = [x_1, x_2, ..., x_m]</math> and <math>y = [y_1, y_2, ..., y_n]</math>, we would like to find two sets of indices <math>i_1 < i_2 < ... < i_k</math> and <math>j_1 < j_2 < ... < j_k</math> such that <math>x_{i_p} = y_{j_p}</math> for all <math>1 \leq p \leq k</math> and <math>k</math> is maximized.

@@ Line 128: / Line 128: @@
 * The [[Levenshtein distance|edit distance]] between two strings is given by the sum of the lengths of the strings minus twice the length of the longest common subsequence.
 * To find a shortest common supersequence of two sequences, start with a longest common subsequence, and then insert the remaining elements in their appropriate positions. For example, [9,'''2''',3,'''6''','''1'''] and ['''2''',0,'''6''','''1''',3] give initially [2,6,1]. We know the 9 precedes the 2, the 3 and the 0 lie in between the 2 and the 6, and the 3 follows the 1, so we construct [9,2,3,0,6,1,3] as a possible shortest common supersequence. (The order of the 3 and 0 is irrelevant in this example; [9,2,0,3,6,1,3] works just as well.)
 ==References==

@@ Line 122: / Line 122: @@
 ==Faster methods==
 The dynamic algorithm presented above always takes the same amount of time to run (to within a constant factor) and it does not depend on the size of the set from which the elements of the sequences are taken. Faster algorithms exist for cases where this set is small and finite (making the sequences strings over a relatively small alphabet), one of the strings is much longer than the other, or the two strings are very similar.<ref name="BHR00">L. Bergroth and H. Hakonen and T. Raita (2000). "A Survey of Longest Common Subsequence Algorithms". ''SPIRE'' (IEEE Computer Society) '''00''': 39–48. doi:[http://dx.doi.org/10.1109%2FSPIRE.2000.878178 10.1109/SPIRE.2000.878178]. ISBN 0-7695-0746-8.</ref> These algorithms almost always outperform the naive algorithm in practice (otherwise the <code>diff</code> utility would be unacceptably slow). However, it is surprisingly difficult to improve over the <math>O(mn)</math> bound of this algorithm in the general case.
 ==References==

@@ Line 140: / Line 140: @@
      border-style: solid;
      border-width: 1px;
+   }
    .lcs_table td
@@ Line 145: / Line 148: @@
      border-style: solid;
      border-width: 1px;
+   }
 }}

← Older revision		Revision as of 21:06, 2 March 2011
Line 146:		Line 146:
	border-width: 1px;		border-width: 1px;
	}		}
		+	}}

@@ Line 124: / Line 124: @@
 ==References==
-{{reflist}}
+<references/>
 [[Category:Dynamic programming]]