pythonrdistance-metrics

Distance Metrics

Ben Gorman

Ben Gorman

Life's a garden. Dig it.

Skip to the problems ->

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).

Example

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

transformations
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.