Take the 2-minute tour ×

I have an algorithm based on Longest Increasing Subsequence that works very well for solving the relevant business problem when the objects in each collection are unique, but tends to give odd results when there are many non-unique objects present in both collections.

It appears that an approach using the Patience Diff algorithm (which is also based on Longest Increasing Subsequence) would provide the results I want when non-unique objects exist. However, before I can figure out if Patience Diff would be suitable, and in order to apply it to my problem if it's suitable, I need a better understanding of the algorithm.

I understand what happens in steps 1 to 3, but I'm not clear on what happens in step 4. After 1 to 3, now there remains blocks of unique lines that have no possible match, and non-unique lines. So what happens next -- suppose there is no match with the remaining first/last lines of the documents, surely it doesn't terminate already (because there are no more unique lines)? Or does it compare every non-unique block in one document with every non-unique block in the other document and pick the best match somehow?


  1. Match the first lines of both if they're identical, then match the second, third, etc. until a pair doesn't match.
  2. Match the last lines of both if they're identical, then match the next to last, second to last, etc. until a pair doesn't match.
  4. Do steps 1-2 on each section between matched lines
share|improve this question
add comment

1 Answer

up vote 2 down vote accepted

Once you've run out of unique lines you need to fall back to a different alignment algorithm. Git uses the standard diff algorithm at that point (Eugene Myers' O(ND) algorithm).

e.g., if the two files are:

a 12121 e 1212 b ee c x d
a 21212 e 2121 b ye c d

First, the patience algorithm aligns any lines that are unique and exist in both files:

a b c d
a b c d

Each subrange between those lines is then aligned recursively, first doing the patience algorithm again, then doing LCS algorithms if the patience algorithm doesn't match anything.

1212 e 121    |  ee  |    x
2121 e 2      |  ye  |

In the first subrange, e is now unique on both so the second patience diff pass will align it, splitting that into two new subranges. The new first subrange (12121 vs 21212) doesn't have any unique lines, so it will be aligned with the LCS algorithm. The second new subrange (1212 vs 2121) is done with a second pass of the LCS algorithm.

The second grouping above (ee vs ye) doesn't have any unique lines, so they'll be aligned using the LCS algorithm as well.

The final grouping (x vs nothing) just outputs x as a delete, without doing either the patience or LCS algorithms.

share|improve this answer
Based on looking at the source code it seems it's not as simple as running LCS on the entire set of non-unique lines. They group some lines, do some LCS, then go back and do something else and come back to LCS again. Anyway, for the specific problem I'm dealing with, I ended up putting together a heuristic that is much simpler and (probably) more efficient for the specific type of data being handled. –  Gigatron May 27 '12 at 18:02
@Gigatron: You don't run the LCS on all of the non-unique lines at once. Patience Diff will give you the alignment for the unique lines, and then you do LCS on each range of non-unique lines within that alignment. –  Craig Peterson May 27 '12 at 21:44
How does one go about selecting ranges for the LCS runs on non-unique lines? If there are 4 such ranges in document 1, and 5 such ranges in document 2, do I run LCS for each of the 4 against all of the other 5 (thereby 20 LCS runs), and then pick the range-pairs with the longest subsequences? –  Gigatron May 27 '12 at 23:42
@Gigatron: Hard to describe as a comment, so I've updated my answer with an example. –  Craig Peterson May 28 '12 at 3:12
OK, I got it now. Thanks. –  Gigatron May 29 '12 at 13:58
add comment

Your Answer


