I am writing a program that computes and displays diffs. I implemented Meyers algorithm that computes the LCS between 2 subsequences (seq1 and seq2); its output is one of the possible LCS and a partition of seq1 and seq2, one projection of which is lcs.

I want to improve it so that the LCS displayed minimizes the number of breaks; to do so, I implemented a function f(lcs, seq):

  • seq is a sequence of characters
  • lcs is a subsequence of seq
  • the output is a partition of seq p0, p1, p2, ... pn such as
    • either p0 + p2 + or p1 + p3 + ... is lcs
    • and n is minimal

I did so using some sort of BFS, at each step finding the next element non-covered in lcs in seq and greedily expanding the common part.

The resulting algorithm is quite slow: on a typical input, ~3x slower that the Myers algorithm which seems to compute something way more complex. See code here: https://github.com/mookid/diffr/blob/c9ed7746193fd9833ddce1237d6e5005e91deaf4/diffr-lib/src/best_projection.rs

Am I missing a better algorithm?

  • $\begingroup$ One way to do this is by using Gotoh's sequence alignment algorithm to compute affine gap costs -- this is where you pay an extra cost for opening a new gap (vs. extending an existing gap). But this takes $\Theta(nm)$ time and memory. Myers's algorithm takes $O(nd)$ time which is quadratic too, but usually $d \ll n$ (or the diff would be unhelpful) so it's much faster, and it can also work with just $O(n)$ memory. This page gives more details. $\endgroup$ – j_random_hacker Nov 26 '19 at 2:17
  • $\begingroup$ BTW, any greedy approach is likely to get stuck. E.g. if seq1 = "RED.APPLEREDAPPLE.R.E.D" and lcs = "REDAPPLERED", an approach that tries to make the longest initial unbroken match will produce "red.appleREDAPPLE.R.E.D" (positions matched to lcs are capitalised) with 3 breaks instead of "RED.APPLEREDapple.r.e.d" with just 1 break. $\endgroup$ – j_random_hacker Nov 26 '19 at 2:26
  • $\begingroup$ thanks for the pointer! I will have a look. Here greediness means that once I match lcs[0] = R with seq1[0], i keep matching E = seq1[1] rather than trying to match E at some later index. $\endgroup$ – mookid Nov 26 '19 at 3:07
  • $\begingroup$ You're welcome :) I believe Myers's algorithm is already greedy in the way you describe -- it always tries to extend "snakes" as far as they can go. $\endgroup$ – j_random_hacker Nov 28 '19 at 1:21
  • $\begingroup$ Another approach that I would recommend (a variant of which is used by the DNA sequence alignment tool MUMmer to great effect) is to look for a maximum-length unique match (MUM) between seq1 and lcs -- that is, the longest substring that appears in both strings exactly once. This can be found in $O(n)$ time and space with a generalised suffix tree. This leaves you with 2 smaller subproblems to solve, one on each "side" of the MUM. Requires some careful programming if you need to implement the suffix tree yourself, but should be fast in practice. $\endgroup$ – j_random_hacker Nov 28 '19 at 1:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.