Best Algorithm to make correction typos in text

Question

I have a list of word library and a text in which there are a spell error (typos), and I want to correct the word spell error to be correct according to list of library

for example

in list of word :

listOfWord = [...,"halo","saya","sedangkan","semangat","cemooh"..];

this is my string :

string = "haaallllllooo ssya sdngkan ceemoooh , smngat semoga menyenangkan"

I want change the spellerror to be correct like :

string = "halo saya sedangkan cemooh, semangat semoga menyenangkan"

what is the best algorithm to check each word in list, because I have millions of words in the list and have many possibilities

Answer 1

It depends on how your data is stored, but you'll probably want to use a pattern matching algorithm like Aho–Corasick. Of course, that assumes your input data structure is a Trie. A Trie a very space-efficient storage container for words that may also be of interest to you (again, depending on your environment.)