Ben Gorman

Ben Gorman

Life's a garden. Dig it.

Levenshtein distance

Given two strings A and B Levenshtein distance mesaures the minimum number of character replacements + insertions + deletions to transform A into B (or equivalently, B into A).


lev ⁡ ( "raccoon" , "baboon" ) = 3 \operatorname {lev} (\text{"raccoon"}, \text{"baboon"}) = 3 lev("raccoon","baboon")=3

raccoon -> baccoon 
baccoon -> babcoon 
babcoon -> baboon  

This example shows that "raccoon" can be transformed into "baboon" with three edits. It does not prove that three edits is the minimum necessary to get the job done.

For details on how Levenshtein distance is calculated, see the Wikipedia article.