RE: [boost] Algo. Proposal: SequenceCompare

From: Beman Dawes (bdawes_at_[hidden])
Date: 2001-10-30 20:21:26

-----Original Message-----
From: Greg Colvin [mailto:gcolvin_at_[hidden]]
Sent: Saturday, October 27, 2001 7:40 AM
To: boost_at_[hidden]
Subject: Re: [boost] Algo. Proposal: SequenceCompare

 > 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

Yep, that's the original reference to Levenshtein's work.  The ACM 
Computing Surveys article was "Approximate String Matching", Vol 12, No. 4, 
December, 1980.

Available online at:
http://portal.acm.org/citation.cfm?id=356830&coll=portal&dl=ACM&CFID=466708&CFTOKEN=31729535 
Note the citings section lists more modern papers.

--Beman