From: haskell-cafe-bounces@haskell.org [mailto:haskell-cafe-bounces@haskell.org] On Behalf Of
Mark.Carroll@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. *****************************************************************