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

----- 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/a... 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.