Autocorrecting language input for virtual keyboards

• US 9,471,560 B2
• Filed: 06/01/2012
• Issued: 10/18/2016
• Est. Priority Date: 06/03/2011
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Kida, Yasuo, Collins, Leland Douglas Jr.
• Primary Examiner(s): Serrou, Abdelali
• Application Number:
  US13/487,113
• Publication Number:
  US 20120310626A1
• Time in Patent Office: 1,600 Days
• Field of Search: 704 7- 10, 704/231, 704/270, 704/277
• US Class Current: 1/1
• 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, wherein deriving the path weights is based on a function having one or more first parameters including the candidate word statistics and one or more second parameters including the keyboard error model data;

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

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

presenting the candidate sentences on a user interface component of the device, where the method is performed by one or more hardware processors of the device.

2. The method of claim 1, wherein presenting the candidate sentences comprises:

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, wherein deriving the path weights is based on a function having one or more first parameters including the candidate word statistics and one or more second parameters including the keyboard error model data;

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

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, wherein presenting the candidate sentences 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 trie 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, wherein deriving the path weights is based on a function having one or more first parameters including the candidate word statistics and one or more second parameters including the keyboard error model data;

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

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

12. The system of claim 11, wherein presenting the candidate sentences 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.

16. The system of claim 11, the operations comprise pruning the word lattice by traversing the sequence of keyboard events in a plurality of iterations, including:

for each key of the virtual keyboard hypothesized to have been touched in the sequence of keyboard events, determining a likelihood of the key being touched and discarding a path in the word lattice that corresponds to a candidate word that corresponds to the key upon determining that the likelihood of the key being touched is less than a first threshold; and

for each key of the virtual keyboard hypothesized to have been touched in the sequence of keyboard events, determining an averaged likelihood by averaging the likelihood of the key being touched and an average likelihood determined in a prior iteration, the average likelihood determined in the prior iteration being an average of likelihood associated with one or more previously iterated keys, and discarding a path in the word lattice that corresponds to a candidate word that corresponds to the key upon determining that the average likelihood is less than a second threshold.

17. The system of claim 16, wherein each likelihood is a log likelihood.

18. The system of claim 11, where the hierarchical data structure is a trie data structure comprising a plurality trie nodes, each trie node including a sort keys data field, a probability data field, and a word address data field, the sort keys data field storing a plurality of forms of a character of the language, the probability data field storing data indicating a relative probability that characters associated with the trie node follow characters associated with an ancestor of the trie node, the word address data field storing an address of a location of a first word in a word list with which the trie node is associated.