[Haskell-cafe] diff implementation in haskell
dons at galois.com
Mon Dec 7 03:14:00 EST 2009
> Don Stewart <dons at galois.com> writes:
> >> Are there pure haskell implementations of diff and diff3 algorithms?
> > http://hackage.haskell.org/package/Diff
> Wherein we can read:
> | This is an implementation of the O(ND) diff algorithm [...]. It is O(mn)
> | in space.
> At first I thought 'N' and 'M' would be the lengths of the lists, and
> 'D' is the number of differences, but then the space bound doesn't make
> sense. I tried to find the reference, but Citeseer is down
> (again. sigh).
> Anybody know what the bounds really are?
This looks like the paper, http://www.xmailserver.org/diff2.pdf
Page 2, "The algorithm can be refined to use linear space", N and M
appear to be the length of the sequences, D is the size of the minimum
More information about the Haskell-Cafe