Boost logo

Boost :

From: Craig Henderson (cdm.henderson_at_[hidden])
Date: 2002-10-22 02:44:49

"Bohdan" <warever_at_[hidden]> wrote in message
> Thanks for links.
> I don't think that using matrix for string comparison is a good idea.
> Memory for matrix should be allocated dynamically, this doesn't allow
> to implement fast algorithm. Besides all it has O(n*n) speed and doesn't
> well
> for two sequence difference ( parameters: 2 pairs of forward iterators ).

Fear not ! My implementation uses linear memory, not a full matrix like
that described in the article. If you're interested, take a look at the
longest_common_subsequence_length() algorithm in the sand-box at

The fundamental algo is the same, and just the core of the loop changes for
Levenshtein Distance.

> I think that lavenstain difference should be in boost, but it is not
There are always alternatives to every algorithm, often suitable for
different datasets. Sure, we should not just have a single implementation to
try to cover all uses.

> More interesting is some kind algorithm with some limitations and better
> perfomance. I'm not ready for more detailed conversation yet. i'll read
> about various edit-differences when i have more time and i hope to propose
> alternative ways.
> But maybe your implementaion alredy doesn't use dynamic memory and is
O(n) ?
> Than i'm wasting time :)

It's never a waste of time to discuss implementation details of algorithms,
IMO :-)


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