How to compare two strings containing typos?

Comparing two strings is one of the first exercises you learn to do when studying programming, but when one of these strings has been written by a human, the task becomes much more complicated.

Normally your first instinct is to perform two operations before using the classic comparison operator:

• Convert both strings to lowercase to avoid any case issues
• Remove all accents

And that's a good start, but in the case of a spelling mistake or simple typo, your basic comparison algorithm will no longer be sufficient.

So how do you make your code understand that "Titanic" and "Titanik" are indeed equivalent to each other? We're going to learn how to do this thanks to a fairly simple algorithm called the "Levenshtein distance".

The Levenshtein distance

The way this algorithm works is simple to understand but can be very powerful if used well.

The principle

The algorithm consists of comparing the distance between two strings based on the minimum number of basic transformations needed to make the strings similar to each other.

These transformations number three, namely:

• The addition of a character
• The deletion of a character
• The replacement of a character

For example, to make the strings "developpeur" and "developers" similar, the following transformations will need to be applied to the first word:

• deletion of the character "p" at position 6
• deletion of the character "u" at position 9
• addition of the character "s" at the end of the string

Since each transformation has the same value (1) for calculating the distance, you just need to add up the number of transformations performed. In this case, the Levenshtein distance between "developpeur" and "developers" is 3.

Usage

As you may have noticed, if you use only the Levenshtein distance without first taking care to transform the strings beforehand, the algorithm will take case as well as accents into account.

The ideal approach is therefore to start with these two transformations beforehand before calculating the distance between the two strings, but you also need to think about the ideal distance for which you want to accept an answer or not.

Indeed, the greater the accepted distance, the more permissive your code will be and the more likely it is to let false positives through, and conversely, too short an accepted distance risks excluding words that are nonetheless very close.

For example, simply forgetting an "s" already equals a distance of 1

There isn't really an ideal distance, it all depends on the language it's applied to as well as the length of the original word. Because yes, a distance of 1 on a 3-letter word or on a 10-letter word doesn't really have the same impact in a real-world scenario.

It's up to you to run your own tests and find the right way to use this algorithm.

Drawbacks

Besides the fact that there is no ideal distance, the main point of caution concerns the type of data you want to check.

For example, in the context of a quiz, we can imagine that the answers "chien" or "chiens" are just as valid as each other, but the answers "1968" and "1969" don't have the same meaning at all, even though all these examples have the same Levenshtein distance equal to 1.

You should therefore not apply this distance without taking into account the format of the data you expect as input and carefully consider the relevance of this method for your use case.

Implementation in Javascript

Even though the principle of this algorithm is very easy to understand, the implementation can play a real role in its performance.

So here's a link to the most efficient Javascript implementation that you can include in your projects.

If you're developing in another language, don't worry, you'll definitely find an existing implementation, and if you're interested in the pseudocode, you'll find a version accessible to everyone on Wikipedia:

https://fr.wikipedia.org/wiki/Distance_de_Levenshtein#Algorithme