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

Subject: Re: [boost] [algorithm] Review Request: edit_distance
From: Erik Erlandson (eje_at_[hidden])
Date: 2014-02-15 15:47:57

----- Original Message -----

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

So, I've been fooling around with this O(NP) variation.  It took a few weeks of head scratching, but I think I have worked out how to properly do the bi-directional variation:

https://github.com/erikerlandson/algorithm/blob/order_np_alg/include/boost/algorithm/sequence/detail/edit_distance.hpp#L343

As you can see, the code is all up on blocks, but you can get the flavor of how it works.   More work remaining to do, with additional testing, plugging the fallback logic back in, porting it over to the version that extracts edit scripts, benchmarking, etc.   But looks promising.