Re: Levenshtein Distance algorithm

From: Craig Henderson (yg-boost-users_at_[hidden])
Date: 2002-09-18 14:39:28

Hi Philippe,
On the Boost Developer's list, I am currently proposing an implementation
for the Longest Common Subsequence algorithm. My implementation calculates
the elements removed from the first (deletions), added to the second
(insertions) and remain unchanged (member of the subsequence). It seems that
this is very similar to your suggestion. I am not familiar with the
Levenshtein distance algorithm, but suspect it would be possible to
integrate this into my library.

A first public release of my LCS library is available at
http://freespace.virgin.net/cdm.henderson/boost/lcs.zip, although beware
that it is work-in-progress and I have already made several changes,
including bug fixes.

I would welcome your input and perhaps we can work together? Check out the
Boost Developer's list for conversations that have already taken place.

Regards,
Craig

"Philippe Lalande" <plalande-yahoo_at_[hidden]> wrote in message
news:20020918152755.GS18030_at_born2play.org...
> Hi,
>
> I was wondering if anyone could tell me if Boost contains a function
> that could perform a 'Levenshtein distance' calculation on a sequence.
> The Levenshtein distance is a measure of the similarity between two
> strings calculated as the number of deletions, insertions, or
> substitutions required to transforms the source string to the target
> string. IMO, it is an interesting algorithm that could apply to any kind
> of sequence.
>
> I'd be happy to discuss interface and implementation on the dev list if
> such algorithm does not exist yet.
>
> Thank you
> Philippe
>