Next: , Previous: , Up: Top   [Index]

30 Levenshtein distance metric

The library (vicare containers levenshtein) is a Scheme implementation of the Levenshtein Distance algorithm, which is an edit distance metric of string similarity, due to Vladimir Levenshtein. The Levenshtein Distance is a function of two strings that represents a count of single–character insertions, deletions, and substitions that will change the first string to the second. More information is available in NIST DADS and the Michael Gilleland article, “Levenshtein Distance in Three Flavors.”

This implementation is modeled after a space–efficient Perl implementation by Jorge Mas Trullenque. It has been written in Scheme by Neil Van Dyke, and extended to support heterogeneous combinations of Scheme types (strings, lists, vectors), user–supplied predicate functions, and optionally reusable scratch vectors.