Levenshtein Distance - Computing Levenshtein Distance

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; }