Algorithm
Article
Library
Snippet
Blog
Group
Users
Forum
Browse
›
Articles
›
'A' Longest Common Subsequence (LCS) implementation
›
History
›
Revision 21 vs. Revision 22
Don't get spied on – We respect your privacy and provide numerous options to protect it.
Join Siafoo Now
or
Learn More
'A' Longest Common Subsequence (LCS) implementation
Revision 21 vs. Revision 22
Legend:
- Unmodified
- Added
- Removed
-
Content
r21 r22 62 62 63 63 The algorithm I came up with is implemented in :snippet:`379`. 64 64 65 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 version and it still will cost more comparisons than the ideal LCS algorithm. 66 66 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```.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`. 68 68 69 69 A 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 70 71 71 Now, 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 72 73 73 If 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 74 75 75 This 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 76 77 My version leads to a recursive solution like ``:snippet:`381```.77 My version leads to a recursive solution like :snippet:`381`. 78 78 79 79 80 80 Chapter 2 Implementation 81 81 ------------------------ 82 82 83 83 I 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. 84 84 85 85 Section 2.1 C version for char* 86 86 ******************************* 87 87 88 The 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.88 The 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. 89 89 90 90 Section 2.2 C++ version (first try) 91 91 *********************************** 92 92 93 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. The code is here ``:snippet:`375``` and test/example code is here ``:snippet:`382```.93 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. The code is here :snippet:`375` and test/example code is here :snippet:`382`. 94 94 95 95 Chapter 3 What else? 96 96 --------------------- 97 97 98 98 At this point comes the meat of my problem. I want to compare two graphs. I've not read any literature about that (yet) but am considering the following way of doing things. At each node in the graph there are edges from that node to the nodes below. What makes a node in one graph equal to a node in the other graph? The edges must match and the nodes they point to must match.