Determining proximity measurements indicating respective intended inputs

• US 9,069,753 B2
• Filed: 10/04/2010
• Issued: 06/30/2015
• Est. Priority Date: 08/25/2004
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Wu, Jun, Chen, Liren
• Primary Examiner(s): TSUI, WILSON W
• Application Number:
  US12/897,096
• Publication Number:
  US 20110022952A1
• Time in Patent Office: 1,730 Days
• Field of Search: 715/256, 715/257, 715/261, 715/269, 715/705
• US Class Current: 1/1
• CPC Class Codes: G06F 40/232 Orthographic correction, e.g. spell checking or vowelisation

Abstract

Determination of proximity measurements indicative of respective intended inputs are disclosed. User inputs are received, where each user input is one of a predefined plurality of inputs that each map to multiple characters in a language. Rates of user selections of candidates decoded from the user inputs into the language are received, where each of the candidates includes one or more characters in the language. User inputs for the candidates having low rates of selection as non-selected user inputs are identified. User inputs for the candidates having high rates of selection as intended inputs are identified. The intended user inputs to the non-selected user inputs are compared to identify one or more misspelled input and intended input pairs. A proximity measurement for each misspelled input and intended input pair is determined based on a ratio of the number of times corresponding candidates for the misspelled input were not selected to the number of times the misspelled input was entered.

Claims

1. A computer-implemented method for determining proximity measurements indicating respective intended inputs for corresponding original inputs, the method comprising:

receiving Pinyin inputs;

converting the Pinyin inputs to corresponding candidates, each of the corresponding candidates comprising one or more Hanzi characters;

receiving rates of user selections for each of the corresponding candidates, the rates indicating how often users select each of the corresponding candidates;

identifying, from the received rates, Pinyin inputs converted to candidates having low rates of user selection as non-selected Pinyin inputs;

identifying, from the received rates, Pinyin inputs converted to candidates having higher rates of user selection than the non-selected Pinyin inputs, as intended Pinyin inputs;

comparing the intended Pinyin inputs to the non-selected Pinyin inputs to identify one or more-non-selected Pinyin input and intended Pinyin input pairs;

for each non-selected Pinyin input, determining a number of times that users did not select from the corresponding candidates and a number of times the non-selected Pinyin input was entered as input by users; and

generating a proximity measurement for each-non-selected Pinyin input and intended Pinyin input pair based on a ratio of the number of times the corresponding candidates were not selected by users to the number of times the non-selected Pinyin input was entered as input by users.

2. The method of claim 1, wherein comparing the intended Pinyin inputs to the non-selected Pinyin inputs to identify one or more non-selected Pinyin input and intended Pinyin input pairs comprises identifying non-selected Pinyin inputs and intended inputs differing by one of the vowel and consonant pairs in/ing, an/ang, en/eng, l/n, sh/s, ch/c, zh/z, and h/f.

3. The method of claim 2, wherein the non-selected Pinyin input and intended Pinyin input pairs comprise a pair of Pinyin inputs that differ by one of the vowel and consonant pairs.

4. The method of claim 1, wherein the Pinyin inputs are inputs for search queries.

5. The method of claim 1, wherein comparing the intended Pinyin inputs to the non-selected Pinyin inputs to identify one or more non-selected Pinyin input and intended Pinyin input pairs comprises:

identifying a Pinyin input that is close in editing distance to an intended Pinyin input as the non-selected Pinyin input; and

identifying the non-selected Pinyin input and the intended Pinyin input as the non-selected Pinyin input and intended Pinyin input pair.

6. A non-transitory computer storage medium encoded with a computer program, the program comprising instructions that when executed by data processing apparatus cause the data processing apparatus to perform operations comprising:

receiving Pinyin inputs;

converting the Pinyin inputs to corresponding candidates, each of the corresponding candidates comprising one or more Hanzi characters;

receiving rates of user selections for each of the corresponding candidates, the rates indicating how often users select each of the corresponding candidates;

identifying, from the received rates, Pinyin inputs converted to candidates having low rates of user selection as non-selected Pinyin inputs;

identifying, from the received rates, Pinyin inputs converted to candidates having higher rates of user selection than the non-selected Pinyin inputs, as intended Pinyin inputs;

comparing the intended Pinyin inputs to the non-selected Pinyin inputs to identify one or more-non-selected Pinyin input and intended Pinyin input pairs;

for each non-selected Pinyin input, determining a number of times that users did not select from the corresponding candidates and a number of times the non-selected Pinyin input was entered as input by users; and

generating a proximity measurement for each-non-selected Pinyin input and intended Pinyin input pair based on a ratio of the number of times the corresponding candidates were not selected by users to the number of times the non-selected Pinyin input was entered as input by users.

7. The computer storage medium of claim 6, wherein comparing the intended Pinyin inputs to the non-selected Pinyin inputs to identify one or more non-selected Pinyin input and intended Pinyin input pairs comprises identifying non-selected Pinyin inputs and intended inputs differing by one of the vowel and consonant pairs in/ing, an/ang, en/eng, l/n, sh/s, ch/c, zh/z, and h/f.

8. The computer storage medium of claim 7, wherein the non-selected Pinyin input and intended Pinyin input pairs comprise a pair of Pinyin inputs that differ by one of the vowel and consonant pairs.

9. The computer storage medium of claim 6, wherein the Pinyin inputs are inputs for search queries.

10. The computer storage medium of claim 6, wherein comparing the intended Pinyin inputs to the non-selected Pinyin inputs to identify one or more non-selected Pinyin input and intended Pinyin input pairs comprises:

identifying a Pinyin input that is close in editing distance to an intended Pinyin input as the non-selected Pinyin input; and

identifying the non-selected Pinyin input and the intended Pinyin input as the non-selected Pinyin input and intended Pinyin input pair.