Computing Levenshtein Distance
A straightforward implementation, as pseudocode for a function LevenshteinDistance that takes two strings, s and t, and returns the Levenshtein distance between them:
int LevenshteinDistance(string s, string t) { int len_s = length(s), len_t = length(t), cost = 0 if(s != t) then cost = 1 if(len_s == 0) then return len_t elseif(len_t == 0) then return len_s else return minimum(LevenshteinDistance(s, t) + 1, LevenshteinDistance(s, t) + 1, LevenshteinDistance(s, t) + cost) }Implemented as-is in a programming language with eager evaluation, this version would need memoization to avoid computing distances multiple times.
Here is a version with memoization.
//i is the start index of str1, j is the start index of str2 function LevenshteinDistance(str1, i, len1, str2, j, len2) { var key = .join(','); if(memo != undefined) return memo; if(len1 == 0) return len2; if(len2 == 0) return len1; var cost = 0; if(str1 != str2) cost = 1; var dist = Math.min( LevenshteinDistance(str1, i+1,len1-1, str2,j,len2)+1, LevenshteinDistance(str1,i,len1,j+1,len2-1)+1, LevenshteinDistance(str1,i+1,len1-1,str2,j+1,len2-1)+cost); memo = dist; return dist; }Read more about this topic: Levenshtein Distance
Famous quotes containing the word distance:
“Her personality had an architectonic quality; I think of her when I see some of the great London railway termini, especially St. Pancras, with its soot and turrets, and she overshadowed her own daughters, whom she did not understand—my mother, who liked things to be nice; my dotty aunt. But my mother had not the strength to put even some physical distance between them, let alone keep the old monster at emotional arm’s length.”
—Angela Carter (1940–1992)