Function distances::strings::levenshtein
source · pub fn levenshtein<U: UInt>(x: &str, y: &str) -> UExpand description
Computes the Levenshtein distance between two strings.
The Levenshtein distance is defined as the minimum number of edits needed to transform one string into the other, with the allowable edit operations being insertion, deletion, or substitution of a single character. It is named after Vladimir Levenshtein, who considered this distance in 1965.
We use the Wagner-Fischer algorithm to compute the Levenshtein distance. The Wagner-Fischer algorithm is a dynamic programming algorithm that computes the edit distance between two strings of characters.
We use penalty values of 1 for all edit operations and we minimize the
total penalty for aligning the two strings.
The input strings are not required to be of the same length.
§Arguments
x: The first string.y: The second string.
§Examples
use distances::strings::levenshtein;
let x = "NAJIBEATSPEPPERS";
let y = "NAJIBPEPPERSEATS";
let distance: u16 = levenshtein(x, y);
assert_eq!(distance, 8);
let x = "TOMEATSWHATFOODEATS";
let y = "FOODEATSWHATTOMEATS";
let distance: u16 = levenshtein(x, y);
assert_eq!(distance, 6);