Web-based spell checker

• US 9,489,372 B2
• Filed: 03/15/2013
• Issued: 11/08/2016
• Est. Priority Date: 03/15/2013
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Tam, Siu-lung, Chan, Man-hon, Prilepov, Iuri, Cheung, Tang-lung, Lee, Keng-fai
• Primary Examiner(s): Ries, Laurie
• Application Number:
  US13/842,827
• Publication Number:
  US 20140281943A1
• Time in Patent Office: 1,334 Days
• US Class Current: 1/1
• 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 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.

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;

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.