Levenshtein

The modules in this package export functions which measure the so called edit distance (also called Levenshtein distance) between two strings, a source and a target. The edit distance is defined as the number of deletions, insertions, or substitutions required to transform the source into the target. The greater the distance, the more different the strings are, and vice versa. Edit distance can be (and has been) used for spell checking and speech recognition purposes.

The distribution contains two functionally equivalent implementations, one in C linked into Oz, and one in pure Oz. They are both straightforward implementations of Levenshtein's algorithm - a dynamic programming algorithm capable of calculating the edit distance in time proportional to the length of the source times the length of the target. The C-based version is roughly eight times faster than the pure Oz version, and is therefore recommended for serious use.