Close Browse › Articles › 'A' Longest Common Subsequence (LCS) implementation › History › Revision 12 vs. Revision 13

'A' Longest Common Subsequence (LCS) implementation

Revision 12 vs. Revision 13

Legend:

Unmodified
Added
Removed

  • Content

    r12 r13  
    6060  
    6161Then we move to starting at :math:`x_2` and do it all again form :math:`y_1` which immediately match.  We proceed to :math:`x_3` and that also matches :math:`y_2`.  Then to :math:`x_4` which matches :math:`y_4`.     
    6262  
    6363The algorithm I came up with is implemented in ``:snippet:`379```.  
    6464  
    65 Now, to understand the potential cost of this it is clear that we go through Y at least n times (where n is the number of items in X).  So that is O(n*m) (m is the number of items in Y).  However, at each point we do not match, we could potentially rewind multiple times.  Doing a lot of testing with no with sequences like X={A,B,C,D} and Y={D} I saw some extra looping which I stopped with some if statements but these cost time.  In any case, what you see is the final one and it still will cost more comparisons than the next one.  
     65Now, to understand the potential cost of this it is clear that we go through Y at least n times (where n is the number of items in X).  So that is O(n*m) (m is the number of items in Y).  However, at each point we do not match, we could potentially rewind multiple times.  Doing a lot of testing with no with sequences like X={A,B,C,D} and Y={D} I saw some extra looping which I stopped with some if statements but these cost time.  In any case, what you see is the final version and it still will cost more comparisons than the ideal LCS algorithm.  
    6666  
    67 What if we take every subsequence of X and look for it in Y?  Then we have the longest subsequence, X itself, then start knocking off one character at a time and check again.  This truly brute force algorithm is provided in ``:snippet:`380```  
     67What if we take every subsequence of X and look for it in Y?  Then we have the longest subsequence, X itself, then start knocking off one character at a time and check again.  This truly brute force algorithm is provided in ``:snippet:`380```.  
     68  
     69A critical insight into this problem is to realize that it can be broken down into sub-problems.  Let us define a suffix as the first part of a sequence.  For example, above suffixes would be A, AB, ABC, ABCD & etc.   
     70  
     71Now, suppose two sequences start with the same element. Then to find their LCS we need to only compare the remainder.  In other words, if the first item matches then a LCS is the item that matched plus a LCS of X = {:math:`x_2, x_3, .., x_i, .., x_n`} with Y = {:math:`y_2, y_3, .., y_j, .., y_m`}.  
     72  
     73If the first element does not match, then obviously it is not part of an LCS and can be ignored.  But then how do we proceed?  We must check X = {:math:`x_2, x_3, .., x_i, .., x_n`} against the Y = {:math:`y_3, y_4, .., y_j, .., y_m`} and vice-versa to see which comparison yields a longer LCS.  
     74  
     75This solution is analogous to the description in the `Wikipedia`_ reference except that there it is more formally defined and he is removing the last element instead of the first.  
     76  
     77My version leads to a recursive solution like ``:snippet:`381```.  
    6878  
    6979  
    7080Chapter 2 Implementation  
    7181------------------------  
    7282  
    73 The code I implemented uses memoization from the `UCI`_ article and the printDiff method is basically a reverse version of the back-tracking printDiff algorithm of the `Wikipedia`_ article.   
     83I went through a series of implementations for fun and exploration.  The first and most basic was a C version for char* comparisons.  The second was a C++ version which used memoization to keep track of the comparisons.   
    7484  
    7585Section 2.1 C version for char*  
    7686*******************************  
    7787  
    78 First, I just pushed through the implementation.  It probably has bugs.  I've revisited it a few times but basically only to look at it for the NEXT implementation.  It can be found in whole at the snippet ``:snippet:`374```.  
     88The first code I implemented was to demonstrate the memoization algorithm from the `UCI`_ article pretty much as-is (``:snippet:374```). It is implemented in C.  
    7989  
    8090Section 2.2 C++ version (first try)  
    8191***********************************  
    8292  
    83 The next thing I decided to do was think about this in terms of the sequence being any object.  As a result I would need to think more about indices and what it meant to be at the end of a set of objects and the size of the object collection.  That was too much to think about so I decided to make an LCS C++ template class that could be used for c++ containers or at least some containers. I'm still working on it here: ``:snippet:`375```  
     93The next thing I decided to do was think about this in terms of the sequence being any object.  As a result I would need to think more about indices and what it meant to be at the end of a set of objects and the size of the object collection.  That was too much to think about so I decided to make an LCS C++ template class that could be used for c++ containers or at least some containers. The code is here ``:snippet:`375``` and test/example code is here ``:snippet:`382```.  
    8494  
    85 Chapter 3 More to do  
     95  
     96  
     97Chapter 3  What else?  
    8698---------------------