Boost logo

Boost :

From: JD (jean.daniel.michaud_at_[hidden])
Date: 2007-05-15 08:22:14


> JD wrote:
>> I would like to know if there is any interest in an implementation of
>> the edit distance algorithm
> I have an implementation of the "diff" (i.e. edit script) algorithm here:
> The "edit distance" is in there somewhere.
> I would welcome this sort of thing in Boost. But it needs to be the
> best-known algorithm. IIRC, there was one improvement that I found in
> the literature but didn't implement because I didn't fully understand it.
> Please correct me if I'm wrong, but I get the impression that your code
> is O(NM) where N and M are the sizes of the two input strings. The
> algorithm that I implemented is O((N+M)D) where D is the edit distance
> in the worst case, and typically O(N+M+D^2). The algorithm is
> described in the .cc file linked above. Also, your code seems to have
> O(NM) space requirement; I'm not sure what the lower bound is, but I
> think it's probably O(N+M).

I improved the algorithm and now the space requirements falls to O(m).
Computational is still the same, however. Having a very quick look at
your algo (in I can see it's more complex in a way that it is
not understandable at first read. As I can see in the Boost Guideline

"Aim first for clarity and correctness; optimization should be only a
secondary concern in most Boost libraries."

So I think unless there is an obvious way to reduce computational cost
to O(m) (the same way it was obvious to reduce space usage to the same),
I think we should stick to the original algorithm.

Thanks for your insights and further remarks,


   Did you have time to take a look? If not, I've just uploaded the new
version to the Vault here (

Thanks for your remarks,


Boost list run by bdawes at, gregod at, cpdaniel at, john at