Re: [boost] RFC: edit_distance / edit_alignment library

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.