Boost logo

Boost :

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:

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: & .hh.

What is your motivation for choosing Needleman-Wunsch?

Regards, Phil.

Boost list run by bdawes at, gregod at, cpdaniel at, john at