Method and system for disambiguation and predictive resolution

• US 7,376,938 B1
• Filed: 03/12/2004
• Issued: 05/20/2008
• Est. Priority Date: 03/12/2004
• Status: Expired due to Fees

• Current Assignee: Cerence Operating Company (Cerence Inc.)
• Original Assignee: Steven Van Der Hoeven
• Inventors: Van der Hoeven, Steven
• Primary Examiner(s): CHAVIS, JOHN Q
• Application Number:
  US10/800,203
• Time in Patent Office: 1,530 Days
• Field of Search: 717/136, 715/533, 700/44
• US Class Current: 717/136
• CPC Class Codes: G06F 8/427 Parsing

Abstract

Apparatuses, methods and systems for the efficient entry of data on a device with a restricted set of input channels are disclosed. These apparatuses, systems and methods may employ a user interface which allows efficient entry of input. This interface may be tailored according to the device with which it is used, and the semantic meaning associated with the interface. To assist in the efficient entry of data, these apparatuses, systems and methods may disambiguate user input, provide an efficient way to specify the input exactly, or predict user input. These apparatuses, systems and methods may also adapt to the proclivities of a certain user, and incorporate user defined abbreviations and synonyms for frequently used inputs.

Claims

1. A method for efficient text input, comprising:

formulating a plurality of candidates based on a prefix and an input, wherein each candidate comprises a set of symbols and a score, the score calculated based upon one of a plurality of symbols associated with the input and the prefix, and the set of symbols associated with the candidate corresponds to the prefix and the one of the plurality of symbols associated with the input;

formulating a set of predictions based on the set of symbols associated with the candidate with a first highest score, wherein the prediction comprises one or more predictive completions associated with the set of symbols of the candidate and each of the set of predictions is associated with a score;

formulating a proposition based on the candidate or the prediction; and

presenting the proposition to a user.

2. The method of claim 1, wherein the prefix is empty, entered by a user, or a previous proposition.

3. The method of claim 1, wherein the score of the candidate is based on a score of the prefix concatenated with the input.

4. The method of claim 3, wherein the score of the candidate is based on a score of the input combined with the score of the prefix.

5. The method of claim 4, wherein the candidate is one of a set of candidates where the score of each of the candidates in the set is above a threshold.

6. The method of claim 5, wherein formulating a candidate further comprises ranking the set of candidates based upon the score of each of the candidates.

7. The method of claim 6, wherein formulating a candidate is based on a language model.

8. The method of claim 7, wherein the score of the candidate is based on a string which is the longest string in the language model which is a extension of the prefix.

9. The method of claim 1, wherein the prediction is one of a set of predictions.

10. The method of claim 9, wherein formulating a prediction is based on a usage model.

11. The method of claim 10, wherein each of the set of predictions is a sequence corresponding to a path through a tree starting from a node based on the candidate and ending with a terminal node.

12. The method of claim 11, wherein formulating a prediction comprises scoring each of the predictions based on frequency of appearance, length of the path through the tree, or the candidate.

13. The method of claim 9, further comprising determining a set of synonyms for the prediction.

14. The method of claim 13, wherein the set of synonyms is based on the terminal node of the prediction in the tree.

15. The method of claim 14, wherein the set of synonyms is stored in the terminal node.

16. The method of claim 14, further comprising scoring each of the set of synonyms based on a score of the prediction and the score of the candidate on which each synonym is based.

17. The method of claim 16, further comprising ranking the set of synonyms.

18. The method of claim 17, further comprising storing the set of synonyms, the set of predictions and a set of candidates, wherein the set synonyms, the set of candidates, and the set of predictions are ranked.

19. A computer readable medium having code for efficient text input, wherein the code is embodied within computer readable medium, the code comprising instructions translatable for:

formulating a plurality of candidates based on a prefix and an input, wherein each candidate comprises a set of symbols and a score, the score calculated based upon one of a plurality of symbols associated with the input and the prefix, and the set of symbols associated with the candidate corresponds to the prefix and the one of the plurality of symbols associated with the input;

formulating a set of predictions based on the set of symbols associated with the candidate with a first highest score, wherein the prediction comprises one or more predictive completions associated with the set of symbols of the candidate and each of the set of predictions is associated with a score;

formulating a proposition based on the candidate or the prediction; and

presenting the proposition to a user.

20. The computer readable medium of claim 19, wherein the prefix is empty, entered by a user, or a previous proposition.

21. The computer readable medium of claim 19, wherein the score of the candidate is based on a score of the prefix concatenated with the input.

22. The computer readable medium of claim 21, wherein the score of the candidate is based on a score of the input combined with the score of the prefix.

23. The computer readable medium of claim 22, wherein the candidate is one of a set of candidates where the score of each of the candidates in the set is above a threshold.

24. The computer readable medium of claim 23, wherein formulating a candidate further comprises ranking the set of candidates based upon the score of each of the candidates.

25. The computer readable medium of claim 24, wherein formulating a candidate is based on a language model.

26. The computer readable medium of claim 25, wherein the score of the candidate is based on a string which is the longest string in the language model which is a extension of the prefix.

27. The computer readable medium of claim 19, wherein the prediction is one of a set of predictions.

28. The computer readable medium of claim 27, wherein formulating a prediction is based on a usage model.

29. The computer readable medium of claim 28, wherein each of the set of predictions is a sequence corresponding to a path through a tree starting from a node based on the candidate and ending with a terminal node.

30. The computer readable medium of claim 29, wherein formulating a prediction comprises scoring each of the predictions based on frequency of appearance, length of the path through the tree, or the candidate.

31. The computer readable medium of claim 27, further comprising instructions for determining a set of synonyms for the prediction.

32. The computer readable medium of claim 31, wherein the set of synonyms is based on the terminal node of the prediction in the tree.

33. The computer readable medium of claim 32, wherein the set of synonyms is stored in the terminal node.

34. The computer readable medium of claim 32, further comprising instructions for scoring each of the set of synonyms based on a score of the prediction and the score of the candidate on which each synonym is based.

35. The computer readable medium of claim 34, further comprising instructions for ranking the set of synonyms.

36. The computer readable medium of claim 35, further comprising instructions for storing the set of synonyms, the set of predictions and a set of candidates, wherein the set of synonyms, the set of candidates, and the set of predictions are ranked.

37. A system for efficient multilingual text input, comprising:

a device comprising;

an input means comprising a set of zones, each zone associated with a plurality of symbols; and

a processor operable to execute instructions on a computer readable medium, the instruction operable for;

formulating a plurality of candidates based on a prefix and an input associated with one of the set of zones, wherein each candidate comprises a set of symbols and a score, the score calculated based upon one of a plurality of symbols associated with the input and the prefix, and the set of symbols associated with the candidate corresponds to the prefix and the one of the plurality of symbols associated with the input;

formulating a set of predictions based on the set of symbols associated with the candidate with a first highest score, wherein the prediction comprises one or more predictive completions associated with the set of symbols of the candidate and each of the set of predictions is associated with a score;

formulating a proposition based on the candidate or the prediction; and

presenting the proposition to a user.

38. The system of claim 37, wherein the prefix is empty, entered by a user, or a previous proposition.

39. The system of claim 37, wherein the score of the candidate is based on a score of the prefix concatenated with the input.

40. The system of claim 39, wherein the score of the candidate is based on a score of the input combined with the score of the prefix.

41. The system of claim 40, wherein the candidate is one of a set of candidates where the score of each of the candidates in the set is above a threshold.

42. The system of claim 41, wherein formulating a candidate further comprises ranking the set of candidates based upon the score of each of the candidates.

43. The system of claim 42, wherein formulating a candidate is based on a language model.

44. The system of claim 43, wherein the score of the candidate is based on a string, wherein the string is the longest string in the language model which is a extension of the prefix.

45. The system of claim 37, wherein the prediction is one of a set of predictions.

46. The system of claim 45, wherein formulating a prediction is based on a usage model.

47. The system of claim 46, wherein each of the set of predictions is a sequence corresponding to a path through a tree starting from a node based on the candidate and ending with a terminal node.

48. The system of claim 47, wherein formulating a prediction comprises scoring each of the predictions based on frequency of appearance and length of the path through the tree.

49. The system of claim 45, wherein the device is further operable for determining a set of synonyms for the prediction.

50. The system of claim 49, wherein the set of synonyms is based on the terminal node of the prediction in the tree.

51. The system of claim 50, wherein the set of synonyms is stored in the terminal node.

52. The system of claim 50, wherein the device is further operable for scoring each of the set of synonyms based on a score of the prediction and the score of the candidate on which each synonym is based.

53. The system of claim 52, wherein the device is further operable for ranking the set of synonyms.

54. The system of claim 53, wherein the device is further operable for storing the set of synonyms, the set of predictions and a set of candidates, wherein the set of synonyms, the set of candidates, and the set of predictions are ranked.

55. A method for efficient multilingual text input, comprising:

formulating a set of candidates based on a prefix and an input, wherein each candidate comprises a set of symbols and a score, the score for the candidate is calculated based upon one of a plurality of symbols associated with the input and the prefix and the set of symbols associated with the candidate corresponds to the prefix and the one of the plurality of symbols associated with the input;

determining a set of predictions based on the candidate associated with a first highest score, wherein the set of predictions comprises one or more predictive completions associated with the set of symbols of the candidate and each of the set of predictions is associated with a score;

formulating a proposition based upon the prediction with a second highest score; and

presenting the proposition to a user.