[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Monotone-devel] lcs mystery
From: |
Markus Schiltknecht |
Subject: |
[Monotone-devel] lcs mystery |
Date: |
Sun, 19 Aug 2007 17:32:11 +0200 |
User-agent: |
Icedove 1.5.0.12 (X11/20070607) |
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
- [Monotone-devel] lcs mystery,
Markus Schiltknecht <=