Except it’s fun: Autocorrect in 3 minutes

Alex Caian

3 min read

·

Apr 1, 2024

--

1

Listen

Share

Welcome! I hope you enjoy reaping this blog!

I meant heading. *

Readying!! ***

Reading! *****

Press enter or click to view image in full size

Hate when that happens. But how does it even work? Let’s learn something new in 3 quick steps:

1. Follow your Intuition

Give credit where credit is due — autocorrect always seems to change words to somewhat similar ones. Let’s stick to our reaping <>reading example. What do we really mean when we say those two words are similar?

They share most of the letters, in the same order.

We can therefore form our first, highly intuitive notion of similarity: Two words are similar insofar as they share as many letters as possible, in the right order. If we want to get closer to quantifying this, we can rephrase it as:

The more similar two words are, the fewer letters we’d need to adjust to get from one to the other.

2. Let’s talk metrics

“Adjust” is a vague word. In our previous example, we’d need to swap a letter for another. Here’s another simple one: Girl <> Girls

In a number of ways, ‘girl’ is no “farther” from ‘girls’ than ‘reading’ is from ‘reaping’. It comes down to what we “value” more. There are broadly two types of adjustments we make to transform words to other words:

• Swaps: Changing a letter to another letter
• Insertions/Deletions: Inserting a whole new letter and/or removing an existing letter.

The question of similarity then becomes:

What is the smallest number of such operations required to transform one word to another?

This is the concept of a Levenshtein distance. The Levenshtein distance between two words is the minimum number of swaps and/or insertions/deletions needed to get from one word to the other. In our examples:

• L(reading, reaping) = 1 ; since we only need 1 letter swap to get there.
• L(girl, girls) = 1 ; as well, since we need a single letter insert/removal.

And that’s it! The smaller the Levenshtein distance is, the more similar the two words are. When two words are identical for example, they have a Levenshtein distance of 0 — which is the smallest possible.

3. Tie it all together

So — how does autocorrect work??

Using numerical notions of similarity like Levenshtein, and comparing against known words in our vocabulary, we can start inferring what someone meant to have typed (more on that at the end). *

Autocorrect integrates this concept, using a strategy known as fuzzy matching. Broadly, fuzzy matching means we have access to a known vocabulary of valid words — so when you mistype (typo), your intended word can be inferred by picking the most similar, valid option from our vocabulary.

Here are two examples:

Press enter or click to view image in full size

There’s a lot more to learn about fuzzy matching, autocorrect and natural language — but I hope this gets your interest going!

See you next time :)

*Most autocorrect algorithms also use several other tools & concepts, such as: Context (inferred from surrounding words in your sentence), Human typing (inferred from your letters proximity on your keyboard) and language settings.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

I’m open to answering any other questions in private — just drop me a message on LinkedIn or Email :)

Find me on: Github || LinkedIn or via email at axl_acc@yahoo.ro