[Haskell-cafe] diff implementation in haskell

[Bayley, Alistair]

> From: haskell-cafe-bounces at haskell.org 
> [mailto:haskell-cafe-bounces at haskell.org] On Behalf Of Ketil Malde
> 
> Don Stewart <dons at galois.com> writes:
> 
> 
> >     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?


I think the space bounds are O(M+N). Section "4b. A Linear Space
Refinement" concludes with "Unfortunately, the input sequences A and B
must be kept in memory, implying that a total of O(M+N) space is
needed."

BTW, there is a minor improvement to this algorithm (claims to be
faster, same space usage):
  http://research.janelia.org/myers/Papers/np_diff.pdf

found via:
 
http://scholar.google.com/scholar?q=%22An+O(NP)+Sequence+Comparison+Algo
rithm.%22

I thought this paper was easier to understand.

Alistair
*****************************************************************
Confidentiality Note: The information contained in this message,
and any attachments, may contain confidential and/or privileged
material. It is intended solely for the person(s) or entity to
which it is addressed. Any review, retransmission, dissemination,
or taking of any action in reliance upon this information by
persons or entities other than the intended recipient(s) is
prohibited. If you received this in error, please contact the
sender and delete the material from any computer.
*****************************************************************