From: Greg Colvin (gcolvin_at_[hidden])
Date: 2001-10-27 09:39:31
From: Beman Dawes <bdawes_at_[hidden]>
> 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.
> >> 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
> >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.
V.I. Levenshtein. Binary codes cabable of correcting, deletions,
insertions, and reversals. Soviet Phys. Dokl. 10:707-710, 1966
This is now called "edit distance", and is but one of a number of
approaches. A good review can be found at the most excellent
NEC ResearchIndex site:
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk