Using language models to expand wildcards

• US 7,277,029 B2
• Filed: 06/23/2005
• Issued: 10/02/2007
• Est. Priority Date: 06/23/2005
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Thiesson, Bo, Church, Kenneth Ward
• Primary Examiner(s): Zimmerman; Brian
• Assistant Examiner(s): Dang; Hung Q
• Application Number:
  US11/159,711
• Publication Number:
  US 20060290535A1
• Time in Patent Office: 831 Days
• Field of Search: 341/22, 704/7, 704/8, 704/9, 704/10, 704/200
• US Class Current: 341/22
• CPC Class Codes: G06F 40/274 Converting codes to words; Guess-ahead of partial word inputs

Abstract

A method of inputting text is provided in which a first portion of an input string is received from a user, the first portion of the input string including at least one keystroke representing a wildcard character of the input string. A second portion of the input string is then received, with the second portion including one or more keystrokes all representing non-wildcard characters of the input string.

Claims

1. A method of inputting text using a mobile device with a limited character keypad having multiple different letters associated with each of a plurality of numbered keys, the method comprising:

receiving from a user a first portion of an input string comprising at least one keystroke on the limited character keypad, the first portion of the input string representing at least one wildcard character;

receiving from the user a second portion of the input string comprising at least one keystroke on the limited character keypad, after the first portion of the input string representing the at least one wildcard character, with all keystrokes of the second portion representing non-wildcard characters; and

after receiving the second portion of the input string, further comprising automatically inserting an additional wildcard character at the end of the input string after receiving the second portion of the input string.

2. The method of claim 1, and after receiving the second portion of the input string, further comprising receiving from the user a third portion of the input string comprising a keystroke on the limited character keypad representing an additional wildcard character at the end of the input string.

3. The method of claim 1, and further comprising using a language model to perform wildcard expansion to identify k-best text matches corresponding to the input string containing the at least one wildcard character.

4. The method of claim 3, and further comprising displaying on the mobile device at least a plurality of the k-best text matches corresponding to the input string containing the at least one wildcard character.

5. The method of claim 4, and further comprising receiving a user input selecting one of the k-best text matches as the text to input.

6. The method of claim 5, wherein the k-best text matches, corresponding to the input string containing the at least one wildcard character, are identified from an index of possible text matches based on scores determined using the language model.

7. The method of claim 5, wherein the language model is a trigram language model.

8. The method of claim 7, wherein the language model uses a Golomb code.

9. The method of claim 5, wherein receiving from the user the first and second portions of the input string comprises receiving the first and second portions of the input string using at least one of a multiple-tap input technique and a single-tap technique on the limited character keypad.

10. The method of claim 5, and further comprising displaying, as the first and second portions of the input string are received, text matches in a word wheeling format.

11. A portable electronic device configured to implement the method of claim 1.

12. A computer-readable medium having computer-executable instructions stored thereon for implementing the steps of method claim 1.

13. A method of inputting text, the method comprising:

receiving from a user a first portion of an input string comprising at least one keystroke, the first portion of the input string representing at least one wildcard character;

receiving from the user a second portion of the input string comprising at least one keystroke, after the first portion of the input string representing the at least one wildcard character, with all keystrokes of the second portion representing non-wildcard characters;

after receiving the second portion of the input string, automatically inserting an additional wildcard character at the end of the input string;

using a language model to perform wildcard expansion to identify k-best text matches corresponding to the input string containing the at least one wildcard character;

displaying to the user a plurality of the k-best text matches corresponding to the input string containing the at least one wildcard character, further comprising displaying, as the first and second portions of the input string are received, text matches in a word wheeling format; and

selecting one of the k-best text matches, as the text to input, in response to a user input.

14. The method of claim 13, and after receiving the second portion of the input string, further comprising receiving from the user a third portion of the input string comprising a keystroke representing an additional wildcard character at the end of the input string.

15. The method of claim 13, wherein the k-best text matches, corresponding to the input string containing the at least one wildcard characters, are identified from an index of possible text matches based on scores determined using the language model.