AUTOMATIC CORRECTION OF USER INPUT BASED ON DICTIONARY

• US 20090083028A1
• Filed: 08/29/2008
• Published: 03/26/2009
• Est. Priority Date: 08/31/2007
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Avidor, Adi, Coccaro, Noah, Tanev, Mario, Davtchev, Ivan D., Andelman, Nir
• Granted Patent: US 8,229,732 B2
• Time in Patent Office: Days
• US Class Current: 704/9
• 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 the language;

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

if a word is identified, accepting the characters as input;

if no word is identified, then;

selecting an alternative keyboard mapping associated with an alternative language;

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

comparing the alternative characters to alternative words in an alternative dictionary, the alternative dictionary storing alternative words for an alternative language; and

determining that the alternative keyboard 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:

selecting one or more candidate words if the alternative characters match an alternative word in the dictionary; and

providing the one or more candidate words on a user device.

3. The computer implemented method of claim 2, wherein a candidate word is ranked based upon an edit distance to the alternative input characters.

4. The computer implemented method of claim 2, wherein a candidate word is ranked according to a frequency of usage comprising a frequency with which the word is occurs in query logs.

5. The computer implemented method of claim 2, wherein a candidate word is ranked according to a frequency of usage comprising a frequency with which the word is used in a language model.

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

selecting one or more candidate words if the alternative characters match an alternative word in the dictionary; and

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

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

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

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

8. The computer implemented method of claim 1, wherein determining a current mapping for the keyboard 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 device comprises:

identifying a language corresponding to a geolocation of the keyboard device; and

determining the current mapping related to the language.

10. The computer implemented method of claim 1, further comprising deriving the alternative keyboard 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 keyboard mapping for the keyboard device and that is associated with a language;

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

comparing the characters to words in the language;

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

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

selecting an alternative keyboard mapping associated with an alternative language;

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

comparing the alternative characters to alternative words in the alternative language; and

identifying one or more alternative words if the alternative characters match alternative words in the alternative language.

12. The computer implemented method of claim 11, wherein determining a current mapping for the keyboard 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 device comprises:

identifying a language corresponding to a geolocation of the keyboard device; and

determining the current mapping related to the language.

14. The computer implemented method of claim 11, further comprising deriving the alternative keyboard mapping, 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 keystrokes associated with a keyboard;

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

comparing the plurality of characters to a plurality of words in the current language;

determining whether the plurality of characters identifies a word in the language if an edit distance between the plurality of characters and the plurality of words in the current language is above a threshold edit distance;

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

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

comparing the plurality of alternative characters with a plurality of alternative words associated with one or more alternative languages;

identifying one or more candidate alternative words if an edit distance between the plurality of alternative characters and the plurality of alternative words in 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 upon 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,

accept the characters based upon identifying a threshold match between the characters and a word;

derive alternative characters based on the keystroke data when a threshold match is not identified; and

compare the alternative characters to alternative words associated with an alternative dictionary to identify an alternative candidate word; 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 device from the language from 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 device comprises through identification of a language corresponding to a geolocation of the keyboard device and to identify the current mapping related to the language.

23. The system of claim 20, wherein the comparison module is operable to select alternative keyboard mappings, alternative languages and the alternative dictionaries responsive to browser settings, operating system settings, browser cookies, or user history.