Web-based spell checker
A fast client-side spell checker is provided that builds efficient structures out of dictionary and a common misspelling list and uses the structures to prune the number of searches required to identify misspelled words and provide suggestions for correcting the misspelled words. The spell checker is a browser-based application, which is provided by a server to a client device. The server sends the dictionary and a list of common misspellings to the client device in the form of efficient data structures. The spell checker utilizes a set of rules to identify the words that are not in the dictionary but are intended to be correct as typed. The spell checker is used by different browser-based applications that utilize the same spell checker regardless of the browser platform used to access the applications. The spell checker, therefore, provides a uniform spell checking user experience across different browser platforms.
1. A method of spell checking a document, the method comprising:
at a client device, activating a browser-based application received from a server through a network;
on the client device, receiving a data structure for a dictionary comprising a list of correctly spelled words from the server, the data structure utilized to prune the number of searches of the dictionary to match a word to strings associated with valid words in the dictionary, wherein the data structure is independent of the browser-based application and is received from the server in a data file separate from the browser-based application; and
by the browser-based application at the client device, determining a word as having a correct spelling when the word matches a string associated with a valid word in the data structure for the dictionary.
2. The method of claim 1 further comprising:
determining whether a second word that does not match any string associated with a valid word in the data structure for the dictionary satisfies a set of rules for valid strings; and
identifying the second word as a misspelled word when no rule in the set of rules is satisfied.
3. The method of claim 2 further comprising:
receiving, from the server, a data structure for a list of common misspellings comprising a set of strings representing common misspelled words, the common misspellings data structure utilized to prune the number of searches required to match a word to a string in the set of strings;
receiving a misspelled word; and
when the misspelled word matches a string in the common misspellings data structure, identifying a set of suggestions associated with the matched string to provide as suggestions to correct the misspelled word.
4. The method of claim 3 , wherein the common misspellings data structure is a prefix tree, wherein the prefix tree comprises a plurality of nodes in a parent-child hierarchical relationship, each node associated with a character, each node further associated with a string, all descendants of a node having a common prefix of the string associated with that node, each of a plurality of nodes in the common misspellings prefix tree representing a commonly misspelled word and associated with a set of suggestions to correct the commonly misspelled word.
5. The method of claim 3 , wherein the dictionary data structure and the common misspellings data structure are received from the server as encoded data structures, the method further comprising:
at the client device, decoding the dictionary data structure from the received dictionary encoded data structure; and
at the client device, decoding the common misspelling data structure from the received common misspelling encoded data structure.
6. The method of claim 1 , wherein the browser-based application is activated by a browser on the client device, the client device comprising a plurality of browsers, the method further comprising:
providing a set of suggestions for one or more words determined as having no correct spelling, wherein spell checking and providing suggestion for each word provides a same set of results regardless of the browser used to activate the browser-based application.
7. The method of claim 1 , wherein the data structure for the dictionary is a prefix tree, the prefix tree comprising a plurality of nodes in a parent-child hierarchical relationship, each node associated with a character, each node further associated with a string, all descendants of a node having a common prefix of the string associated with that node.
8. The method of claim 1 , wherein the data structure for the dictionary is a prefix tree, the method further comprising:
changing a set of characters in a misspelled word;
after changing each character, discarding the change when a resulting string is not found in the dictionary prefix tree; and
identifying a set of suggestions for the misspelled word when changing the set of characters in the misspelled word results in a valid string in the dictionary prefix tree.
9. The method of claim 8 , wherein changing the set of characters comprises one of adding a character to the misspelled word, replacing a character in the misspelled word, and deleting a character in the misspelled word.
10. The method of claim 8 further comprising:
scoring the set of suggestions for the misspelled word based on a set of rules; and
displaying up to a predetermined number of high scored suggestions.
11. The method of claim 10 further comprising assigning a highest score to any suggestions found for the misspelled word in a data structure for a list of common misspellings.
12. The method of claim 8 further comprising:
scoring the set of suggestions for the misspelled word based on how many times a same suggestion is found for the misspelled word when changing the set of characters in the misspelled word results in finding the same valid string in the dictionary prefix tree; and
displaying up to a predetermined number of high scored suggestions.
13. The method of claim 8 further comprising:
scoring the set of suggestions for the misspelled word based on a number of characters that are changed in the misspelled word before changing a set of characters in the misspelled word results a valid string in the dictionary prefix tree; and
displaying up to a predetermined number of high scored suggestions.
14. A non-transitory machine-readable medium storing a browser-based application received from a server through a network for spell checking a document on a client device, the browser-based application executable by at least one processing unit, the browser-based application comprising sets of instructions for:
receiving, on the client device, a data structure for a dictionary comprising a list of correctly spelled words from the server, the data structure utilized to prune the number of searches of the dictionary to match a word to strings associated with valid words in the dictionary, wherein the data structure is independent of the browser-based application and is received from the server in a data file separate from the browser-based application; and
determining a word as having a correct spelling when the word matches a string associated with a valid word in the data structure for the dictionary.
15. The non-transitory machine-readable medium of claim 14 , the browser-based application further comprising sets of instructions for:
determining whether a second word that does not match any string associated with a valid word in the data structure for the dictionary satisfies a set of rules for valid strings; and
identifying the second word as a misspelled word when no rule in the set of rules is satisfied.
16. The non-transitory machine-readable medium of claim 15 , the browser-based application further comprising sets of instructions for:
receiving, from the server, a data structure for a list of common misspellings comprising a set of strings representing common misspelled words, the data structure for the common misspellings utilized to prune the number of searches required to match a word to a string in the set of strings;
receiving a misspelled word; and
identifying, when the misspelled word matches a string in the common misspellings data structure, a set of suggestions associated with the matched string to provide as suggestions to correct the misspelled word.
17. The non-transitory machine-readable medium of claim 16 , wherein the common misspellings data structure is a prefix tree, wherein the prefix tree comprises a plurality of nodes in a parent-child hierarchical relationship, each node associated with a character, each node further associated with a string, all descendants of a node having a common prefix of the string associated with that node, each of a plurality of nodes in the common misspellings prefix tree representing a commonly misspelled word and associated with a set of suggestions to correct the commonly misspelled word.
18. The non-transitory machine-readable medium of claim 16 , wherein the dictionary data structure and the common misspellings data structure are received from the server as encoded data structures, the browser-based application further comprising sets of instructions for:
decoding the dictionary data structure from the received dictionary encoded data structure; and
decoding the common misspelling data structure from the received common misspelling encoded data structure.
19. The non-transitory machine-readable medium of claim 14 , wherein the browser-based application is activated by a browser on the client device, the client device having a plurality of browsers, the browser-based application further comprising a set of instructions for providing a set of suggestions for one or more words determined as having no correct spelling, wherein spell checking and providing suggestion for each word provides a same set of results regardless of the browser used to activate the browser-based application.
20. The non-transitory machine-readable medium of claim 14 , wherein the data structure for the dictionary is a prefix tree, the prefix tree comprising a plurality of nodes in a parent-child hierarchical relationship, each node associated with a character, each node further associated with a string, all descendants of a node having a common prefix of the string associated with that node.
21. The non-transitory machine-readable medium of claim 14 , wherein the data structure for the dictionary is a prefix tree, the browser-based application further comprising sets of instructions for:
changing a set of characters in a misspelled word;
discarding, after changing each character, the change when a resulting string is not found in the dictionary prefix tree; and
identifying a set of suggestions for the misspelled word when changing the set of characters in the misspelled word results a in valid string in the dictionary prefix tree.
22. The non-transitory machine-readable medium of claim 21 , wherein the set of instructions for changing the set of characters comprises sets of instructions for (i) adding a character to the misspelled word, (ii) replacing a character in the misspelled word, or (iii) deleting a character in the misspelled word.
23. The non-transitory machine-readable medium of claim 21 , the browser-based application further comprising sets of instructions for:
scoring the set of suggestions for the misspelled word based on a set of rules; and
displaying up to a predetermined number of high scored suggestions.
24. The non-transitory machine-readable medium of claim 23 , the browser-based application further comprising a set of instructions for assigning a highest score to any suggestions found for the misspelled word in a data structure for a list of common misspellings.
25. The non-transitory machine-readable medium of claim 23 , the browser-based application further comprising sets of instructions for:
scoring the set of suggestions for the misspelled word based on how many times a same suggestion is found for the misspelled word when changing the set of characters in the misspelled word results in finding the same valid string in the dictionary prefix tree; and
displaying up to a predetermined number of high scored suggestions.
26. The non-transitory machine-readable medium of claim 21 , the browser-based application further comprising sets of instructions for:
scoring the set of suggestions for the misspelled word based on a number of characters that are changed in the misspelled word before changing a set of characters in the misspelled word results a valid string in the dictionary prefix tree; and
displaying up to a predetermined number of high scored suggestions.