Reduced keyboard disambiguating system

• US 6,307,548 B1
• Filed: 09/24/1998
• Issued: 10/23/2001
• Est. Priority Date: 09/25/1997
• Status: Expired due to Term

• Current Assignee: Nuance Communications, Inc. (Microsoft Corporation)
• Original Assignee: Tegic Communications, Inc. (Microsoft Corporation)
• Inventors: Grunbock, Cheryl, Grover, Dale, Kushler, Clifford A., King, Martin T., Flinchem, Edward P.
• Primary Examiner(s): Huynh, Ba
• Application Number:
  US09/160,433
• Time in Patent Office: 1,125 Days
• Field of Search: 345/168, 345/169, 345/171, 345/173, 345/179, 345/352, 345/353, 345/354, 704/2-4, 704/8, 704/9, 704/10, 707/532, 707/533, 707/534, 707/535, 707/536, 341/20, 341/22, 341/28, 710/67, 710/68, 710/73, 400/110, 400/484
• US Class Current: 715/811
• CPC Class Codes: G06F 3/0237 using prediction or retrieval techniques

Abstract

A reduced keyboard disambiguating system. The keyboard has twelve to sixteen keys, nine of them labeled with numerous letters and other symbols, and those nine plus one more are associated each with one of the ten digits. Textual entry keystrokes are ambiguous. The user strikes a delimiting “Select” key, or a key with an unambiguous character interpretation, at the end of each word, delimiting a keystroke sequence that could match any of a plurality of words associated with the same keystroke sequence. Each input keystroke sequence is processed with a complete vocabulary, and words which match the sequence of keystrokes are presented to the user in order of decreasing frequency of use. The vocabulary is stored in a special format that supports significant data compression without requiring additional processing. In addition, stems of longer words whose initial letters match the sequence of keystrokes are also presented to the user in order of decreasing frequency of use. If the frequency of the words associated with a stem is high enough, that stem is displayed as the default word object. Activations of an ambiguous key associated with a plurality of punctuation characters are disambiguated from the context of the surrounding keystrokes.

Claims

1. A disambiguating system for disambiguating ambiguous input sequences entered by a user, the disambiguating system comprising:

(a) a user input device having a plurality of inputs, each of the plurality of inputs associated with a plurality of characters, wherein an input sequence has a textual interpretation that is ambiguous due to the plurality of characters associated with each input;

(b) a memory containing data used to construct a plurality of objects, each of the plurality of objects having a numerical index and being associated with an input sequence and a relative frequency of use, all objects being stored in the memory in a tree structure comprised of a plurality of parent and child nodes, each node being associated with an input sequence and with one or more objects, with each parent node having a base input sequence, the plurality of nodes being connected by a plurality of paths, each of the plurality of paths linking a parent node associated with a base input sequence with a child node associated with the base input sequence of the parent node and an additional input; and

wherein the objects associated with a child node are based on the objects associated with the corresponding parent node to which the child node is linked and are constructed using a code pre-stored in memory to modify objects associated with the corresponding parent node, the code used to construct objects associated with a child node modifying objects associated with the corresponding parent node and comprising a specification of a numerical index of the object associated with the corresponding parent node and a specification of a numerical index of one of the characters associated with the additional input linking the parent node to the child node;

said memory tree structure being arranged to eliminate redundant parent nodes, two parent nodes of the tree being redundant in the event that all codes associated with a given input sequence that are present in both of the two parent nodes are identical in that the codes occur in the same sequence and specify the same numerical object index and the same numerical character index and, further, for all inputs for which child nodes are linked to each of the two parent nodes said child nodes are also redundant in the same recursive sense, one of said redundant parent nodes being omitted from the tree structure in memory and the remaining redundant parent node being augmented by any codes and links to child nodes that were present only in the omitted redundant parent node, all links from any parent node of which the omitted parent node is a child being re-written as links to the remaining redundant parent node;

(c) a display to depict system output to the user; and

(d) a processor coupled to the user input device, memory and display, the processor;

(i) identifying from the one or more objects in the memory associated with each generated input sequence at least one candidate object with the highest frequency of use, the candidate object being a word object when at least one word object is associated with the generated input sequence and being a word stem object when no word object is associated with the generated input sequence; and

(ii) generating an output signal causing the display to display the at least one identified candidate object associated with each generated input sequence as a textual interpretation of the generated input sequence.

2. The system of claim 1, in which one or more characters which include special diacritic marks are associated with the same input with which the corresponding character without special diacritic marks is associated.

3. The system of claim 2, in which the one or more characters which include special diacritic marks do not appear on the input associated with the corresponding character without special diacritic marks.

4. The system of claim 1, wherein the at least one identified candidate object with the highest frequency of use that is displayed as a textual interpretation of the generated input sequence is a word stem object when the frequency of use of said word stem object exceeds by a predetermined factor the highest frequency of use associated with any word object associated with the generated input sequence, and where said highest frequency of use associated with any word object associated with the generated input sequence does not exceed a predetermined threshold.

5. The system of claim 1, wherein the at least one object with the highest frequency of use that is provisionally displayed as a textual interpretation of the generated input sequence is confirmed for output as the textual interpretation of the generated input sequence upon entry of any input that results in the unambiguous generation of one or more characters, wherein said one or more unambiguous characters are output immediately following the output of said confirmed textual interpretation.

6. The system of claim 1, wherein the code used to construct objects associated with a child node by modifying objects associated with the corresponding parent node further includes a specification of whether the code is the final code of the sequence of codes which create objects associated with the child node.

7. The system of claim 1, wherein the number and identity of additional inputs which correspond to child nodes linked to a parent node is indicated in the parent node by a field of valid key bits that indicate the number and identity of said child nodes.

8. The system of claim 7, wherein each set of one or more codes used to create the objects associated with a child node is immediately followed by a pointer to said child node, and wherein the one or more sets of one or more codes and following pointer are placed sequentially in memory within the parent node in the same order as the valid key bits that indicate the number and identity of said child nodes.

9. The system of claim 1, wherein the sequence of codes which create objects associated with a child node are ordered in memory such that objects are created in a sequence that is sorted with respect to the frequency of use of said objects.

10. The system of claim 1, wherein the indices of the characters associated with each input are assigned sequentially to the characters in descending order of the frequency of occurrence of the characters in word objects in memory.

11. The system of claim 10, wherein the code used to construct objects associated with a child node by modifying objects associated with the corresponding parent node also includes a specification of an object type associated with the constructed object associated with the child node.

12. The system of claim 11, wherein the object type that is specified includes information regarding the part of speech of the constructed object.

13. The system of claim 11, wherein the object type that is specified includes information regarding the capitalization of the constructed object.

14. The system of claim 11, wherein the object type that is specified includes information regarding inflectional endings and suffixes that may be appended to the constructed object.

15. The system of claim 11, wherein the object type that is specified includes a code that uniquely identifies the constructed object among the objects in memory.

16. The system of claim 11, wherein the object type that is specified includes information regarding the frequency of use of the constructed object.

17. The system of claim 11, wherein the object type that is specified includes information regarding whether the constructed object is a completed word.

18. The system of claim 9, wherein the indices of the characters associated with each input include indices that are assigned to a string comprising a plurality of characters.

19. The system of claim 1, wherein the indices of the characters associated with each input are assigned sequentially to the characters in descending order of the frequency of occurrence of the characters following the immediately preceding character in the object associated with the corresponding parent node to which the indexed character is appended to form an object associated with the child node.

20. The system of claim 1, wherein one or more codes that are associated with a given input and are present in both of said redundant parent nodes are defined as being identical when the codes specify the same numerical object index and the same numerical character index, even when said codes occur in a different sequence in the two redundant parent nodes.

21. The system of claim 1, wherein one or more codes used to construct objects associated with child nodes by modifying objects associated with the corresponding parent node also include a specification of an object type associated with the constructed object associated with the child node, and wherein two codes are defined as being identical when they specify the same numerical object index and the same numerical character index and when at most one of the two codes specifies an object type, wherein the code that is present in the remaining redundant parent node that is augmented by any codes and links to child nodes that were present only in the omitted redundant parent node includes the specification of said object type.

22. The system of claim 21, wherein the object type that is specified includes information to distinguish the input sequence corresponding to the constructed object from other input sequences that utilize the node.

23. The system of claim 1, wherein two parent nodes of the tree are defined as redundant only when all codes associated with a given input are present in both of said redundant parent nodes and are identical in that the codes occur in the same sequence and specify the same numerical object index and the same numerical character index, and further in that for all inputs for which child nodes are linked to each of the two redundant parent nodes said child nodes are also redundant in the same recursive sense.

24. The system of claim 23, wherein one or more codes that are associated with a given input and are present in both of said redundant parent nodes are defined as being identical when the codes specify the same numerical object index and the same numerical character index, even when said codes occur in a different sequence in the two redundant parent nodes.

25. A disambiguating system for disambiguating ambiguous input sequences entered by a user, the disambiguating system comprising:

(a) a user input device having a plurality of inputs, each of the plurality of inputs associated with a plurality of characters, an input sequence being generated each time an input is selected by manipulating the user input device, wherein the generated input sequence corresponds to the sequence of inputs that have been selected, and the generated input sequence has a textual interpretation that is ambiguous due to the plurality of characters associated with each input, at least one of the plurality of inputs being an ambiguous punctuation input associated with a plurality of punctuation characters, the input device having at least one unambiguous selection input for generating an unambiguous output, an input sequence being terminated when the user manipulates the user input to any unambiguous input;

(b) a memory containing a plurality of objects, each of the plurality of objects being associated with an input sequence, each of the plurality of objects in the memory being further associated with a frequency of use;

(c) a display to depict system output to the user; and

(d) a processor coupled to the user input device, memory and display, said processor comprising;

(i) an identifying component for identifying from the plurality of objects in the memory at least one object associated with each generated input sequence and having the highest frequency of use;

(ii) an output component for displaying at least one of the identified objects associated with each generated input sequence as a textual interpretation of the generated input sequence, wherein the objects associated with each input sequence are displayed in order of decreasing frequency of use; and

(iii) a selection component for selecting one of the identified objects for entry into a text entry display location upon detecting one or more manipulations of the user input device to an unambiguous selection input;

wherein the processor, detects the selection of the ambiguous punctuation input, appends it to an input sequence, and provisionally outputs the associated textual interpretation of the input sequence which is terminated by one of the associated punctuation characters of the ambiguous punctuation input, and upon detection of a next input that is a member of a first set of designated inputs that is associated with the output of a character distinct from said provisionally output punctuation character, confirms the previously output punctuation character, and, alternatively, upon detection of a next input that is a member of one of one or more alternate sets of designated inputs, wherein each of said one or more alternate sets of designated inputs is associated with the output of a next character that is distinct from said provisionally output punctuation character, replaces the previously output punctuation character with another of the plurality of punctuation characters associated with the ambiguous punctuation input with the replacing punctuation character being determined by the alternate set of designated inputs of which said next input is a member.

26. The system of claim 25, wherein the ambiguous punctuation input is associated with a period, a hyphen, and an apostrophe.

27. The system of claim 25, wherein the processor, upon detecting the selection of the ambiguous punctuation input and appending said ambiguous punctuation input to the current generated input sequence to form a sequence that is not associated with any object in memory, accepts the provisionally displayed object with the highest frequency of use associated with the generated input sequence prior to detecting the selection of the ambiguous punctuation input, provisionally outputs the default punctuation character associated with the ambiguous punctuation input, and establishes a new generated input sequence of length one comprising the ambiguous punctuation input.

28. The system of claim 25, wherein the processor, upon detecting an occurrence of the ambiguous punctuation input in the generated input sequence, generates a sequence of alternate textual interpretations which may be selected by the manipulation of the user input device to an unambiguous selection input one or more times, wherein the first of said sequence of alternate textual interpretations is generated by appending one of the punctuation characters associated with the ambiguous punctuation input to the object with the highest frequency of use associated with the sequence of inputs in the generated input sequence that were input preceding the ambiguous punctuation input, followed by appending the object with the highest frequency of use associated with the sequence of inputs in the generated input sequence that was input following the ambiguous punctuation input, followed by other combinations of objects which include objects with progressively lower frequencies of use that are associated with the sequence of inputs in the generated input sequence that were input preceding the ambiguous punctuation input, and also objects with progressively lower frequencies of use associated with the sequence of inputs in the generated input sequence that was input following the ambiguous punctuation input, such that the created objects are created in descending order of the combined frequency ranking of said two objects.

29. The system of claim 25, wherein the processor, upon detecting the selection of a sequence of one or more ambiguous input followed by a first selection of an unambiguous selection input, selects the object having a highest frequency of use and outputs said selected text object and a single following space to the display, and wherein upon detecting each subsequent repeated successive selection of an unambiguous selection input selects an object having the next lower frequency of use from the identified objects, and replaces the previously output text object in its display position preceding the previously output single space with each said successively selected text object.

30. The system of claim 25, wherein the processor, upon detecting the selection of the ambiguous punctuation input and appending the ambiguous punctuation input to the current generated input sequence to form a sequence that is associated with a completed word object in memory with a highest frequency of use that ends with a punctuation character associated with said ambiguous punctuation input, and upon detecting the selection of a next input wherein said next input is an ambiguous input associated with one or more alphabetic letters, confirms the output of said completed word object as the textual interpretation of the current generated input sequence including the selection of the ambiguous punctuation input, and starts a new generated input sequence comprising said next ambiguous input.

31. The system of claim 25, wherein the composition of said first set and said one or more alternate sets of designated inputs is determined with respect to whether there exists in said memory one or more objects associated with said input sequence including the appended ambiguous punctuation input.

32. The system of claim 31, wherein the processor, upon detecting the selection of the ambiguous punctuation input and appending said ambiguous punctuation input to the current generated input sequence to form a sequence that is not associated with any object in memory corresponding to a completed word, provisionally outputs one of the associated punctuation characters, and

wherein the processor, upon detecting the selection of a next input wherein said next input is an ambiguous input associated with one or more alphabetic letters but not associated with the letter ‘ s’

, changes the previously output punctuation character to a hyphen, confirms the provisionally output textual interpretation of the current generated input sequence prior to the selection of the ambiguous punctuation input, and starts a new generated input sequence comprising said next ambiguous input, and

wherein the processor, upon detecting the selection of a next input wherein said next input is an ambiguous input associated with one or more alphabetic letters including the letter ‘

is’

, confirms the provisionally output textual interpretation of the current generated input sequence prior to the selection of the ambiguous punctuation input and starts a new generated input sequence comprising said next ambiguous input and replaces the previously output punctuation character with an apostrophe and provisionally appends the letter ‘

s’

as the textual interpretation of said new generated input sequence, and wherein the processor, upon detecting the selection of a yet another next input wherein said next input is an ambiguous input associated with one or more alphabetic letters, replaces the previously output apostrophe with a hyphen, and starts a new generated input sequence comprising said ambiguous input associated with one or more alphabetic letters including the letter ‘

s’

followed by said yet another next ambiguous input, and outputs the object in memory associated with said newly started input sequence following said hyphen, and

wherein the processor, upon detecting the selection of a next input wherein said next input is not associated with one or more alphabetic letters, confirms the previously output punctuation character.

33. The system of claim 25, wherein the composition of said first set and said one or more alternate sets of designated inputs is determined with respect to whether there exists in said memory one or more objects associated with the input sequence including the appended ambiguous punctuation input and further appending said next input when said next input is an ambiguous input.

34. The system of claim 25, wherein the composition of said first set and said one or more alternate sets of designated inputs is determined with respect to whether there exists in memory one or more objects associated with an input sequence beginning with the selection of the ambiguous punctuation input and appending said next input when said next input is an ambiguous input.

35. A method for disambiguating ambiguous input sequences, the method comprising:

(a) generating an input sequence from a plurality of inputs, each of the plurality of inputs associated with a plurality of characters, the generated input sequence having a textual interpretation that is ambiguous due to the plurality of characters associated with each input;

(b) storing data used to construct a plurality of objects, each of the plurality of objects associated with an input sequence and a relative frequency of use, wherein each of the plurality of objects includes completed word objects, word stem objects comprising a sequence of the initial characters of a yet uncompleted word object, and objects that are both a completed word and a stem of a word, and wherein all word and stem objects are stored in a tree structure comprised of a plurality of nodes, each node associated with an input sequence and with one or more objects, and wherein the plurality of nodes are connected by a plurality of paths, each of the plurality of paths linking a parent node associated with a base input sequence with a child node associated with the base input sequence of the parent node and an additional input; and

wherein the objects associated with a child node are based on the objects associated with the corresponding parent node to which the child node is linked; and

wherein the objects associated with a child node are constructed using a code pre-stored in memory to modify objects associated with the corresponding parent node; and

wherein the code used to construct objects associated with a child node by modifying objects associated with the corresponding parent node comprises a specification of the numerical index of the object associated with the corresponding parent node and a specification of the numerical index of one of the characters associated with the additional input linking the parent node to the child node;

(c) identifying from the one or more objects associated with each generated input sequence at least one candidate object with the highest frequency of use, wherein said candidate object is a word object when at least one word object is associated with the generated input sequence, and wherein said candidate object is a word stem object when no word object is associated with the generated input sequence; and

(d) displaying the at least one identified candidate object associated with each generated input sequence as a textual interpretation of the generated input sequence;

wherein two parent nodes of the tree structure are defined as being redundant in the event that all codes associated with a given input are present in both of said redundant parent nodes and are identical in that the codes occur in the same sequence and specify the same numerical object index and the same numerical character index, and further that all inputs for which child nodes are linked to each of said parent nodes said child nodes are also redundant in the same recursive sense, and wherein one of said redundant parent nodes is omitted from the tree structure in memory and the remaining redundant parent node is augmented by any codes and links to child nodes that were present only in the omitted redundant parent node, and all links from any parent node of which the omitted parent node is a child are re-written as links to the remaining redundant parent node.

36. The method of claim 35, wherein the at least one identified candidate object with the highest frequency of use that is displayed as a textual interpretation of the generated input sequence is a word stem object when the frequency of use of said word stem object exceeds by a predetermined factor the highest frequency of use associated with any word object associated with the generated input sequence, and where said highest frequency of use associated with any word object associated with the generated input sequence does not exceed a predetermined threshold.

37. The method of claim 35, wherein the at least one object with the highest frequency of use that is provisionally displayed as a textual interpretation of the generated input sequence is confirmed for output as the textual interpretation of the generated input sequence upon entry of any input that results in the unambiguous generation of one or more characters, wherein said one or more unambiguous characters are output immediately following the output of said object with the highest frequency of use.

38. The method of claim 35, wherein the code used to construct objects associated with a child node by modifying objects associated with the corresponding parent node further includes a specification of whether the code is the final code of the sequence of codes which create objects associated with the child node.

39. The method of claim 35, wherein the number and identity of additional inputs which correspond to child nodes linked to a parent node is indicated in the parent node by a field of valid key bits that indicate the number and identity of said child nodes.

40. The method of claim 39, wherein each set of one or more codes used to create the objects associated with a child node is immediately followed by a pointer to said child node, and wherein the one or more sets of one or more codes and following pointer are placed sequentially in memory within the parent node in the same order as the valid key bits that indicate the number and identity of said child nodes.

41. The method of claim 35, wherein the sequence of codes which create objects associated with a child node are ordered in memory such that objects are created in a sequence that is sorted with respect to the frequency of use of said objects.

42. The method of claim 35, wherein the indices of the characters associated with each input are assigned sequentially to the characters in descending order of the frequency of occurrence of the characters in word objects in memory.

43. The method of claim 42, wherein the code used to construct objects associated with a child node by modifying objects associated with the corresponding parent node also includes a specification of an object type associated with the constructed object associated with the child node.

44. The method of claim 43, wherein the object type that is specified includes a code that uniquely identifies the constructed object among the objects in memory.

45. The method of claim 43, wherein the object type that is specified includes information regarding the frequency of use of the constructed object.

46. The method of claim 43, wherein the object type that is specified includes information regarding whether the constructed object is a completed word.

47. The method of claim 35, wherein the indices of the characters associated with each input include indices that are assigned to a string comprising a plurality of characters.

48. The method of claim 35, wherein the indices of the characters associated with each input are assigned sequentially to the characters in descending order of the frequency of occurrence of the characters following the immediately preceding character in the object associated with the corresponding parent node to which the indexed character is appended to form an object associated with the child node.

49. The method of claim 35, wherein one or more codes that are associated with a given input and are present in both of said redundant parent nodes are defined as being identical when the codes specify the same numerical object index and the same numerical character index, even when said codes occur in a different sequence in the two redundant parent nodes.

50. The method of claim 35, wherein one or more codes used to construct objects associated with child nodes by modifying objects associated with the corresponding parent node also include a specification of an object type associated with the constructed object associated with the child node, and wherein two codes are defined as being identical when they specify the same numerical object index and the same numerical character index and when at most one of the two codes specifies an object type, wherein the code that is present in the remaining redundant parent node that is augmented by any codes and links to child nodes that were present only in the omitted redundant parent node includes the specification of said object type.

51. The method of claim 50, wherein the object type that is specified includes information to distinguish the input sequence corresponding to the constructed object from other input sequences that utilize the node.

52. The method of claim 35, wherein two parent nodes of the tree are defined as redundant only when all codes associated with a given input are present in both of said redundant parent nodes and are identical in that the codes occur in the same sequence and specify the same numerical object index and the same numerical character index, and further in that for all inputs for which child nodes are linked to each of the two redundant parent nodes said child nodes are also redundant in the same recursive sense.

53. The method of claim 52, wherein one or more codes that are associated with a given input and are present in both of said redundant parent nodes are defined as being identical when the codes specify the same numerical object index and the same numerical character index, even when said codes occur in a different sequence in the two redundant parent nodes.

54. A computer-readable medium having computer-executable components for disambiguating ambiguous input sequences, the computer-executable components comprising:

(a) a user input component for processing input sequences consisting of one or more inputs, at least a portion of the inputs being associated with a plurality of characters, at least a portion of the input sequences having a textual interpretation that is ambiguous due to the plurality of characters associated with the inputs;

(b) a storage component containing data used to construct a plurality of objects, each of the plurality of objects associated with an input sequence and a relative frequency of use, wherein each of the plurality of objects include completed word objects, word stem objects comprising a sequence of the initial characters of a yet uncompleted word object, and objects that are both a completed word and a stem of a word, all word and stem objects being stored in a tree structure comprised of a plurality of parent and child nodes, each node being associated with an input sequence and with one or more objects, the plurality of nodes being connected by a plurality of paths, each of the parent nodes having a base input sequence, each of the plurality of paths linking a parent node with a child node associated with the base input sequence of the parent node and an additional input, the objects associated with a child node being based on the objects associated with the parent node to which the child node is linked;

the objects associated with a child node being constructed using an executable stored code to modify objects associated with the corresponding parent node;

the executable stored code modifying objects associated with the corresponding parent node and comprising a specification of the numerical index of the object associated with the corresponding parent node and a specification of the numerical index of one of the characters associated with the additional input linking the parent node to the child node, two parent nodes of the tree structure being considered redundant when all codes associated with a given input are present in both of said parent nodes and are identical in that the codes occur in the same sequence and specify the same numerical object index and the same numerical character index and all inputs linking child nodes to the two parent nodes are also redundant in the same recursive sense, said data stored in said storage component including executable code for omitting one of said redundant parent nodes from the tree structure in memory and for augmenting the remaining redundant parent node with any codes and links to child nodes that were present only in the omitted redundant parent node, and executable code for re-writing all links from the omitted parent node to a parent of the omitted parent node as links to the remaining redundant parent node;

(c) an identifying component for identifying from the one or more objects associated with each input sequence at least one candidate object with the highest frequency of use, wherein said candidate object is a word object when at least one word object is associated with the input sequence, and wherein said candidate object is a word stem object when no word object is associated with the input sequence; and

(d) an output component for displaying the at least one identified candidate object associated with each input sequence as a textual interpretation of the input sequence.

55. The computer-readable medium of claim 54, wherein the at least one identified candidate object with the highest frequency of use that is displayed as a textual interpretation of the generated input sequence is a word stem object when the frequency of use of said word stem object exceeds by a predetermined factor the highest frequency of use associated with any word object associated with the generated input sequence, and where said highest frequency of use associated with any word object associated with the generated input sequence does not exceed a predetermined threshold.

56. The computer-readable medium of claim 54, wherein the at least one object with the highest frequency of use that is provisionally displayed as a textual interpretation of the generated input sequence is confirmed for output as the textual interpretation of the generated input sequence upon entry of any input that results in the unambiguous generation of one or more characters, wherein said one or more unambiguous characters are output immediately following the provisional display of said object said at least one object with the highest frequency of use as said textual interpretation.

57. The computer-readable medium of claim 54, wherein the code used to construct objects associated with a child node by modifying objects associated with the corresponding parent node further includes a specification of whether the code is the final code of the sequence of codes which create objects associated with the child node.

58. The computer-readable medium of claim 54, wherein the number and identity of additional inputs which correspond to child nodes linked to a parent node is indicated in the parent node by a field of valid key bits that indicate the number and identity of said child nodes.

59. The computer-readable medium of claim 58, wherein each set of one or more codes used to create the objects associated with a child node is immediately followed by a pointer to said child node, and wherein the one or more sets of one or more codes and following pointer are placed sequentially in memory within the parent node in the same order as the valid key bits that indicate the number and identity of said child nodes.

60. The computer-readable medium of claim 54, wherein the sequence of codes which create objects associated with a child node are ordered in memory such that objects are created in a sequence that is sorted with respect to the frequency of use of said objects.

61. The computer-readable medium of claim 54, wherein the indices of the characters associated with each input are assigned sequentially to the characters in descending order of the frequency of occurrence of the characters in word objects in memory.

62. The computer-readable medium of claim 61, wherein the code used to construct objects associated with a child node by modifying objects associated with the corresponding parent node also includes a specification of an object type associated with the constructed object associated with the child node.

63. The computer-readable medium of claim 62, wherein the object type that is specified includes a code that uniquely identifies the constructed object among the objects in memory.

64. The computer-readable medium of claim 62, wherein the object type that is specified includes information regarding the frequency of use of the constructed object.

65. The computer-readable medium of claim 62, wherein the object type that is specified includes information regarding whether the constructed object is a completed word.

66. The computer-readable medium of claim 54, wherein the indices of the characters associated with each input include indices that are assigned to a string comprising a plurality of characters.

67. The computer-readable medium of claim 54, wherein the indices of the characters associated with each input are assigned sequentially to the characters in descending order of the frequency of occurrence of the characters following the immediately preceding character in the object associated with the corresponding parent node to which the indexed character is appended to form an object associated with the child node.

68. The computer-readable medium of claim 54, wherein one or more codes that are associated with a given input and are present in both of said redundant parent nodes are defined as being identical when the codes specify the same numerical object index and the same numerical character index, even when said codes occur in a different sequence in the two redundant parent nodes.

69. The computer-readable medium of claim 54, wherein one or more codes used to construct objects associated with child nodes by modifying objects associated with the corresponding parent node also include a specification of an object type associated with the constructed object associated with the child node, and wherein two codes are defined as being identical when they specify the same numerical object index and the same numerical character index and when at most one of the two codes specifies an object type, wherein the code that is present in the remaining redundant parent node that is augmented by any codes and links to child nodes that were present only in the omitted redundant parent node includes the specification of said object type.

70. The computer-readable medium of claim 69, wherein the object type that is specified includes information to distinguish the input sequence corresponding to the constructed object from other input sequences that utilize the node.

71. The computer-readable medium of claim 54, wherein two parent nodes of the tree are defined as redundant only when all codes associated with a given input are present in both of said redundant parent nodes and are identical in that the codes occur in the same sequence and specify the same numerical object index and the same numerical character index, and further in that for all inputs for which child nodes are linked to each of the two redundant parent nodes said child nodes are also redundant in the same recursive sense.

72. The computer-readable medium of claim 71, wherein one or more codes that are associated with a given input and are present in both of said redundant parent nodes are defined as being identical when the codes specify the same numerical object index and the same numerical character index, even when said codes occur in a different sequence in the two redundant parent nodes.

73. A method for disambiguating ambiguous input sequences entered by a user, the method comprising

(a) generating an input sequence from a plurality of inputs, each of the plurality of inputs associated with a plurality of characters, the generated input sequence having a textual interpretation that is ambiguous due to the plurality of characters associated with each input;

(b) storing a plurality of objects, each of the plurality of objects comprising a sequence of characters associated with an input sequence and a frequency of use;

(c) identifying from the plurality of objects at least one object associated with each generated input sequence and having a highest frequency of use;

(d) displaying at least one of the identified objects having a highest frequency of use associated with each generated input sequence as a textual interpretation of the generated input sequence, wherein the objects associated with each input sequence are displayed in order of decreasing frequency of use;

(e) selecting one of the identified objects as the textual interpretation of the generated input sequence upon detecting one or more selections of an unambiguous selection input;

wherein;

(i) upon detection of the selection of an ambiguous punctuation input, the step of selecting one of the identified objects provisionally selects one of the punctuation characters associated with the selected ambiguous punctuation input;

(ii) upon detection of the selection of the next input following the selection of the ambiguous punctuation input, the provisionally selected punctuation character is confirmed if said next input is a member of a first set of designated inputs, wherein each of said first set of designated inputs is associated with the output of a next character distinct from said provisionally selected punctuation character; and

(iii) upon detection of the selection of said next input following the selection of the ambiguous punctuation input, the provisionally selected punctuation character is replaced with another of the plurality of punctuation characters associated with the ambiguous punctuation input, if said next input is a member of one of one or more alternate sets of designated inputs, wherein each of said one or more alternate sets of designated inputs is associated with the output of a next character distinct from said provisionally punctuation character and wherein the replacing punctuation character is determined by the alternate set of designated inputs of which said next input is a member.

74. The method of claim 73, further comprising:

(a) upon detection of the selection of the ambiguous punctuation input and appending said ambiguous punctuation input to the current generated input sequence to form a sequence that is not associated with any object in memory that corresponds to a completed word, provisionally outputting one of the associated punctuation characters, and

(b) upon detection of the selection of a next input wherein said next input is an ambiguous input associated with one or more alphabetic letters but not associated with the letter ‘

s’

;

(i) changing the previously output punctuation character to a hyphen;

(ii) confirming the provisionally output textual interpretation of the current generated input sequence prior to the selection of the ambiguous punctuation input; and

(iii) starting a new generated input sequence comprising said next ambiguous input; and

(c) upon detection of the selection of a next input wherein said next input is an ambiguous input associated with one or more alphabetic letters including the letter ‘

s’

,

(i) confirming the provisionally output textual interpretation of the current generated input sequence prior to the selection of the ambiguous punctuation input;

(ii) starting a new generated input sequence comprising said next ambiguous input;

(iii) replacing the previously output punctuation character with an apostrophe and provisionally appending the letter ‘

s’

as the textual interpretation of said new generated input sequence; and

(iv) upon detection of the selection of a yet another next input wherein said next input is an ambiguous input associated with one or more alphabetic letters, replacing the previously output apostrophe with a hyphen, and starting a new generated input sequence comprising said ambiguous input associated with one or more alphabetic letters including the letter ‘

s’

followed by said yet another next ambiguous input, and outputting the object in memory associated with said newly started input sequence following said hyphen, and

(d) upon detection of the selection of a next input wherein said next input is not associated with one or more alphabetic letters, confirming the previously output punctuation character.

75. The method of claim 73, further comprising:

upon detection of the selection of the ambiguous punctuation input and appending said ambiguous punctuation input to the current generated input sequence to form a sequence that is not associated with any object in memory,

(a) accepting the provisionally displayed object with the highest frequency of use associated with the generated input sequence prior to detecting the selection of the ambiguous punctuation input;

(b) provisionally outputting the default punctuation character associated with the ambiguous punctuation input; and

(c) establishing a new generated input sequence of length one comprising the ambiguous punctuation input.

76. The method of claim 73, further comprising:

upon detection of an occurrence of the ambiguous punctuation input in the generated input sequence,

(a) generating a sequence of alternate textual interpretations which may be selected by the manipulation of the user input device to an unambiguous selection input one or more times, wherein the first of said sequence of alternate textual interpretations is generated by appending one of the punctuation characters associated with the ambiguous punctuation input to the object with the highest frequency of use associated with the sequence of inputs in the generated input sequence that were input preceding the ambiguous punctuation input, followed by appending the object with the highest frequency of use associated with the sequence of inputs in the generated input sequence that was input following the ambiguous punctuation input, followed by other combinations of objects which include objects with progressively lower frequencies of use that are associated with the sequence of inputs in the generated input sequence that were input preceding the ambiguous punctuation input, and also objects with progressively lower frequencies of use associated with the sequence of inputs in the generated input sequence that was input following the ambiguous punctuation input, such that the created objects are created in descending order of the combined frequency ranking of said two objects; and

(b) selecting one of these alternate textual interpretations upon detecting the manipulation of the user input device to said unambiguous selection input one or more times.

77. The method of claim 73, further comprising:

(a) upon detection of the selection of a sequence of one or more ambiguous inputs followed by a first selection of an unambiguous selection input, selecting the object having a highest frequency of use and outputs said selected text object and a single following space to the display; and

(b) upon detection of each subsequent repeated successive selection of an unambiguous selection input,

(i) selecting an object having the next lower frequency of use from the identified objects; and

(ii) replacing the previously output text object in its display position preceding the previously output single space with each said successively selected text object.

78. The method of claim 73, further comprising

upon detection of the selection of the ambiguous punctuation input and appending the ambiguous punctuation input to the current generated input sequence to form a sequence that is associated with a completed word object in memory with a highest frequency of use that ends with a punctuation character associated with said ambiguous punctuation input, and upon detection of the selection of a next input wherein said next input is an ambiguous input associated with one or more alphabetic letters, punctuation input to the current generated input sequence to form a sequence that is not associated with any object in memory, the output component accepts the provisionally displayed object with the highest frequency of use associated with the generated input sequence prior to detection of the selection of the ambiguous punctuation input, provisionally outputs the default punctuation character associated with the ambiguous punctuation input, and establishes a new generated input sequence of length one comprising the ambiguous punctuation input.

79. The method of claim 73, wherein the composition of said first set and said one or more alternate sets of designated inputs is determined with respect to whether there exists in said memory one or more objects associated with said input sequence including the appended ambiguous punctuation input.

80. The method of claim 73, wherein the composition of said first set and said one or more alternate sets of designated inputs is determined with respect to whether there exists in said memory one or more objects associated with the input sequence including the appended ambiguous punctuation input and further appending said next input when said next input is an ambiguous input.

81. The method of claim 73, wherein the composition of said first set and said one or more alternate sets of designated inputs is determined with respect to whether there exists in memory one or more objects associated with an input sequence beginning with the selection of the ambiguous punctuation input and appending said next input when said next input is an ambiguous input.

82. A computer-readable medium having computer-executable components for disambiguating ambiguous input sequences, the computer-executable components comprising:

(a) a user input component for processing generated input sequences including a plurality of inputs, at least a portion of the plurality of inputs being associated with a plurality of characters, at least a portion of the generated input sequences having a textual interpretation that is ambiguous due to the portion of the plurality of inputs that are associated with a plurality of characters, at least one of the plurality of inputs being an ambiguous punctuation input associated with a plurality of punctuation characters, at least one of the plurality of inputs including an unambiguous selection input for generating an unambiguous output, an input sequence being terminated when an unambiguous input is selected;

(b) a storage component for storing a plurality of objects, each of the plurality of objects being associated with an input sequence and a frequency of use;

(c) an identifying component for identifying from the plurality of objects at least one object associated with each generated input sequence and having a highest frequency of use;

(d) an output component for displaying at least one of the identified objects associated with each generated input sequence as a textual interpretation of the generated input sequence, wherein the objects associated with each input sequence are displayed in order of decreasing frequency of use; and

(e) a selection component for selecting one of the identified objects as the textual interpretation of the generated input sequence upon detecting one or more selections of an unambiguous selection input;

wherein;

(i) upon detection of the selection of said ambiguous punctuation input, one of the associated punctuation characters is provisionally selected by said selection component;

(ii) upon detection of the selection of a next input, the provisionally selected punctuation character is confirmed in the event said next input is a member of a first set of designated inputs, wherein each of said first set of designated inputs is associated with the output of a next character distinct from said provisionally output punctuation character; and

(iii) upon detection of the selection of said next input, the provisionally selected punctuation character is replaced with another of the plurality of punctuation characters associated with the ambiguous punctuation input in the event said next input is a member of one or more alternate sets of designated inputs wherein each of said one or more alternate sets of designated inputs is associated with the output of a next character distinct from said provisionally output punctuation character, with the replacing punctuation character being determined by the alternate set of designated inputs of which said next input is a member.

83. The computer-readable medium of claim 82, wherein:

(a) upon detection of the selection of the ambiguous punctuation input and appending said ambiguous punctuation input to the current generated input sequence to form a sequence that is not associated with any object in the storage component corresponding to a completed word, the output component provisionally outputs one of the associated punctuation characters;

(b) upon detection of the selection of a next input wherein said next input is an ambiguous input associated with one or more alphabetic letters but not associated with the letter ‘

s’

, the output component changes the previously output punctuation character to a hyphen, confirms the provisionally output textual interpretation of the current generated input sequence prior to the selection of the ambiguous punctuation input, and starts a new generated input sequence comprising said next ambiguous input;

(c) upon detection of the selection of a next input wherein said next input is an ambiguous input associated with one or more alphabetic letters including the letter ‘

s’

, the output component confirms the provisionally output textual interpretation of the current generated input sequence prior to the selection of the ambiguous punctuation input, starts a new generated input sequence comprising said next ambiguous input, replaces the previously output punctuation character with an apostrophe and provisionally appends the letter ‘

s’

as the textual interpretation of said new generated input sequence, and wherein, upon the input component detecting the selection of a yet another next input wherein said next input is an ambiguous input associated with one or more alphabetic letters, the output component replaces the previously output apostrophe with a hyphen, and the input component starts a new generated input sequence comprising said ambiguous input associated with one or more alphabetic letters including the letter ‘

s’

followed by said yet another next ambiguous input, and the output component outputs the object identified by the identifying component as being associated with said newly started input sequence following said hyphen; and

(d) upon detection of the selection of a next input wherein said next input is not associated with one or more alphabetic letters, the output component confirms the previously output punctuation character.

84. The computer-readable medium of claim 82, wherein upon detection of the selection of the ambiguous punctuation input and appending said ambiguous punctuation input to the current generated input sequence to form a sequence that is not associated with any object in the storage component, the output component accepts the provisionally displayed object with the highest frequency of use associated with the generated input sequence prior to detection of the selection of the ambiguous punctuation input, provisionally outputs the default punctuation character associated with the ambiguous punctuation input, and establishes a new generated input sequence of length one comprising the ambiguous punctuation input.

85. The computer-readable medium of claim 82, wherein upon detection of an occurrence of the ambiguous punctuation input in the generated input sequence:

(a) the output component generates a sequence of alternate textual interpretations which may be selected by the selection of the unambiguous selection input one or more times, wherein the first of said sequence of alternate textual interpretations is generated by appending one of the punctuation characters associated with the ambiguous punctuation input to the object with the highest frequency of use associated with the sequence of inputs in the generated input sequence that were input preceding the ambiguous punctuation input, followed by appending the object with the highest frequency of use associated with the sequence of inputs in the generated input sequence that was input following the ambiguous punctuation input, followed by other combinations of objects which include objects with progressively lower frequencies of use that are associated with the sequence of inputs in the generated input sequence that were input preceding the ambiguous punctuation input, and also objects with progressively lower frequencies of use associated with the sequence of inputs in the generated input sequence that was input following the ambiguous punctuation input, such that the created objects are created in descending order of the combined frequency ranking of said two objects; and

(b) the selection component selects one of these alternate textual interpretations upon detecting the manipulation of the user input device to an unambiguous selection input one or more times.

86. The computer-readable medium of claim 82, wherein:

(a) upon detection of the selection of a sequence of one or more ambiguous inputs followed by a first selection of an unambiguous selection input, the selection component selects the object having a highest frequency of use and the output component outputs said selected text object and a single following space to the display; and

(b) upon detection of each subsequent repeated successive selection of an unambiguous selection input, the selection component selects an object having the next lower frequency of use from the identified objects, and the output component replaces the previously output text object in its display position preceding the previously output single space with each said successively selected text object.

87. The computer-readable medium of claim 82, wherein upon detection of the selection of the ambiguous punctuation input and appending the ambiguous punctuation input to the current generated input sequence to form a sequence that is associated with a completed word object in the storage component with a highest frequency of use that ends with a punctuation character associated with said ambiguous punctuation input, and upon detecting the selection of a next input wherein said next input is an ambiguous input associated with one or more alphabetic letters, the output component confirms the output of said completed word object as the textual interpretation of the current generated input sequence including the selection of the ambiguous punctuation input, and starts a new generated input sequence comprising said next ambiguous input.

88. The computer-readable medium of claim 82 having computer-executable components for disambiguating ambiguous input sequences, said computer-executable components further characterized in that:

the composition of said first set and said one or more alternate sets of designated inputs is determined with respect to whether there exists in said storage component one or more objects associated with said input sequence including the appended ambiguous punctuation input.

89. The computer-readable medium of claim 82 having computer-executable components for disambiguating ambiguous input sequences, said computer-executable components further characterized in that:

the composition of said first set and said one or more alternate sets of designated inputs is determined with respect to whether there exists in said storage component one or more objects associated with the input sequence including the appended ambiguous punctuation input and further appending said next input when said next input is an ambiguous input.

90. The computer-readable medium of claim 82 having computer-executable components for disambiguating ambiguous input sequences, said computer-executable components further characterized in that:

the composition of said first set and said one or more alternate sets of designated inputs is determined with respect to whether there exists in the storage component one or more objects associated with an input sequence beginning with the selection of the ambiguous punctuation input and appending said next input when said next input is an ambiguous input.