Re: [boost] [algorithm] Review Request: edit_distance

Subject: Re: [boost] [algorithm] Review Request: edit_distance
From: Erik Erlandson (eje_at_[hidden])
Date: 2014-02-21 23:22:22

----- Original Message -----
> > > - Have you looked at the supposedly better algorithm "An O(NP)
> > > Sequence Comparison Algorithm" by Sun Wu, Udi Manber, and Gene
> > > Myers ?

> 
> I've been doing more cross-testing and benchmarking against the current O(ND)
> version.   The latest O(NP) prototype is passing randomized cross-testing
> and is now about 25% faster than the O(ND) baseline.
> 

I wrote up a blog post that describes the various ideas I applied to get this result:

http://erikerlandson.github.io/blog/2014/02/20/a-bi-directional-variation-of-the-o-np-edit-distance-algorithm/