Autocorrect - Is your phone reading your mind?

Except for some mortifying and hilarious auto-correct fails that often circulate around the internet, the autocorrect feature on smartphones is generally useful in increasing our texting productivity, and correcting embarrassing misspelled words before we send out important emails. This handy tool, in some cases, can even analyze the context by determining the recipient of messages, and suggest the most suitable alternatives.

So, what is the algorithm behind autocorrect? Could we build a simple autocorrect program?

The basic principles of autocorrect is to have a comprehenisive dictionary of words and colloquialisms that are often used in modern context. Given a word, it would try different sorts of revisions, such as deletion, transposition (swap too adjacent letters), a replacement, or an insertion.  For a word of length n, there will be n deletions, n-1 transpositions, 26n alterations, and 26(n+1) insertions, for a total of 54n+25 (Norvig). Because this approach would result in such a big set, the algorithm then ruled out all non-sensical words, using the built-in dictionary.

However, how could the program tell if “lates” should be corrected to “late”, “latest” or “lattes” (Norvig) ? What’s its secret to finding the most suitable correction? This is where math and probabilities came in. Let w be the word the user typed in, and c as the correction. The algorithm would analyze both the probability that c appears as a word of English text (ex: “the probability of “the” occuring in English text would be 7%), and the probability that w would be typed in a text when the author meant c (ex: the probability would be high for “teh” and “the”, but low for “theeezyx” and “the”) (Norvig). Then it would try to determine the word that has the highest combined probability. I would not go too deep into the calculations in this blog, but here is a thorough and relatively easy-to-understand explanation if you guys want to dig deeper into this. 

That is the basics of a simple autocorrect program. Most current autocorrection systems—including on the iPhone, Android, BlackBerry – also incorporate some kinds of learning behavior, and is constantly improving to meet users' need. Nevertheless, this technology still has  a lot of room to grow. Hopefully in the future, the occurences of autocorrect mishaps would decrease, and the algorithm might be able to predict full phrases or sentences that the users intend to type.

            Works Cited

Content:

http://norvig.com/spell-correct.html

http://www.slate.com/articles/technology/technology/2010/07/yes_ill_matty_you.html

Graphics

pirateprerogative.com. Dear AutoCorrect

DailyMails.co.uk. The Funniest Autocorrect Fails Sweeping Webs.