Edit Distance

Edit distance, whose most common form is also known as Levenshtein distance, is a way to measure the difference between two strings of text. It's often used in spell-checkers and fuzzy-search engines.

Given two strings, we want to find the minimum number of edits that it takes to transform one string into the other. An "edit" could be any of the following three operations:

• Insert a character
• Delete a character
• Substitute a character

Let's look at some examples.

# 1 addition
edit_distance("crow", "crowd") == 1

# 1 deletion
edit_distance("beard", "bear") == 1

# 1 substitution
edit_distance("toad", "road") == 1

# 3 substitutions total
# label -> tabel
# tabel -> tabll
# tabll -> table
edit_distance("label", "table") == 3

In the last example, you might want to say that the edit distance is 2, since the last two letters just need to be swapped. And there are edit distance algorithms that allow for that operation; but Levenshtein distance sticks to a simpler set of operations.

Remember: Levenshtein distance is concerned with insertions, deletions, and in-place substitutions. That's what we'll be working on in this chapter.