10. Levenshtein Distance

By Bernd Klein. Last modified: 01 Feb 2022.

On this page ➤

Introduction

This chapter covers the Levenshtein distance and presents some Python implementations for this measure. There are lots of use cases for the Levenshtein distances. The Levenshtein Distance and the underlying ideas are widely used in areas like computer science, computer linguistics, and even bioinformatics, molecular biology, DNA analysis. You can even measure the similarity of melodies or rhythms in music¹. The Levenshtein distance has widely permeated our everyday life. Whenever you use a program or an application using some form of spell checking and error correction, the programmers most likely will have used "edit distance" or as it is also called "Levenshtein distance".

Levenshtein Distance

You might already have encountered another possible use case for this concept: Imagine that you are using a Python dictionary, in which you use strings as keys.

Let us look at the following example dictionary with city names of the United States, which are often misspelled:

cities = {"Pittsburgh":"Pennsylvania",
          "Tucson":"Arizona",
          "Cincinnati":"Ohio",
          "Albuquerque":"New Mexico",
          "Culpeper":"Virginia",
          "Asheville":"North Carolina",
          "Worcester":"Massachusetts",
          "Manhattan":"New York",
          "Phoenix":"Arizona",
          "Niagara Falls":"New York"}

So, trying to get the corresponding state names via the following dictionary accesses will raise exceptions:

cities["Tuscon"] cities["Pittsburg"] cities["Cincinati"] cities["Albequerque"]

If a human reader looks at these misspellings, he or she will have no problem in recognizing the city you have in mind. The Python dictionary on the other hand is pedantic and unforgivable. It only accepts a key, if it is exactly identical.

The question is to what degree are two strings similar? What we need is a string similarity metric or a measure for the "distance" of strings.

A string metric is a metric that measures the distance between two text strings. One of the best known string metrics is the so-called Levenshtein Distance, also known as Edit Distance. Levenshtein calculates the the number of substitutions and deletions needed in order to transform one string into another one.

Live Python training

Enjoying this page? We offer live Python training courses covering the content of this site.

See our Python training courses

See our Machine Learning with Python training courses

The Minimum Edit Distance or Levenshtein Dinstance

The minimum edit distance between two strings is the minimum numer of editing operations needed to convert one string into another. The editing operations can consist of insertions, deletions and substitutions.

The simplest sets of edit operations can be defined as:

Insertion of a single symbol. This means that we add a character to a string s. Example: If we have the string s = "Manhatan", we can insert the character "t" to get the correct spelling:
```
>>> s = "Manhatan"
>>> s = s[:5] + "t" + s[5:]
>>> print(s)
Manhattan
```

Deletion of a single symbol Example:

>>> s = "Mannhattan"
>>> s = s[:2] + s[3:]
>>> s
'Manhattan'

Substitution of a single symbol In the following example, we have to change the letter "o" into the letter "a" to get the correct spelling:
```
>>> s = "Manhatton"
>>> s = s[:7] + "a" + s[8:]
>>> s
'Manhattan'
```

The minimum edit distance between the two strings "Mannhaton" and "Manhattan" corresponds to the value 3, as we need three basic editing operation to transform the first one into the second one:

>>> s = "Mannhaton"
>>> s = s[:2] + s[3:]         # deletion
>>> s
'Manhaton'
>>> s = s[:5] + "t" + s[5:]   # insertion
>>> s
'Manhatton'
>>> s = s[:7] + "a" + s[8:]   # substitution
>>> s
'Manhattan'

We can assign assign a weight or costs to each of these edit operations, e.g. setting each of them to 1. It is also possible to argue that substitutions should be more expensive than insertations or deletions, so sometimes the costs for substitutions are set to 2.

Mathematical Definition of the Levenshtein Distance

The Levenshtein distance between two strings a and b is given by lev_a,b(len(a), len(b)) where lev_a,b(i, j) is equal to

max(i, j) if min(i, j)=0

otherwise:

min(lev_a,b(i-1, j) + 1,
    lev_a,b(i, j-1) + 1,
    lev_a,b(i-1, j-1) + 1_{a_i≠b_j})

where 1_{a_i≠b_j} is the indicator function equal to 0 when a_i=b_j and equal to 1 otherwise, and lev_a,b(i, j) is the distance between the first i characters of a and the first j characters of b.

The Levenshtein distance has the following properties:

It is zero if and only if the strings are equal.
It is at least the difference of the sizes of the two strings.
It is at most the length of the longer string.
Triangle inequality: The Levenshtein distance between two strings is no greater than the sum of their Levenshtein distances from a third string.

Live Python training

Enjoying this page? We offer live Python training courses covering the content of this site.

Upcoming online Courses

Python Course for Beginners

Python Intensive Course

Data Analysis with Python

Efficient Data Analysis with Pandas

See our Python training courses

See our Machine Learning with Python training courses

Recursive Levenshtein Function in Python

The following Python function implements the Levenshtein distance in a recursive way:

def LD(s, t):
    if s == "":
        return len(t)
    if t == "":
        return len(s)
    if s[-1] == t[-1]:
        cost = 0
    else:
        cost = 1
       
    res = min([LD(s[:-1], t)+1,
               LD(s, t[:-1])+1, 
               LD(s[:-1], t[:-1]) + cost])

    return res

print(LD("Python", "Peithen"))

OUTPUT:

This recursive implementation is very inefficient because it recomputes the Levenshtein distance of the same substrings over and over again. We count the number of calls in the following version by using a decorator function. If you don't know them, you can learn about them in our chapter on Memoization and Decorators:

from collections import Counter

def call_counter(func):
    def helper(*args, **kwargs):
        helper.calls += 1
        key = str(args) + str(kwargs)
        helper.c[key] += 1
        return func(*args, **kwargs)
    helper.c = Counter()
    helper.calls = 0
    helper.__name__= func.__name__

    return helper

@call_counter
def LD(s, t):
    if s == "":
        return len(t)
    if t == "":
        return len(s)
    if s[-1] == t[-1]:
        cost = 0
    else:
        cost = 1
       
    res = min([LD(s[:-1], t)+1,
               LD(s, t[:-1])+1, 
               LD(s[:-1], t[:-1]) + cost])

    return res

print(LD("Python", "Peithen"))

print("LD was called " + str(LD.calls) + " times!")
print(LD.c.most_common())

OUTPUT:

3
LD was called 29737 times!
[("('', 'P'){}", 5336), ("('P', ''){}", 4942), ("('', ''){}", 3653), ("('P', 'P'){}", 3653), ("('', 'Pe'){}", 2364), ("('P', 'Pe'){}", 1683), ("('Py', ''){}", 1666), ("('Py', 'P'){}", 1289), ("('', 'Pei'){}", 912), ("('Py', 'Pe'){}", 681), ("('P', 'Pei'){}", 681), ("('Pyt', ''){}", 462), ("('Pyt', 'P'){}", 377), ("('Py', 'Pei'){}", 321), ("('', 'Peit'){}", 292), ("('Pyt', 'Pe'){}", 231), ("('P', 'Peit'){}", 231), ("('Py', 'Peit'){}", 129), ("('Pyt', 'Pei'){}", 129), ("('Pyth', ''){}", 98), ("('Pyth', 'P'){}", 85), ("('', 'Peith'){}", 72), ("('Pyt', 'Peit'){}", 63), ("('Pyth', 'Pe'){}", 61), ("('P', 'Peith'){}", 61), ("('Py', 'Peith'){}", 41), ("('Pyth', 'Pei'){}", 41), ("('Pyth', 'Peit'){}", 25), ("('Pyt', 'Peith'){}", 25), ("('Pytho', ''){}", 14), ("('Pyth', 'Peith'){}", 13), ("('Pytho', 'P'){}", 13), ("('', 'Peithe'){}", 12), ("('Pytho', 'Pe'){}", 11), ("('P', 'Peithe'){}", 11), ("('Py', 'Peithe'){}", 9), ("('Pytho', 'Pei'){}", 9), ("('Pyt', 'Peithe'){}", 7), ("('Pytho', 'Peit'){}", 7), ("('Pyth', 'Peithe'){}", 5), ("('Pytho', 'Peith'){}", 5), ("('Pytho', 'Peithe'){}", 3), ("('Python', 'Pei'){}", 1), ("('Python', 'Peithe'){}", 1), ("('', 'Peithen'){}", 1), ("('P', 'Peithen'){}", 1), ("('Pytho', 'Peithen'){}", 1), ("('Py', 'Peithen'){}", 1), ("('Python', 'P'){}", 1), ("('Python', 'Peit'){}", 1), ("('Pyt', 'Peithen'){}", 1), ("('Pyth', 'Peithen'){}", 1), ("('Python', 'Peith'){}", 1), ("('Python', ''){}", 1), ("('Python', 'Pe'){}", 1), ("('Python', 'Peithen'){}", 1)]

We can see that this recursive function is highly inefficient. The Levenshtein distance of the string s="" and t="P" was calculated 5336 times. In the following version we add some "memory" to our recursive Levenshtein function by adding a dictionary memo:

def call_counter(func):
    def helper(*args, **kwargs):
        helper.calls += 1
        return func(*args, **kwargs)
    helper.calls = 0
    helper.__name__= func.__name__

    return helper


memo = {}
@call_counter
def levenshtein(s, t):
    if s == "":
        return len(t)
    if t == "":
        return len(s)
    cost = 0 if s[-1] == t[-1] else 1
       
    i1 = (s[:-1], t)
    if not i1 in memo:
        memo[i1] = levenshtein(*i1)
    i2 = (s, t[:-1])
    if not i2 in memo:
        memo[i2] = levenshtein(*i2)
    i3 = (s[:-1], t[:-1])
    if not i3 in memo:
        memo[i3] = levenshtein(*i3)
    res = min([