# US 2008/0167858 A1 · Method and system for providing word recommendations for text input

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2008/0167858 A1
- Document ID: US20080167858A1
- Status: Published application
- Kind: A1
- Application number: 11/620,641
- Filed: 2007-01-05
- Published: 2008-07-10
- Earliest claimed: 2007-01-05
- Assignees: Apple Inc.
- Inventors: Greg Christie; Bas Ording; Scott Forstall; Kenneth Kocienda; Richard Williamson; Jerome Rene Bellegarda
- Web page: https://patentgrep.com/patent/US20080167858A1

## CPC

- G06F 3/0237: {using prediction or retrieval techniques}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Word recommendations are provided in response to text input. For a particular text input, possible word recommendations are identified based on the characters of the input and corresponding neighbor characters on a keyboard layout. The possible word recommendations are scored based on how closely they match the input word on a character-by-character basis, and a subset of the possible word recommendations are selected for presentation to the user.

## Claims

### Claim 1

A computer-implemented method, comprising:
receiving a sequence of input characters from a keyboard, wherein the keyboard has a predefined layout of characters with each character in the layout having one or more neighbor characters;
generating a set of strings from at least a subset of the sequence of input characters, the set of strings comprising permutations of respective input characters in the subset of the sequence and neighbor characters of the respective input characters on the layout of the keyboard;
identifying in a dictionary one or more candidate words, each candidate word having a string in the set of strings as a prefix;
scoring the candidate words;
selecting a subset of the candidate words based on predefined criteria; and
presenting the subset of the candidate words.

### Claim 2 (depends on 1)

The method of claim 1, wherein scoring a respective candidate word comprises:
comparing a respective character in each character position of the candidate word with a respective character in a corresponding position in the sequence of input characters; and
determining a score for the respective candidate word based on the comparing.

### Claim 3 (depends on 2)

The method of claim 2, wherein scoring the respective candidate word further comprises increasing the score of the respective candidate word if the respective candidate word, compared to the sequence of input characters, has only one character that is different.

### Claim 4 (depends on 2)

The method of claim 2, wherein scoring the respective candidate word further comprises increasing the score of the respective candidate word if the respective candidate word, compared to the sequence of input characters, has only a set of transposed characters that are different.

### Claim 5 (depends on 1)

The method of claim 1, wherein the keyboard comprises a virtual keyboard.

### Claim 6 (depends on 1)

The method of claim 1, wherein the dictionary comprises a list of words and associated usage frequency rankings.

### Claim 7 (depends on 6)

The method of claim 6, wherein the associated usage frequency rankings are tailored to the user based on previous input from the user.

### Claim 8 (depends on 6)

The method of claim 6, wherein selecting a subset of the candidate words comprises organizing the candidate words into a first group and a second group, the first group comprising the candidate words having respective usage frequency rankings that exceed a threshold, the second group comprising the candidate words having respective usage frequency rankings that do not exceed the threshold; and
wherein presenting the subset of the candidate words comprises presenting one or more of the candidate words of the first group in an order based on their scores.

### Claim 9 (depends on 8)

The method of claim 8, wherein selecting a subset of the candidate words further comprises adding a candidate word of the second group into the first group if the candidate word of the second group has a score that exceeds a score of the highest scoring candidate word of the first group by a predefined margin.

### Claim 10 (depends on 8)

The method of claim 8, wherein presenting the subset of the candidate words further comprises presenting a highest scoring candidate word of the second group.

### Claim 11 (depends on 1)

The method of claim 1, further comprising presenting the sequence of input characters as a candidate word.

### Claim 12 (depends on 1)

The method of claim 1, wherein the keyboard comprises a physical keyboard.

### Claim 13

A computer program product for use in conjunction with a portable communications device, the computer program product comprising a computer readable storage medium and a computer program mechanism embedded therein, the computer program mechanism comprising:
instructions for receiving a sequence of input characters from a keyboard, wherein the keyboard has a predefined layout of characters with each character in the layout having one or more neighbor characters;
instructions for generating a set of strings from at least a subset of the sequence of input characters, the set of strings comprising permutations of respective input characters in the subset of the sequence and neighbor characters of the respective input characters on the layout of the keyboard;
instructions for identifying in a dictionary one or more candidate words, each candidate word having a string in the set of strings as a prefix;
instructions for scoring the candidate words;
instructions for selecting a subset of the candidate words based on predefined criteria; and
instructions for presenting the subset of the candidate words.

### Claim 14

A portable communications device, comprising:
a display;
a keyboard, the keyboard having a predefined layout of characters with each character in the layout having one or more neighbor characters;
one or more processors;
memory; and
a program, wherein the program is stored in the memory and configured to be executed by the one or more processors, the program including:
instructions for receiving a sequence of input characters from the keyboard;
instructions for generating a set of strings from at least a subset of the sequence of input characters, the set of strings comprising permutations of respective input characters in the subset of the sequence and neighbor characters of the respective input characters on the layout of the keyboard;
instructions for identifying in a dictionary one or more candidate words, each candidate word having a string in the set of strings as a prefix;
instructions for scoring the candidate words;
instructions for selecting a subset of the candidate words based on predefined criteria; and
instructions for presenting the subset of the candidate words.

### Claim 15

A portable communications device, comprising:
display means;
input means, the input means having a predefined layout of characters, each character in the layout having one or more neighbor characters;
one or more processor means;
memory means; and
a program mechanism, wherein the program mechanism is stored in the memory means and configured to be executed by the one or more processors means, the program mechanism including:
instructions for receiving a sequence of input characters from the input means;
instructions for generating a set of strings from at least a subset of the sequence of input characters, the set of strings comprising permutations of respective input characters in the subset of the sequence and neighbor characters of the respective input characters on the layout of the input means;
instructions for identifying in a dictionary one or more candidate words, each candidate word having a string in the set of strings as a prefix;
instructions for scoring the candidate words;
instructions for selecting a subset of the candidate words based on predefined criteria; and
instructions for presenting the subset of the candidate words.

### Claim 16

A computer-implemented method, comprising:
receiving a sequence of individual touch points input by a user that form a user-input directed graph;
comparing the user-input directed graph to respective directed graphs for words in a dictionary;
generating a list of candidate words based at least in part on the comparing step; and
presenting at least some of the candidate words to the user.

### Claim 17 (depends on 16)

The method of claim 16, wherein the sequence of individual touch points is input by the user on a touch screen of a portable electronic device.

### Claim 18 (depends on 16)

The method of claim 16, wherein generating a list of candidate words is based at least in part on the usage frequency of the candidate words.

### Claim 19 (depends on 16)

The method of claim 16, wherein generating a list of candidate words is based at least in part on one or more words previously typed by the user.

### Claim 20 (depends on 16)

The method of claim 16, wherein the dictionary comprises a list of words and associated usage frequency rankings.

### Claim 21 (depends on 20)

The method of claim 20, wherein the associated usage frequency rankings are tailored to the user based on previous input from the user.

### Claim 22

A computer program product for use in conjunction with a portable communications device, the computer program product comprising a computer readable storage medium and a computer program mechanism embedded therein, the computer program mechanism comprising:
instructions for receiving a sequence of individual touch points input by a user that form a user-input directed graph;
instructions for comparing the user-input directed graph to respective directed graphs for words in a dictionary;
instructions for generating a list of candidate words based at least in part on the comparing step; and
instructions for presenting at least some of the candidate words to the user.

### Claim 23

A portable communications device, comprising:
a display;
a keyboard;
one or more processors;
memory; and
a program, wherein the program is stored in the memory and configured to be executed by the one or more processors, the program including:
instructions for receiving a sequence of individual touch points input by a user that form a user-input directed graph;
instructions for comparing the user-input directed graph to respective directed graphs for words in a dictionary;
instructions for generating a list of candidate words based at least in part on the comparing step; and
instructions for presenting at least some of the candidate words to the user.

### Claim 24

A portable communications device, comprising:
means for receiving a sequence of individual touch points input by a user that form a user-input directed graph;
means for comparing the user-input directed graph to respective directed graphs for words in a dictionary;
means for generating a list of candidate words based at least in part on the comparing step; and
means for presenting at least some of the candidate words to the user.
