Re: [boost] Algo. Proposal: SequenceCompare

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