Method and system for predicting text

• US 8,078,978 B2
• Filed: 11/21/2007
• Issued: 12/13/2011
• Est. Priority Date: 10/19/2007
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Perry, Hagit, Ron, Uri
• Primary Examiner(s): Hailu, Tadeese
• Assistant Examiner(s): ULRICH, NICHOLAS S
• Application Number:
  US11/986,600
• Publication Number:
  US 20090106695A1
• Time in Patent Office: 1,483 Days
• Field of Search: 704/10, 715/259, 715/708, 715/710, 715/745, 715/780, 715/789, 715/811, 715/816, 715/825, 715/752, 706/21, 709/206
• US Class Current: 715/752
• CPC Class Codes: G06F 40/166 Editing, e.g. inserting or deleting
• CPC Class Codes: G06F 40/274 Converting codes to words; Guess-ahead of partial word inputs
• CPC Class Codes: G10L 15/26 Speech to text systems G10L15/08 takes precedence
• CPC Class Codes: Y02D 30/70 in wireless communication networks

Abstract

An electronic messager with a predictive text editor, including a storage unit for storing a data structure associating, for each one of a plurality of a user'"'"'s contacts, usage data for the user'"'"'s history of usage of words in communications with the user contact, a data manager coupled with the storage unit for generating the data structure in the storage unit, and for updating the data structure as additional communications with each user contact are performed and additional usage data is obtained therefrom, and a text predictor coupled with the storage unit, for receiving as input a character string and a designated user contact, and for generating as output an ordered list of predicted words, based on usage data in the data structure associated with the designated user contact. A method is also described and claimed.

Claims

1. An electronic messager with a predictive text editor, comprising:

a receiver for receiving an incoming communication from one of a plurality of a user'"'"'s contacts;

a storage unit for storing a data structure associating, for each one of the plurality of the user'"'"'s contacts, usage data for a history of usage of words in communications with the user contact;

a data manager coupled with said storage unit, for generating the data structure in said storage unit, and for updating the data structure as additional communications with each user contact are conducted and additional usage data is obtained therefrom;

a text predictor coupled with said storage unit, for receiving as input a character string and a designated user contact, and for generating as output an ordered list of predicted words, based on usage data in the data structure associated with the designated user contact; and

a reply generator coupled with said receiver and with said text predictor for generating a reply communication to the incoming communication, by (i) parsing the incoming communication to identify questions, phone numbers and special phrases therein, (ii) presenting possible responses that the user may choose from, based on identified questions, phone numbers and special phrases, and (iii) presenting the ordered list of predicted words for the user to choose from, based on character strings input by the user.

2. The electronic messager of claim 1 wherein the usage data includes statistical frequencies of use of words in communications with each user contact, and wherein the list of predicted words generated by said text predictor is ordered according to frequencies of use.

3. The electronic messager of claim 1 wherein the usage data includes dates and times of use of words in communications with each user contact, and wherein the list of predicted words generated by said text predictor is ordered according to dates and times.

4. The electronic messager of claim 1 wherein the usage data includes statistical frequencies of use of words and dates and times of use of words in communications with each user contact, and wherein the list of predicted words generated by said text predictor is ordered according to scores based on both frequencies of use and dates and times of use.

5. The electronic messager of claim 1 wherein the data structure comprises a tree data structure, the nodes of which contain linked lists of words or of pointers to words.

6. The electronic messager of claim 1 wherein the data structure comprises a tabulated dictionary, the entries of which contain words and their usage data with each user contact.

7. The electronic messager of claim 1 wherein said messager is a cellular telephone.

8. The electronic messager of claim 1 wherein said messager is an SMS messager.

9. The electronic messager of claim 1 wherein said reply generator identifies a question that begins with “

Where”

, and presents a list of locations the user may choose from.

10. The electronic messager of claim 1 wherein said reply generator identifies a question that begins with “

Where”

, and presents a response based on entries in a user scheduler.

11. The electronic messager of claim 1 wherein said reply generator identifies a question that begins with “

Who”

, and presents a list of people the user may choose from.

12. The electronic messager of claim 1 wherein said reply generator identifies a question that begins with “

When”

, and presents a list of dates and times the user may choose from.

13. The electronic messager of claim 1 wherein said reply generator identifies a question that begins with “

When”

, and presents a list of response words the user may choose from, the response words including “

at”

.

14. The electronic messager of claim 1 wherein said reply generator identifies a question that begins with “

Why”

, and presents a list of response words the user may choose from, the response words including “

because”

.

15. The electronic messager of claim 1 wherein said reply generator identifies the phrase “

how are you”

.

16. The electronic messager of claim 1 wherein said reply generator identifies yes/no questions.

17. A method for predicting text while a message is being composed, comprising:

generating a data structure associating, for each one of a plurality of a user'"'"'s contacts, usage data about a history of usage of words in messages sent to and received from the user contact;

updating the data structure as additional messages with each user contact are sent and received, and additional usage data is obtained therefrom;

receiving an incoming message from one of the plurality of the user'"'"'s contacts; and

predicting text while the user is composing a reply to the incoming message, comprising;

parsing the incoming message to identify questions, phone numbers and special phrases therein;

presenting possible responses that the user may choose from, based on the questions, phone numbers and special phrases identified by said parsing;

receiving as input from the user a character string; and

generating as output an ordered list of predicted words, based on usage data in the data structure associated with the user contact from whom the incoming message was received.

18. The method of claim 17 wherein the usage data includes statistical frequencies of use of words in messages sent to and received from each user contact, and wherein said generating orders the list of predicted words according to frequencies of use.

19. The method of claim 17 wherein the usage data includes dates and times of use of words in messages sent to and received from each user contact, and wherein said generating orders the list of predicted words according to dates and times.

20. The method of claim 17 wherein the usage data includes statistical frequencies of use of words and dates and times of use of words in messages sent to and received from each user contact, and wherein said generating orders the list of predicted words according to scores based on both frequencies of use and dates and times of use.

21. The method of claim 17 wherein the data structure comprises a tree data structure, the nodes of which contain linked lists of words or of pointers to words.

22. The method of claim 17 wherein the data structure comprises a tabulated dictionary, the entries of which contain words and their usage data in communications with the each user contact.

23. The method of claim 17 wherein said parsing identifies a question that begins with “

Where”

, and wherein said presenting presents a list of locations the user may choose from.

24. The method of claim 17 wherein said parsing identifies a question that begins with “

Where”

, and wherein said presenting presents a response based on entries in a user scheduler.

25. The method of claim 17 wherein said parsing identifies a question that begins with “

Who”

, and wherein said presenting presents a list of people the user may choose from.

26. The method of claim 17 wherein said parsing identifies a question that begins with “

When”

, and wherein said presenting presents a list of dates and times the user may choose from.

27. The method of claim 17 wherein said parsing identifies a question that begins with “

When”

, and wherein said presenting presents a list of response words the user may choose from, the response words including “

at”

.

28. The method of claim 17 wherein said parsing identifies a question that begins with “

Why”

, and wherein said presenting presents a list of response words the user may choose from, the response words including “

because”

.

29. The method of claim 17 wherein said parsing identifies the phrase “

how are you”

.

30. The method of claim 17 wherein said parsing identifies yes/no questions.