Levenshtein Distance and the Triangle Inequality « Inviting Epiphany
The first and most important thing about Levenshtein distance is it’s actually a metric distance. That is, it obeys the triangle inequality. For most other string distance measurements this property doesn’t hold.