Method for predicting keystroke characters on single pointer keyboards and apparatus therefore

• US 6,621,424 B1
• Filed: 02/18/2000
• Issued: 09/16/2003
• Est. Priority Date: 02/18/2000
• Status: Expired due to Term

• Current Assignee: CDN Innovations, LLC (IP Investments Group LLC)
• Original Assignee: Mitsubishi Electric Research Laboratories, Inc. (Mitsubishi Electric Corporation)
• Inventors: Brand, Matthew
• Primary Examiner(s): Edwards, Timothy
• Assistant Examiner(s): Dang, Hung Q
• Application Number:
  US09/506,609
• Time in Patent Office: 1,306 Days
• Field of Search: 341/22, 341/28, 341/23, 400/109, 400/110, 400/484
• US Class Current: 341/22
• CPC Class Codes: G06F 3/0237 using prediction or retrieval techniques

Abstract

Keystrokes on a keyboard are predicted by constructing a model from a training corpus. The training corpus includes symbol sequences. The model predicts a set of symbols, where each symbol of the set continues a particular symbol sequence using variable-length subsequences of the particular symbol sequence. A particular length is chosen to maximize a probability that the predicting is correct. Keys on the keyboard are highlighted. The highlighted keys correspond to selected symbols in the set of symbols.

Claims

1. A method for predicting keystrokes on a keyboard, comprising the steps of:

constructing a model from a training corpus including symbol sequences, wherein symbols in the model are stored in a reverse order of occurrence of the symbols;

predicting a set of symbols by traversing the model from a root node backwards once, through the reverse order of occurrence of the symbols, each symbol of the set continuing a particular symbol sequence using variable-length subsequences of the particular symbol sequence, a particular length of the subsequences chosen to maximize a probability that the predicting is correct;

highlighting keys on the keyboard, the highlighted keys corresponding to selected symbols of the predicted set of symbols.

2. The method of claim 1 wherein the model is a variable memory length Markov model.

3. The method of claim 2 wherein each node of the Markov model stores a symbol and an order of associated probability.

4. The method of claim 1 wherein the constructing further comprises the steps of:

assigning a probability of 1.0 to the root node of the model, the root node having a default “

null”

symbol;

constructing a first layer of nodes connected to the root node, each node of the first layer representing a unique symbol of the training corpus and a probability of the frequency that the symbol appears in the training corpus;

reexamining the training corpus according to the model to construct a next layer, each node in the next layer representing a particular symbol preceding a connected node in the first layer and a probability of the frequency that the particular symbol precedes the connected node; and

repeating the reexamination of the training corpus and the constructing of the next layer until a termination condition is reached.

5. The method of claim 4 further comprising the step of:

pruning the particular node in the model when the particular node has a probability less than a predetermined threshold.

6. The method of claims 1 wherein the model is a decision tree.

7. The method of claims 1 wherein the model is a decision tree, and wherein redundant nodes are pruned.

8. The method of claim 6 wherein each node of the decision tree stores a current symbol and an ordered set of predicted symbols.

9. The method of claim 6 wherein the decision tree is derived from a variable memory length Markov model.

10. A predictive keyboard, comprising:

a memory storing a model constructed from a training corpus including symbol sequences, wherein symbols in the model are stored in a reverse order of occurrence of the symbols, the model predicting a set of symbols by traversing the model backwards once, from a root node through the reverse order of occurrence of the symbols, each symbol of the set continuing a particular symbol sequence using variable-length subsequences of the particular symbol sequence, a particular length chosen to maximize a probability that the predicting is correct;

a plurality of keys; and

means for highlighting particular keys, the highlighted keys corresponding to selected symbols of the set of symbols.

11. A method for predicting keystrokes on a keyboard from a sequence of typed symbols, comprising the steps of:

constructing a decision tree where a root node has a set of most frequently occurring symbols in a training corpus, and each node in each next layer storing an ordered set of symbols that would precede symbols of a node of a previous layer;

traversing the decision tree once to predict probable next symbols to be typed, the searching beginning at the root and proceeding in a reverse order to find a sequence of symbols in the decision tree that matches a subset of the sequence of the typed symbols; and

highlighting keys on the keyboard, the highlighted keys corresponding to the probable next symbols.