ketil: > Don Stewart <[email protected]> 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 edit script. -- Don _______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
