I've never had to make a spell checker before, so I was wondering if anyone knew the best algorithm for this. It will be written in Javascript, and no, I don't want a premade spell checker. If anyone can post a link to some different algorithms, it would be appreciated.

And yes, I am googling it right now, I was just wondering if any one here knew some algorithms.

Thanks.

EDIT: Oh, and time efficiency is important.

Algorithm? Isn't just a simple lookup table?

Unless you want to fill up your own dictionary with all the words in the english language, I'd suggest getting ahold of someone else's if you can.

Yeah pretty sure Tux is right, there's no algorithm. It's a dictionary lookup and if there is an algorithm, it's just based off adding suffixes to words to form plurals, participles, etc., while keeping track of exceptions. This is pretty much the last thing I'd want to create.

Finding out if a word doesn't exist in the dictionary is the easy part, I was talking about the part where it suggests what word you meant to type if it doesn't exist in the look up table.

You could brute-force it by checking for the adjacent keys of each letter of the word.

Example: I wanted to spell "dog", but typed "eog" instead. "eog" is not in the dictionary, go through each letter of "eog" (e, o, g) to find respective adjacent letter-keys (e's adjacent keys would be w, s, d, f, r; o's adjacent keys would be p, l, k, i), and if any of the new combination of letters makes a valid word from the dictionary, suggest that word.

But, that doesn't sound very efficient. :x

(wog), sog, (dog), (fog), rog
eig, ekg, elg, epg
eot, eor, eof, eov, eob, (eon), eoh, eoy

The next (more inefficient but comprehensive) method would be to replace every single letter of the word with every single letter from the alphabet.
But that would still be slow. :x

That's what most spell checkers do from what my research shows. I like your idea though.

I've also noticed that some methods add and subtract letters, and swap letters, along with replacing letters. They then repeat this process two or three times.

But that sounds like a lot of checking...

Oh word suggest? Maybe you could dissect a given word into its syllables, then check alternate spellings for given syllables and return the resulting set of words that also happen to exist in the dictionary. Or find similar-sounding or closely-spelled syllables, try them out, and check if they produce actual words as well.

If it's only 1 word at a time, it shouldn't be hugely problematic performance wise.

Post has been edited 2 time(s), last time on Jan 4 2011, 10:41 pm by Tuxedo-Templar.

How about making a 2nd row in the word database which has an integer value associated to each word. In the first step you look for the checked word itself and if it wasn't found (e.g. typo) you compare the 2nd row with the integer value of the checked word and if it's only different by a small amount suggest this word.

This would be among the fastest methods possible, I believe, but the would probably also generate false positives - depending on the algorithm creating the integer. The problem is finding a clever algorithm that creates a useful integer value for you. Ideally it'd be something like a MD5 hash where every word has a unique number but similar words (differ only in 1 or 2 letters) have close values. I'm not sure if something like this exists or is even possible, but if you're interested I can put more thought / research into the idea.

The point of something like MD5 is so similar things have drastically different results ... You'd probably have to make your own hashing algorithm.

I know how MD5 works. My point was that it should create a unique ID for each word (like MD5) but NOT a completely different ID for similar words (UNlike MD5)

There appears to be something like this already: http://en.wikipedia.org/wiki/Levenshtein_distance . I'm currently looking into it. There likewise exists the function ratio() in the python library that returns a ratio of whether two strings are similar.

Is this what you are talking about?

Btw, thanks everyone for the suggestions. Most of these I've never even thought of.

Well, kinda, yes. But the levenshtein distance requires you to run a function involving both strings which I was trying to avoid because that's far slower than comparing a value with a row in a table.
However there's several optimizations, most of which can be applied to your problem since you're only interested in near distances (close matches). You'll have to try it out if performance is good enough for you.

EDIT:
These seem also relevant:
http://en.wikipedia.org/wiki/Levenshtein_automaton
http://en.wikipedia.org/wiki/Hash_function#Finding_similar_records

Post has been edited 1 time(s), last time on Jan 5 2011, 12:41 pm by NudeRaider.

My dictionary of words also has a frequency associated with each word, so, I'm thinking of ordering possible word suggestions by frequency. Good idea, or no?

Typos are generally of a similar length to the misspelled words.

DOG
FOGG

So take all words that are within two characters of input's length, and narrow it down from there, or something. Prefixes and suffixes could complicate this, though.

FAMNING

Did you mean:
FARMING
DAMNING
CANNING
FAMINE

etc.

Wouldn't FAMNING be two mutations away from FARMING? That would be a lot of mutations to check. Not sure if there is a better way. And technically DAMNING is only one mutation away, so it should be first on the list.