How is levenshtein distance calculated?

Decoding Levenshtein Distance: Or, How to Tell if “Kitten” is Basically “Sitting”

Ever wondered how computers figure out if two words are kinda, sorta the same? Or how spellcheck knows you meant “embarrassed” even when you type “embaressed?” The secret sauce is often something called the Levenshtein distance. It’s a way of measuring how different two strings of text are, and it’s surprisingly useful in all sorts of places.

So, what is Levenshtein distance? Simply put, it’s the minimum number of single-character changes you need to make to turn one string into another. Think of it like this: how many steps does it take to morph “kitten” into “sitting?” You’re allowed to insert letters, delete them, or swap them out.

Let’s break it down. To get from “kitten” to “sitting,” you’d:

That’s three changes. So, the Levenshtein distance between “kitten” and “sitting” is 3. The smaller the distance, the more alike the words are. Zero means they’re identical twins!

Okay, But How Do You Actually Calculate It?

This is where it gets a little geeky, but stick with me. The most common way to calculate Levenshtein distance is with something called dynamic programming. Basically, we build a grid (or matrix, if you want to sound fancy) and fill it in step-by-step.

Imagine a spreadsheet. Across the top, you write out one word, and down the side, you write the other. The numbers in the spreadsheet tell you the Levenshtein distance between the prefixes of the two words.

Here’s the gist:

Let’s picture that “ke” and “h” example again:

h01k11e22