[Monotone-devel] lcs mystery

[Markus Schiltknecht]

Hello Graydon,

I just had another look at the merge bug I've tracked down at the summit 
(test_a_merge_8). I've taken a look at the debugging output and added 
some more of that. Unfortunately, that stuff doesn't tell me much, as I 
don't have no understanding of the algorithm used.

Peeking at the source (lcs.cc) revealed that you did a reimplementation 
of an algorithm by Aubrey Jaffer, which is said to "perform quite a bit 
better than myers, manber and miller's O(NP)" algorithm. Looking at the 
original Scheme source code from Aubrey Jaffer [1], he states that he 
implements the algorithm by 'S. Wu, E. Myers, U. Manber, and W. Miller, 
"An O(NP) Sequence Comparison Algorithm,"'. So, what algorithm do we 
use? Does another (Jaffer's) algorithm exist or is that just a small 
modification of the former?

To make things even worse, all the links to papers cited in differ.scm 
are not valid anymore ([2] and [3]). And google didn't turn up anything 
useful either.

Can you shed some light on this mystery, please?

Regards

Markus

[1]: SLIB on savannah, CVS Repository, file differ.scm:
http://cvs.savannah.gnu.org/viewvc/slib/differ.scm?revision=1.84&root=slib&view=markup

[2]: S. Wu, E. Myers, U. Manber, and W. Miller
"An O(NP) Sequence Comparison Algorithm,"
Information Processing Letters 35, 6 (1990), 317-323.
DEPRECATED URL: http://www.cs.arizona.edu/people/gene/PAPERS/np_diff.ps

[3]: E. Myers and W. Miller,
"Optimal alignments in linear space",
Computer Application in the Biosciences (CABIOS), 4(1):11-17, 1988.
DEPRECATED URL: http://www.cs.arizona.edu/people/gene/PAPERS/linear.ps