Re: [boost] RFC: edit_distance / edit_alignment library

Subject: Re: [boost] RFC: edit_distance / edit_alignment library
From: Rene Rivera (grafikrobot_at_[hidden])
Date: 2013-06-30 21:14:38

On Sunday, June 30, 2013, Erik Erlandson wrote:

>
> > 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?
>
>
> It was the simplest algorithm to get going.  I was interested in
> developing a nice boost-ish programmatic interface, and developing unit
> tests, so for the implementation I stuck with the easy algorithm that I was
> familiar with.   Now I (or anybody else) can drop in better algorithms with
> some unit test assurance.
>
> Plus, Needleman-Wunsch is pretty effective for applications involving
> relatively small strings or sequences.   Not so much for applications like
> large file diffs, or DNA sequences, etc.
>
> At any rate, I view the particular algorithm as somewhat fungible,
> provided that the interface design is appealing to people.  If there is
> disagreement on that point, I'm interested to know that too.

In the current interface I don't see how one could implement a replacement
algorithm.

-- 
-- 
-- Grafik - Don't Assume Anything
-- Redshift Software, Inc. - http://redshift-software.com
-- rrivera/acm.org - grafik/redshift-software.com
-- 102708583/icq - grafikrobot/aim - grafikrobot/yahoo