Text correction processing

• US 8,994,660 B2
• Filed: 08/29/2011
• Issued: 03/31/2015
• Est. Priority Date: 08/29/2011
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Neels, Alice E., Jong, Nicholas K.
• Primary Examiner(s): Chang, Kent
• Assistant Examiner(s): ROSARIO, NELSON M
• Application Number:
  US13/220,202
• Publication Number:
  US 20130050089A1
• Time in Patent Office: 1,310 Days
• Field of Search: 345/156, 345/168, 345/169, 345171-178, 704/1, 704 8- 10, 715257-261
• US Class Current: 345/162
• CPC Class Codes: G06F 3/0237 using prediction or retrieval techniques
• CPC Class Codes: G06F 3/04886 by partitioning the display area of the touch-screen or the surface of the digitising tablet into independently controllable areas, e.g. virtual keyboards or menus

Abstract

Text correction processing is disclosed. An initial score is assigned to each of a plurality of candidate sequences of one or more characters, based at least in part on a keyboard geometry-based value associated with the received user input with respect to the candidate key. Further processing is performed with respect to a subset of the candidate sequences having the highest initial score(s) to determine for each candidate sequence in the subset a refined score. A candidate sequence is selected for inclusion in a result set based at least in part on a determination that a refined score of the selected candidate is higher than an initial score of one or more candidate sequences that are not included in the subset and with respect to which the further processing has not been performed.

Claims

1. A method of processing user input, comprising:

assigning to each of a plurality of candidate sequences of one or more characters, each associated with a candidate key which has been identified as a candidate with which a received user input is associated, an initial score based at least in part on a keyboard geometry-based value associated with the received user input with respect to the candidate key;

performing further processing with respect to a subset of the candidate sequences having the highest initial score(s), without at least initially performing the same further processing with respect to one or more other candidate sequences not in the subset, to determine for each candidate sequence in the subset a refined score; and

selecting a candidate sequence for inclusion in a result set based at least in part on a determination that a refined score of the selected candidate is higher than an initial score of one or more candidate sequences that are not included in the subset and with respect to which the further processing has not been performed.

2. The method of claim 1, wherein the received user inputs comprise touches on a touch-sensitive display or other input device.

3. The method of claim 1, wherein the keyboard geometry-based value comprises an error vector representing a detected location of the user input relative to a location at which a user interface image associated with the candidate key is displayed.

4. The method of claim 1, wherein the further processing includes using a language model to determine the refined score.

5. The method of claim 4, wherein the language model is used to determine a probability of occurrence of the candidate sequence in a language with which the user input is associated.

6. The method of claim 1, wherein result set comprises a set of N candidate sequences to be carried forward into a next iteration of processing.

7. The method of claim 6, wherein the result set comprises a starting set of candidate sequences to be used to evaluate a next user input.

8. The method of claim 6, wherein the steps of performing further processing and selecting are repeated until N candidate sequences have been added to the result set.

9. The method of claim 8, wherein an iteration of the method of claim 1 ends without further processing being performed on any further candidate sequences in the plurality of candidate sequences once N candidate sequences have been added to the result set.

10. The method of claim 1, wherein the further processing includes using a language model and an n-gram context data associated with the candidate sequence to determine the refined score.

11. The method of claim 10, wherein the n-gram context data comprises two words preceding the candidate sequence.

12. The method of claim 1, wherein the further processing includes using a language model and an n-gram context data associated with the candidate sequence to determine at least in part whether the received user input should be mapped to the candidate key.

13. A system configured to process text input, comprising:

an input device configured to receive a sequence of user inputs; and

a processor coupled to the input device and configured to;

assign to each of a plurality of candidate sequences of one or more characters, each associated with a candidate key which has been identified as a candidate with which a received user input is associated, an initial score based at least in part on a keyboard geometry-based value associated with the received user input with respect to the candidate key;

perform further processing with respect to a subset of the candidate sequences having the highest initial score(s), without at least initially performing the same further processing with respect to one or more other candidate sequences not in the subset, to determine for each candidate sequence in the subset a refined score; and

select a candidate sequence for inclusion in a result set based at least in part on a determination that a refined score of the selected candidate is higher than an initial score of one or more candidate sequences that are not included in the subset and with respect to which the further processing has not been performed.

14. The system of claim 13, wherein the input device comprises a touch-sensitive device.

15. The system of claim 13, wherein the input device comprises a touch-sensitive display device and the processor is configured to display on the display device, for each received user input, a selected character to which the input has been mapped.

16. The system of claim 13, wherein the processor is further configured to generate, based at least in part on the result set, an auto-correction/completion candidate.

17. The system of claim 16, wherein the processor is further configured to display a selected auto-correction/ completion candidate.

18. The system of claim 13, wherein the further processing includes using a language model to determine the refined score;

and wherein the system further includes a storage device configured to store the language model.

19. A non-transitory computer program product for processing user input, the computer program product being embodied in a computer readable storage medium and comprising computer instructions for:

assigning to each of a plurality of candidate sequences of one or more characters, each associated with a candidate key which has been identified as a candidate with which a received user input is associated, an initial score based at least in part on a keyboard geometry-based value associated with the received user input with respect to the candidate key;

performing further processing with respect to a subset of the candidate sequences having the highest initial score(s), without at least initially performing the same further processing with respect to one or more other candidate sequences not in the subset, to determine for each candidate sequence in the subset a refined score; and

selecting a candidate sequence for inclusion in a result set based at least in part on a determination that a refined score of the selected candidate is higher than an initial score of one or more candidate sequences that are not included in the subset and with respect to which the further processing has not been performed.

20. A method of processing user input, comprising:

determining based on a received sequence of user inputs a set of candidate key sequences, the set including a candidate key sequences that includes a space key; and

assigning to the candidate key sequence that includes the space key a candidate sequence score determined at least in part by associating with the space key a score component determined based at least in part on a probability associated with a subsequent key that follows the space key in the candidate sequence occurring at the beginning of a word.

21. The method of claim 20, wherein the set of candidate key sequences includes one or more candidate keys.

22. The method of claim 20, further comprising determining based at least in part on the candidate sequence score that a user input associated with the space key in the candidate sequence is to be mapped to the space key.

23. The method of claim 22, further comprising displaying a space in a display location associated with the space key in the candidate sequence based at least in part on the determination.

24. A system configured to process user inputs, comprising:

an input device configured to receive a sequence of user inputs; and

a processor coupled to the input device and configured to;

determine based on a received sequence of user inputs a set of candidate key sequences, the set including a candidate key sequences that includes a space key; and

assign to the candidate key sequence that includes the space key a candidate sequence score determined at least in part by associating with the space key a score component determined based at least in part on a probability associated with a subsequent key that follows the space key in the candidate sequence occurring at the beginning of a word.

25. The system of claim 24, wherein the processor is further configured to determine based at least in part on the candidate sequence score that a user input associated with the space key in the candidate sequence is to be mapped to the space key;

and to display, on a display device comprising the system, a space in a display location associated with the space key in the candidate sequence based at least in part on the determination.