Re: [boost] RFC: edit_distance / edit_alignment library

Subject: Re: [boost] RFC: edit_distance / edit_alignment library
From: Phil Endecott (spam_from_boost_dev_at_[hidden])
Date: 2013-06-30 08:19:30

Hi Erik,

Erik Erlandson wrote:
> Boost Community,
>
> I cooked up a library that provides a pair of functions: edit_distance() 
> and edit_alignment().  The library currently lives here:
> https://github.com/erikerlandson/edit_distance

I have had a quick look.  It seems that you've implemented the Needleman-Wunsch
algorithm, which takes quadratic time and space.  There are less 
complex algorithms,
at least for similar input sequences, e.g. Myers - "An O(ND) Difference Algorithm
and Its Variations"; I have an implementation of that here:
http://svn.chezphil.org/anyterm/trunk/src/diff.cc & .hh.

What is your motivation for choosing Needleman-Wunsch?

Regards,  Phil.