Automatic correction of user input based on dictionary

• US 8,229,732 B2
• Filed: 08/29/2008
• Issued: 07/24/2012
• Est. Priority Date: 08/31/2007
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Davtchev, Ivan D., Coccaro, Noah, Avidor, Adi, Andelman, Nir, Tanev, Mario
• Primary Examiner(s): ALBERTALLI, BRIAN LOUIS
• Application Number:
  US12/201,895
• Publication Number:
  US 20090083028A1
• Time in Patent Office: 1,425 Days
• Field of Search: None
• US Class Current: 704/8
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 40/232 Orthographic correction, e.g. spell checking or vowelisation
• CPC Class Codes: G06F 40/263 Language identification
• CPC Class Codes: G06F 40/53 Processing of non-Latin text kana-to-kanji conversion G06F40/129; vowelisation G06F40/232

Abstract

Methods, systems, and apparatus, including computer program products, in which input keystroke data can be interpreted by a current mapping and a determination can be made whether the current mapping is valid based upon the characters identified by the mapping and the keystroke data. Invalid mappings can be corrected based upon alternative mapping of the keystroke data.

Claims

1. A computer implemented method comprising:

receiving keystroke data from a keyboard input device;

determining a current mapping for the keyboard input device in response to a language for the keyboard input device;

identifying characters responsive to the keystroke data and the current mapping;

comparing the characters to words in a dictionary associated with the current mapping, wherein the dictionary stores words in the language;

determining whether the characters identify a word in the language based on the comparison;

if a word in the language is identified by the characters, accepting the characters as input; and

if no word in the language is identified by the characters;

selecting an alternative mapping for the keyboard input device, wherein the alternative mapping is associated with an alternative language;

determining alternative characters based on the keystroke data and the alternative mapping;

comparing the alternative characters to alternative words in an alternative dictionary associated with the alternative mapping, wherein the alternative dictionary stores words in the alternative language; and

determining that the alternative mapping is valid if the alternative characters match an alternative word in the alternative dictionary.

2. The computer implemented method of claim 1, further comprising:

wherein if the alternative characters do not match any alternative word in the alternative dictionary;

identifying one or more candidate words based on partial matches of the alternative characters to the alternative words;

ranking the identified candidate words at least in part based on respective frequencies of usage of the identified candidate words in a language model of the alternative language; and

providing the one or more identified candidate words for display on a user device at least in part based on the ranking.

3. The computer implemented method of claim 2, wherein the candidate words are ranked at least in part based on an edit distance of the candidate word to the alternative input characters.

4. The computer implemented method of claim 2, wherein the candidate word is ranked at least in part based on a frequency of usage of the candidate word comprising a frequency with which the candidate word occurs in query logs.

5. The computer implemented method of claim 2, wherein the candidate words are ranked at least in part based on a frequency of usage of the candidate word comprising a frequency with which the candidate word is used in a language model.

6. The computer implemented method of claim 1, further comprising:

wherein if the alternative characters do not match any alternative word in the alternative dictionary;

identifying one or more candidate words based on partial matches of the alternative characters to the alternative words;

ranking the identified candidate words at least in part based on respective frequencies of usage of the identified candidate words in a language model of the alternative language; and

providing the one or more identified candidate words to a search engine interface at least in part based on the ranking.

7. The computer implemented method of claim 1, further comprising:

entering the word or the alternative word into a search query; and

performing a search of internet documents based on the search query.

8. The computer implemented method of claim 1, wherein determining a current mapping for the keyboard input device comprises retrieving the language from web browser preferences or browser cookies, an input method editor (IME), an operating system, or the keyboard input device.

9. The computer implemented method of claim 1, wherein determining a current mapping for the keyboard input device is at least in part based on

a language corresponding to a geolocation of the keyboard input device.

10. The computer implemented method of claim 1, further comprising deriving the alternative mappings and the alternative dictionary from browser settings, operating system settings, or browser cookies.

11. A computer implemented method comprising:

receiving keystroke data for a keyboard input device;

determining a current mapping for the keyboard input device that is associated with a language;

determining characters based on the keystroke data and the current mapping;

comparing the characters to words in a dictionary associated with the language, wherein the dictionary stores words in the language;

determining whether the characters identify a word in the language based on the comparison;

if the characters are determined to not identify a word in the language;

selecting an alternative mapping for the keyboard input device, wherein the alternative mapping is associated with an alternative language;

determining alternative characters based on the keystroke data and the alternative mapping;

comparing the alternative characters to alternative words in an alternative dictionary associated with the alternative language wherein the alternative dictionary stores words in the alternative language; and

identifying one or more alternative words based on the comparison of the alternative characters and the alternative words in the alternative language.

12. The computer implemented method of claim 11, wherein determining a current mapping for the keyboard input device comprises

retrieving the language from web browser preferences or cookies, an input method editor (IME), an operating system, or the keyboard input device.

13. The computer implemented method of claim 11, wherein determining a current mapping for the keyboard input device is at least in part based on

a language corresponding to a geolocation of the keyboard input device.

14. The computer implemented method of claim 11, further comprising deriving the alternative mapping, the alternative language and the alternative dictionary from browser settings, operating system settings, browser cookies, or user history.

15. Software stored in one or more computer readable media and comprising instruction executable by a processing system, and upon such execution causing the processing system to perform operations comprising:

receiving a plurality of keystrokes associated with a keyboard input device;

identifying a plurality of characters based on the plurality of keystrokes and a current language associated with the keyboard input device;

comparing the plurality of characters to a plurality of words from a current dictionary associated with the current language;

determining whether the plurality of characters identifies a word in the current dictionary at least on part based on whether an edit distance between the plurality of characters and a word from the plurality of words in the current dictionary is above a threshold edit distance;

if the plurality of characters does not identify a word in the current dictionary;

identifying a plurality of alternative characters using an alternative mapping of the keyboard input device in one or more alternative languages;

comparing the plurality of alternative characters to a plurality of alternative words from an alternative dictionary associated with the one or more alternative languages;

identifying one or more candidate alternative words at least in part based on an edit distance between the plurality of alternative characters and the plurality of alternative words from an alternative dictionary associated with the one or more alternative language.

16. The software of claim 15, the instructions further operable to cause the processing system to perform a further operation comprising

providing the one or more candidate alternative words to a user device.

17. The software of claim 16, the instructions further operable to cause the processing system to perform a further operation comprising

providing the one or more candidate alternative words in a list ordered from most frequently used alternative words to least frequently used alternative words.

18. The software of claim 16, the instructions further operable to cause the processing system to perform a further operation comprising

providing the one or more candidate alternative words in a list ordered by an edit distance between the alternative characters and the one or more candidate alternative words.

19. The software of claim 15, the instructions further operable to cause the processing system to perform a further operation comprising

providing the one or more candidate alternative words to a search engine interface.

20. A system comprising:

an input module operable to receive keystroke data from a keyboard input device and to map the keystroke data to characters based on a current mapping associated with the keyboard input device;

a comparison module operable to;

compare the characters to words identified by a dictionary associated with the current mapping, wherein the dictionary stores words in a current language associated with the current mapping,

accept the characters based on identifying a threshold match between the characters and a word from the current dictionary;

derive alternative characters based on the keystroke data and an alternative mapping when a threshold match between the characters and a word from the current dictionary is not identified; and

compare the alternative characters to alternative words from an alternative dictionary associated with an alternative language to identify an alternative candidate word, wherein the alternative dictionary stores the alternative words in the alternative language; and

an output module operable to provide the word or the alternative candidate word to a user.

21. The system of claim 20, wherein the input module is further operable to identify the current mapping for the keyboard input device from the language of web browser preferences or cookies, an input method editor (IME), an operating system, or the keyboard input device.

22. The system of claim 20, wherein the input module is further operable to

identify the current mapping for the keyboard input device through identification of a local language corresponding to a geolocation of the keyboard input device and

identify the current mapping related to the local language.

23. The system of claim 20, wherein the comparison module is operable to

select alternative mappings, alternative languages and alternative dictionaries responsive to browser settings, operating system settings, browser cookies, or user history.