-
Notifications
You must be signed in to change notification settings - Fork 0
PhillipTaylor/CSpellChecker
This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.
Folders and files
Name | Name | Last commit message | Last commit date | |
---|---|---|---|---|
Repository files navigation
A basic complete example of a spell checker. first, I wrote a function "int get_key(string)" that turns a word into a numeric representation. So a=0, b=1, c=2 .... y=24, z=25, aa=26 etc. This is the key function in my hash table. Then I take any word, map it to it's number and I store a boolean 1 or 0 in the array at that word's location to mark it as valid or invalid. Since I only need a bit for every word, I use the mod and power functions to store 32 flags in a single array element. That way I can store the whole dictionary in 352 elements. Here's an example: 1. hello = 307 2. 307 / 32 = 9. 3. Get the unsigned 32 bit int at position 9 in the array. 4. the uint32s value is = 00100010101010101010101010101010 5. 307 % 32 = 19. Extract bit 19. 6. if 1, word is valid. If 0, word is invalid. 7. if storing a word, set that bit to 1. notes: The longest word in the dictionary is antidisestablishmentarianism. It's 28 chars, so when we get to char 29 of the current word, just automatically fail. A limit of 29, regardless of the passed in word's length means the program is O(1). The value of the longest word is 11281, so my array goes from 0 -> 11281. If the array is 32 bit integers, we can divide 11281 / 32 and store every word in just 352 elements. Phillip Taylor.
About
The basic O(1) spell checker implementation
Resources
Stars
Watchers
Forks
Releases
No releases published
Packages 0
No packages published