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
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
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?