Spelling correction for two-way mobile communication devices

• US 6,556,841 B2
• Filed: 05/03/1999
• Issued: 04/29/2003
• Est. Priority Date: 05/03/1999
• Status: Expired due to Term

• Current Assignee: Unwired Planet LLC (JP Morgan Chase & Co)
• Original Assignee: Openwave Systems Incorporated (JP Morgan Chase & Co)
• Inventors: Yu, Francis H.
• Primary Examiner(s): Trost, William
• Assistant Examiner(s): Nguyen, Simon
• Application Number:
  US09/304,428
• Publication Number:
  US 20030017844A1
• Time in Patent Office: 1,457 Days
• Field of Search: 455/66, 455/412, 455/414, 455/466, 455/575, 455/556, 707/530-537, 341/23, 341/28
• US Class Current: 455/556.1
• CPC Class Codes: G06F 3/0237 using prediction or retrieval techniques
• CPC Class Codes: H04M 1/2748 by matching character strings
• CPC Class Codes: H04M 1/72436 for text messaging, e.g. short messaging services [SMS] or e-mails

Abstract

An apparatus and method for implementing spelling error detection and correction for a two-way mobile communication device. The two-way mobile communication device has a display screen and a telephone-type keypad (e.g., keys 0-9, “*”, “#”, etc.) with the characters mapped onto each key in a many to one fashion. According to one embodiment, when the end of a character string (e.g., a word) is indicated by the input of a termination symbol (e.g., a space or “#”) then that character string is compared to a plurality of character strings stored in a dictionary. If no match is found for the character string in the dictionary, then it assumed that the character string is misspelled. Individual character elements of the subject character string are then systematically replaced by character elements mapped to the same key, and then each combination is compared to the entries resident in the dictionary. Matching character strings are retrieved and presented to the user for examination and selection or, if so desired, the most likely matching character string can automatically replace the misspelled character string.

Claims

1. A method for spell checking and correcting of character strings input to a mobile device through use of keys of the mobile device, said method comprising the operations of:

(a) receiving a character input, the character input uniquely identifying a character;

(b) determining whether the character input is a predetermined delimiter character;

(c) adding the character input to a character string when said determining (b) determines that the character input is not the predetermined delimiter character;

(d) performing an initial dictionary look-up for the character string only after said determining (b) determines that the character input is the delimiter character;

(e) performing character substitutions on at least one character in the character string to produce a modified character string when said performing (d) of the initial dictionary look-up does not locate the character string, the character substitutions being limited to other characters mapped to a common key of the keys of the mobile device; and

(f) performing a subsequent dictionary look-up for the modified character string following said performing (e) of the character substitutions.

2. A method as recited in claim 1, wherein the mobile device includes a display screen, and

wherein said method further comprises the operation of:

(g) displaying the modified character string on the display screen when said performing (d) of the subsequent dictionary look-up does locate the modified character string.

3. A method as recited in claim 2,

wherein said performing (e) of the character substitutions produces a plurality of modified character strings, and

wherein said performing (f) of the subsequent dictionary look-up operates to look-up each of the plurality of modified character strings.

4. A method as recited in claim 3, wherein said performing (e) operates to provide one or more character substitutions on each character in the character string to produce the plurality of modified character strings.

5. A method as recited in claim 3, wherein said displaying (g) operates to display those of the plurality of modified character strings that are located by the subsequent dictionary look-up.

6. A method as recited in claim 5, wherein said method further comprises the operations of:

(h) receiving a selection of one of the modified character strings being displayed on the display screen; and

(i) replacing the selected one of the modified character strings with the character string.

7. A method as recited in claim 1, wherein the character substitutions are further limited by processing rules.

8. A method as recited in claim 7, wherein the processing rules operate to further limit the character substitutions based on probabilities.

9. A method as recited in claim 1, wherein the ordering of the character substitutions is determined based on probabilities.

10. A method for performing spelling error detection and correction for a two-way mobile communication device having a display screen and a telephone-type keypad, where input characters are mapped onto the keys in a many to one fashion, said method comprising:

storing a plurality of acceptable character strings and associated information within an on-board dictionary resident within the two-way mobile communication device;

receiving an input character string where an end of the input character string is indicated by a termination character;

comparing the received input character string to the acceptable character strings and providing an indication when a character string substantially matching the received input character string is not found within the on-board dictionary;

thereafter replacing the individual characters of the received input character string for which no substantial matches were found with characters mapped to the same key of the telephone-type keypad to generate a plurality of associated character strings; and

comparing the associated character strings to the acceptable character strings to identify those of the associated character strings that substantially match the acceptable character strings within the on-board dictionary.

11. A method as described in claim 10, further comprising:

displaying the identified associated character strings that substantially match the acceptable character strings on the display screen of the two-way mobile communication device;

receiving a selection input relating to one of the identified associated character strings; and

replacing the input character string for which no substantial matches were found with the selected one of the identified associated character strings.

12. A method as recited in claim 10, wherein said associated information is comprised of word usage percentages and spelling rules.

13. A method as recited in claim 12, wherein said word usage percentages and spelling rules are utilized to minimize the number of associated character strings.

14. A method as recited in claim 10, wherein said method further comprises:

replacing the character string for which no substantial matches were found with the associated character string having a highest usage percentage.

15. A method as recited in claim 10, wherein said comparing the associated character strings to the acceptable character strings is limited by reducing the characters mapped to the same key that are available for replacement.

16. A method as recited in claim 10, wherein said replacing of the individual characters of the input character string for which no substantial matches were found with the characters mapped to the same key of the telephone-type keypad to generate the associated character strings only utilizes those of the characters mapped to the same key that meet a pre-determined statistical threshold.

17. A method as recited in claim 10, wherein the termination character is generated by a predetermined key resident on the telephone-type keypad.

18. A computer readable media including computer program code for spell checking and correcting of character strings input to a mobile device through use of keys of the mobile device, said computer readable media comprising:

computer program code for receiving a character input, the character input uniquely identifies a character;

computer program code for determining whether the character input is a predetermined delimiter character;

computer program code for adding the character input to a character string only after said computer program code for determining determines that the character input is not the predetermined delimiter character;

computer program code for performing an initial dictionary look-up for the character string when said computer program code for determining determines that the character input is the delimiter character;

computer program code for performing character substitutions on at least one character in the character string to produce a modified character string when said computer program code for performing of the initial dictionary look-up does not locate the character string, the character substitutions being limited to other characters mapped to a common key of the keys of the mobile device; and

computer program code for performing a subsequent dictionary look-up for the modified character string following said computer program code for performing of the character substitutions.

19. A computer readable media as recited in claim 18, wherein the mobile device includes a display screen, and

wherein said computer readable media further comprises:

computer program code for displaying the modified character string on the display screen when said computer program code for performing of the subsequent dictionary look-up does locate the modified character string.

20. A computer readable media as recited in claim 19,

wherein said computer program code for performing of the character substitutions produces a plurality of modified character strings, and

wherein said computer program code for performing of the subsequent dictionary look-up operates to look-up each of the plurality of modified character strings.

21. A computer readable media as recited in claim 20, wherein said computer program code for performing operates to provide one or more character substitutions on each character in the character string to produce the plurality of modified character strings.

22. A computer readable media as recited in claim 20, wherein said computer program code for displaying operates to display those of the plurality of modified character strings that are located by the subsequent dictionary look-up.

23. A computer readable media as recited in claim 22, wherein said computer readable media further comprises:

computer program code for receiving a selection of one of the modified character strings being displayed on the display screen; and

computer program code for replacing the selected one of the modified character strings with the character string.

24. A computer readable media as recited in claim 18, wherein the character substitutions are further limited by processing rules.

25. A computer readable media as recited in claim 24, wherein the processing rules operate to further limit the character substitutions based on probabilities.

26. A computer readable media as recited in claim 18, wherein the ordering of the character substitutions is determined based on probabilities.

27. A wireless two-way interactive communication device, comprising:

a display screen;

a telephone-type keypad, where the characters are mapped onto the keys in a many to one fashion;

a storage device for storing a plurality of acceptable character strings and associated information within an on-board dictionary resident within said two-way mobile communication device;

a memory for storing program code for a processor;

a processor coupled to said storage device and said memory, said processor operates to execute said program code stored in said memory to identify input character strings which do not correspond to at least one of the acceptable character strings in said storage device, to generate replacement character strings for said identified input character strings using replacement characters being mapped to the same key as the character in said identified input character string being replaced, and then to identify those of the replacement character strings that correspond to at least one of the acceptable character strings in said storage device, and

wherein the identified character strings being input include only uniquely identified characters.

28. A wireless two-way interactive communication device as recited in claim 27, wherein said wireless two-way interactive communication device is a hand-held device, and wherein said display screen has a limited size.

29. A wireless two-way interactive communication device as recited in claim 27, wherein said wireless two-way interactive communication device is selected from a group consisting of mobile telephones, Personal Digital Assistants (PDA) and Palm-Sized Computing Devices.