WEB-BASED SPELL CHECKER

• US 20140281943A1
• Filed: 03/15/2013
• Published: 09/18/2014
• Est. Priority Date: 03/15/2013
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Prilepov, Iuri, Cheung, Tang-lung, Lee, Keng-fai, Tam, Siu-lung, Chan, Man-hon
• Granted Patent: US 9,489,372 B2
• Time in Patent Office: Days
• US Class Current: 715/257
• CPC Class Codes: G06F 40/232 Orthographic correction, e.g. spell checking or vowelisation
• CPC Class Codes: G06F 40/242 Dictionaries

Abstract

A fast client-side spell checker is provided that builds efficient structures out of dictionary and a common misspelling lists 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 also 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. In this way, the spell checker provides a uniform spell checking user experience across different browser platforms.

Claims

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;

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; and

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 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 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, the client device having a plurality of browsers, wherein spell checking and providing suggestion for every word provides a same set of results regardless the browser used to activate the browser-based application.

5. The method of claim 3, 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.

6. The method of claim 5 further comprising:

changing a set of characters in the 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 a set of characters in the misspelled word results a valid string in the dictionary prefix tree.

7. The method of claim 6, 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.

8. The method of claim 6 further comprising:

scoring the suggestions for the misspelled word based on a set of rules; and

displaying up to a predetermined number of high scored suggestions.

9. The method of claim 8 further comprising assigning a highest score to any suggestions found for the misspelled word in the common misspelling prefix tree.

10. The method of claim 8 further comprising assigning scores 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 finding the same valid string in the dictionary prefix tree.

11. The method of claim 8 further comprising assigning scores 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.

12. 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 repressing a commonly misspelled word and associated with a set of suggestions to correct the commonly misspelled word.

13. 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.

14. A machine-readable medium storing a program for spell checking a document on a client device, the program executable by at least one processing unit, the program comprising sets of instructions for:

activating a browser-based application received from a server through a network;

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; 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 machine-readable medium of claim 14, the program further comprising sets of instructions for:

determining whether a 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 word as a misspelled word when no rule in the set of rules is satisfied.

16. The machine-readable medium of claim 15, the program 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 machine-readable medium of claim 16, the client device having a plurality of browsers, wherein spell checking and providing suggestion for every word provides a same set of results regardless the browser used to activate the browser-based application.

18. The machine-readable medium of claim 16, 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.

19. The machine-readable medium of claim 18, the program further comprising sets of instructions for:

changing a set of characters in the 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 a set of characters in the misspelled word results a valid string in the dictionary prefix tree.

20. The machine-readable medium of claim 19, 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.

21. The machine-readable medium of claim 19, the program further comprising sets of instructions for:

scoring the suggestions for the misspelled word based on a set of rules; and

displaying up to a predetermined number of high scored suggestions.

22. The machine-readable medium of claim 21, the program further comprising a set of instructions for assigning a highest score to any suggestions found for the misspelled word in the common misspelling prefix tree.

23. The machine-readable medium of claim 21 further comprising assigning scores 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 finding the same valid string in the dictionary prefix tree.

24. The machine-readable medium of claim 21, the program further comprising a set of instructions for assigning scores 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.

25. The 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 repressing a commonly misspelled word and associated with a set of suggestions to correct the commonly misspelled word.

26. The 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 program 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.