AUTOCORRECTING LANGUAGE INPUT FOR VIRTUAL KEYBOARDS

• US 20120310626A1
• Filed: 06/01/2012
• Published: 12/06/2012
• Est. Priority Date: 06/03/2011
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Kida, Yasuo, Collins, Leland Douglas Jr.
• Granted Patent: US 9,471,560 B2
• Time in Patent Office: Days
• US Class Current: 704/8
• CPC Class Codes: G06F 40/232 Orthographic correction, e.g. spell checking or vowelisation

Abstract

Various techniques for autocorrecting virtual keyboard input for various languages (e.g., Japanese, Chinese) are disclosed. In one aspect, a system or process receives a sequence of keyboard events representing keystrokes on a virtual keyboard. A hierarchical data structure is traversed according to the sequence of keyboard events to determine candidate words for the sequence of keyboard events. A word lattice is constructed using a language model, including deriving weights or paths in the word lattice based on candidate word statistics and data from a keyboard error model. The word lattice is searched to determine one or more candidate sentences comprising candidate words based on the path weights. Paths through the word lattice can be pruned (e.g., discarded) to reduce the size and search time of the word lattice.

Claims

1. A method comprising:

receiving a sequence of keyboard events representing keystrokes input to a virtual keyboard of a device;

traversing a hierarchical data structure according to the sequence of keyboard events to determine candidate words;

constructing a word lattice based on a language model, including deriving path weights from candidate word statistics and keyboard error model data;

searching the word lattice for N best paths, where N is a positive integer; and

determining one or more candidate sentences comprising candidate words based on the N best paths,

where the method is performed by one or more hardware processors of the device.

2. The method of claim 1, further comprising:

displaying the candidate sentences on a screen of the device.

3. The method of claim 1, where the hierarchical data structure is a trie data structure.

4. The method of claim 1, where the language represented by the language model is Japanese or Chinese.

5. The method of claim 1, further comprising:

pruning paths in the word lattice based on the path weights.

6. A non-transitory computer-readable medium storing instructions, which, when executed, are operable to cause one or more processors to perform operations comprising:

receiving a sequence of keyboard events representing keystrokes input to a virtual keyboard of a device;

traversing a hierarchical data structure according to the sequence of keyboard events to determine candidate words;

constructing a word lattice based on a language model, including deriving path weights from candidate word statistics and keyboard error model data;

searching the word lattice for N best paths, where N is a positive integer; and

determining one or more candidate sentences comprising candidate words based on the N best paths.

7. The non-transitory computer-readable medium of claim 6, the operations further comprising:

displaying the candidate sentences on a screen of the device.

8. The non-transitory computer-readable medium of claim 6, where the hierarchical data structure is a tie data structure.

9. The non-transitory computer-readable medium of claim 6, where the language represented by the language model is Japanese or Chinese.

10. The non-transitory computer-readable medium of claim 6, the operations further comprising:

pruning paths in the word lattice based on the path weights.

11. A system comprising:

one or more hardware processors;

a non-transitory computer-readable medium storing instructions, which, when executed, are operable to cause the one or more processors to perform operations comprising;

receiving a sequence of keyboard events representing keystrokes input to a virtual keyboard of a device;

traversing a hierarchical data structure according to the sequence of keyboard events to determine candidate words;

constructing a word lattice based on a language model, including deriving path weights from candidate word statistics and keyboard error model data;

searching the word lattice for N best paths, where N is a positive integer; and

determining one or more candidate sentences comprising candidate words based on the N best paths.

12. The system of claim 11, the operations further comprising:

displaying the candidate sentences on a screen of the device.

13. The system of claim 11, where the hierarchical data structure is a trie data structure.

14. The system of claim 11, where the language represented by the language model is Japanese or Chinese.

15. The system of claim 11, the operations further comprising:

pruning paths in the word lattice based on the path weights.

searching the word lattice for N best paths, where N is a positive integer; and

determining one or more candidate sentences comprising candidate words based on the N best paths.