[Haskell-cafe] Re: Memoizing longest-common-subsequence

[Bayley, Alistair]

> From: haskell-cafe-bounces at haskell.org 
> [mailto:haskell-cafe-bounces at haskell.org] On Behalf Of 
> 
> Mark.Carroll at Aetion.com (Mark T.B. Carroll) writes:
> 
> > I wanted a longest common subsequence function and a bit of Googling
> > failed to turn up a functional one, except for in a scary 
> bit of darcs.
> 
> The code in darcs is a translation of the example code in the 
> Eugene Myers
> paper mentioned in the comments and the C code in GNU diff. I 
> didn't try
> much to simplify it because I first wanted to see how close I 
> could come
> to the perfomance of the C code. 
> 
> [..]
> 
> > Take this as your cue to point out the much better LCS 
> algorithm that
> > already exists in the standard libraries, that I couldn't find. (-:
> 
> There is a nice implementation of the Hunt-Szymanski algorithm by
> Ian Lynagh at http://urchin.earth.li/darcs/ian/lcs/.
> 
> Benedikt


I also had a go at this a while ago, using this Eugene Myers' paper as
the specification:
  http://www.cs.arizona.edu/~gene/PAPERS/np_diff.ps

which claims improvement over the one you mention above:
  http://www.cs.arizona.edu/~gene/PAPERS/diff.ps

and also ended up with an STArray based implementation. I can send the
code if you're interested. I have no idea how well it performs compared
to Ian's, or the one in darcs (which uses PackedStrings).

There's some kind of summary/comparison of LCS algorithms (including
Hunt-Szymanski) here:
  http://www-math.mit.edu/~lippert/18.417/papers/mye:1991.pdf

also by Eugene Myers.

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.
*****************************************************************