Boost logo

Boost :

From: Beman Dawes (bdawes_at_[hidden])
Date: 2001-10-27 19:33:28


At 10:47 AM 10/26/01 +0400, Vladimir Prus wrote:
>
>
>David Brownell wrote:
>
>> I am in the process of writing an algorithm that, when given two
>> sequences of objects, will compare the differences and, if requested,
>> output a set of instructions on how to convert sequence #1 to
>> sequence #2.
>
>[snip]
>
>> The most common applications of this algorithm could be file
>> comparisons or some sort of file versioning system similar to CVS or
>> SourceSafe, but could even work on more complicated sequences such as
>> DNA or even a seating chart.
>>
>> Is there any interest in this algorithm?
>
>I'm interested. Yet, I'll be even more interested if you don't just
present
>some algorithm which does the task, but also present a comparison of all
>possible approaches.

IIRC, the algorithm is called a Levenstein (or possibly Levenshein)
Match. It was written up some years ago in ACM Computing Surveys in an
article on approximate string matching. I can dig out the reference if
anyone cares.

--Beman


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk