Spell Checker

[metachief]

Here it is... It is very slow so have patience. Also I bet it can be shortened if worked on... Anyways, the source is there so you can help me out to make it function faster.

[DemonWasp]

Interesting how the .t file is misspelled: "cheker".

The output also isn't quite what I would have expected:

code:

hs The word 'hs' is spelled incorrectly! Did you mean: as ha has he his is ms us Enter one of the listed words: his s The word 's' is spelled incorrectly! Did you mean: a as i is ms so us Enter one of the listed words: ms   The word '' is spelled incorrectly! Did you mean: a i Enter one of the listed words: a ext The word 'ext' is spelled incorrectly! Did you mean: eat exit next text Enter one of the listed words:

[Tony]

metachief @ Wed Sep 23, 2009 7:54 pm wrote:

It is very slow...

You seem to be doing your dictionary searches using a binary search in a file. There are two performance problems with this:

1. log(N) performance on ~35,000 word dictionary results in ~16 search steps
2. your search step is an IO seek

Some ideas to consider:

1. Use a dictionary tree to store your words. It's a linear search, one character at a time, but most words are well below 16 letters long (this would be an example where BigO alone isn't enough to compare algorithms).
2. You'll be performing your search in memory, and memory access is 100~1000 times (really) faster than HDD.

[Kharybdis]

I can't believe that you just posted this, meta.. -_-

Your spellchecker is beyond old-school.

But then i believe that Google has a whole department trying to make the search method used at google.ca to be even faster than it is now

[metachief]

Tony, I changed my program to store the dictionary words in the memory by creating an array of those words. However, it takes an awfully long time to load in the beginning. Even though it pays off, since after the first long load there is no waiting.

[Dan]

It is posible to store the dictionary tree on the hard drive but in a way that it resmbels a tree and gets fast access with out having to load it in to memeory.

A simpel example would be to make folders A-Z for the frist letter of the word, each having folders A-Z in them for the second letter and so on intill all words are convered. Then have a file in the folder to mark if this is a word or not. If there is no such directory that matches a word or the file says this is not a word then the word is not in the dictoray.

The problem with this method is it might be harder to generate sugestions and it can be more of a pain to update the dictionary.

You could also store the tree in a singal file and read it in allready processed in a tree format witch might save some time rather then processing a list each run.

I am shure there are other more adnveced methods out there if you research it.