The minimum edit distance between two strings is defined as the minimum number of operations (also called edits) needed to transform one string into another. Operations includes insertion, deletion, substitution, and switch.

Minimum edit distance

Edit distance counts the number of operations that performed on a string to change it into another string.

University of Michigan - Ann Arbor

1. Identify a misspelled word
    - If word not in vocabulary: misspelled = True
2. Find string n edit distance away
    - n edit distance tells you how many operations away one string is from another (usually set n to 1-3).
3. Filter candidates
    - If candidate not in vocabulary: list.pop(candidate)
    - At last, you will get a list of actual words
4. Calculate word probabilities
    - In the text/corpus, count word frequency and calculate word probabilities (number of times the word appears / total size of the corpus)
    - Find the word with the highest probability and choose it as the replacement

The steps of building the autocorrect model are based on the "Natural Language Processing with Probabilistic Models" course on Coursera.

Building an autocorrect model

An on-going but a helpful book resource about NLP
https://web.stanford.edu/~jurafsky/slp3/

Speech and Language Processing (3rd ed. draft) 

Edit distance

An operation performed on a string to change it by following steps:

1- Insert

2- Delete

3- Switch

4-Replace

Learn Before

Related

Learn After