Edit Distance

A customer types hary poter into the Bright Books search bar. To a computer, those are simply different strings, with no match at all. A person would know exactly what they meant. To close that gap, we need a way of measuring how far apart two words are.

• A customer types 'hary poter'
• To a computer, no match
• Measure how far apart words are

Levenshtein distance

Edit distance counts the smallest number of single letter changes to turn one word into another. Add a letter, delete a letter, or swap one. The clever part is this table of partial answers, built up row by row. Each cell looks at its three neighbours, and takes the cheapest option. That technique is called dynamic programming. Run it. Kitten to sitting takes three edits. Hary poter is just two away from harry potter. And refund to itself is zero. In about seven lines, we've measured similarity between strings. Spell checkers, DNA alignment, and fraud detection all use this exact idea.

def distance(a, b):
    row = list(range(len(b) + 1))
    for i, ca in enumerate(a, 1):
        new = [i]
        for j, cb in enumerate(b, 1):
            new.append(min(row[j] + 1, new[j - 1] + 1, row[j - 1] + (ca != cb)))
        row = new
    return row[-1]

print(distance("kitten", "sitting"))
print(distance("harry potter", "hary poter"))
print(distance("refund", "refund"))

3
2
0

Where edit distance is used

You'll find this everywhere. Matching names across two databases, where one has Jon, and the other has John. Cleaning up product names. Comparing genetic sequences. And checking speech recognition, as word error rate is simply edit distance over words. Its weakness is that it only sees letters, so car and automobile look completely different.

Summary