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

Subject: Re: [boost] [algorithm] Review Request: edit_distance
From: Erik Erlandson (eje_at_[hidden])
Date: 2014-01-30 15:44:44

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

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

Assuming I'm reading this paper correctly, their O(NP) improvement is essentially a tweak to the previous O(ND) algorithm, that examines a narrower band of path-heads on each iteration combined with a clever re-parameterization of the distance to D = delta+2*P.  The semantics of the working vector looks unchanged aside from its required width.  If so, it may be a fairly simple modification of the existing code to get this working.

Either way, their implied performance is uniformly better than the original O(ND) variation, so getting an implementation working eventually is definitely on my to-do list.