# Algorithms to correct misspelled word?

At present, I am doing a project on Optical Character Recognition (OCR). I am looking forward to improve the results by checking the output words of my OCR code with existing words from a text file. The file contains all English words.

Word is good to go if it exists in the file, but if it doesn't then I want to replace it with a word from the text file. Suppose the word in the image was "horse", and the OCR gives "hurze". Which algorithms should I use for detecting errors and their corrections.

I know that sometimes the correction depends on the context of the sentence. But, the thing is that I am not looking for 100% results. I just want to improve my results for OCR.

Can you suggest me anything else? I am looking forward to ideas.

• You can find the word which is closest to the read word in edit distance. Or you could come up with a better metric that takes into account what errors to expect from the OCR process. How to do this efficiently is a different question. Commented Apr 6, 2017 at 18:26
• @YuvalFilmus If I find the closest word, then hurze is no way near to the horse. I am also looking for efficient methods. Commented Apr 6, 2017 at 18:32
• Closest in edit distance, not in lexicographic order. Of course, it's better to come up with an OCR-specific version of edit distance. Before coming up with an efficient algorithm, you have to figure out what problem this algorithm is trying to solve. Let me stress that computing the edit distance can be done efficiently, but doing it for every word in the dictionary could be a bit slow if you had to do it a lot; but you don't necessarily have to speed it up by much, since OCR itself is also quite computation-intensive. Commented Apr 6, 2017 at 18:33
• For example, I would never misspell "wave" as "vvave" but OCR might do that. Commented Apr 7, 2017 at 20:57

## 1 Answer

Standard OCR software already incorporates this idea: it has a corpus of words, along with their frequency of occurrence, and uses this to correct errors.

How does it work? OCR doesn't just output a letter at each position; it actually produces a probability distribution on letters. For example, its output might be something like: I'm 99% sure the first letter is a 'h'; I'm 60% sure the second letter is a 'u', but there's is a 20% chance it is a 'o', and a 15% chance it is an 'a', and so on. This lets you consider many possibilities for what the word might be, and combine the probabilities from the OCR with the frequency of occurrence of that possibility in English text to come up with an educated guess about what the actual word is.

For instance, if the OCR says "5% chance this is 'hurze", 2% chance this is 'horse'", and you know that 'horse' occurs 100x more often than 'hurze' in English language, you should guess that the corresponding word is probably 'horse', not 'hurze'.

As Yuval Filmus says, another approach is to look for a dictionary word that is within edit distance 1 or 2 of the raw output from the OCR.

If your OCR software is any good, it might already be doing this sort of correction. Sometimes you can give the OCR software a custom dictionary of words that tend to appear in your documents, to help it do this sort of correction.

• Any idea how applications like MS Office, Grammarly, etc. provides options for correction? What kind of algorithms do they use? Commented Apr 6, 2017 at 19:04