Reduced keyboard text input system for the Japanese language

Abstract

A reduced keyboard system for the Japanese language which uses word-level disambiguation of entered keystroke sequences, and which enables the user to select the desired interpretation of an ambiguous input key sequence as kana, and then select the desired textual interpretation associated with the selected kana interpretation. The system uses a highly compressed database format which has several advantages in terms of reduced size and minimal processing requirements during operation. Also disclosed is a reduced keyboard system which uses sequences of two keystrokes to specify each syllable, including the syllables with palatalized vowels that are written with two kana each. Input sequences of keystrokes are interpreted as ordered pairs of keystrokes which select a character according to its position in a two-dimensional matrix. The first keystroke of each ordered pair specifies the row of the matrix in which the desired character appears, and the second keystroke of each pair specifies the column. The organization of the characters in the first five columns of the matrix conforms to the manner in which the Japanese syllabary is learned and conceptualized by a native Japanese speaker. An additional three columns are organized in a manner that corresponds with the natural model of how the syllables with palatalized vowels are formed (each as a combination of two kana). Up to two more specialized columns are added to handle two special cases that do not fit into the simple patterns of the first eight columns.

Claims

The embodiments of the invention in which an exclusive property or privilege is claimed are defined as follows:

1. A disambiguating system for disambiguating ambiguous input sequences entered by a user and generating textual output in the Japanese language, the disambiguating system comprising:

a) a user input device having a plurality of inputs, each of a plurality of said inputs associated with a plurality of characters, an input sequence being generated each time an input is selected by manipulating the user input device and corresponding to the sequence of inputs that have been selected, the generated input sequence having 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 Yomikata text objects, each of the plurality of Yomikata text objects being associated with an input sequence and a frequency of use value, wherein each of the plurality of Yomikata text objects in the memory specifies a sequence of kana to be output to the user, said Yomikata text objects comprise root word objects, and one or more suffix objects that correspond to the root word objects;

c) a display; and

d) a processor coupled to the user input device, memory, and display, the processor adapted for identifying from the memory all Yomikata text objects according to the generated input sequence, wherein said identified Yomikata text objects are root word objects that are associated with the generated input sequence, and wherein said identified Yomikata text objects are combinations of root word objects and suffix objects when the combination is associated with the generated input sequence, and the processor further adapted for generating an output signal causing the display to display at least one of the identified Yomikata text objects as a textual interpretation of the generated input sequence.

2. The system of claim 1, wherein each suffix object is associated with a predefined suffix class.

3. The system of claim 2, wherein root and suffix objects are stored in the memory in a tree structure, said tree structure is comprised of a plurality of nodes, and each node is associated with an input sequence and with one or more Yomikata objects.

4. The system of claim 3, wherein each root word object comprises a class specifier when associated with at least one suffix object, and said class specifier identifies one or more predefined suffix classes that include one or more suffix objects that were previously determined to be associated with the root word object.

5. The system of claim 2, wherein the suffix objects are stored in the memory in suffix tree structures according to their respective suffix classes, each of said suffix tree structures comprises a plurality of nodes, and each node is associated with at least a portion of an input sequence and with one or more Yomikata objects, and wherein said root word objects are stored in the memory in a root tree structure, said root tree structure comprises a plurality of nodes, and each node is associated with at least a portion of an input sequence and a root word object.

6. The system of claim 5, wherein each suffix object comprises a frequency of use value for indicating the suffix object's frequency of use relative to other suffix objects within the associated predefined suffix class and each root word object comprises a frequency of use value for indicating the root word object's frequency of use relative to the other root word objects.

7. The system of claim 6, wherein the relative frequency of use values are logarithmic values.

8. The system of claim 6, wherein said processor identifies from the memory all Yomikata text objects according to the generated input sequence and the associated class specifiers.

9. The system of claim 8, wherein the processor comprises a frequency component for determining a frequency of use value of each of the identified Yomikata text objects, determines the order of the identified Yomikata text objects according to the determined frequency of use values, and instructs the display to display the identified Yomikata text objects according to the determined order.

10. The system of claim 9, wherein the frequency component determines the frequency of use value of each of the identified Yomikata text objects by:

(a) when the identified Yomikata text object is a root word object corresponding to the entire input sequence and the root word object is predefined to appear suffixed, determining the frequency of use associated with each identified Yomikata text object;

(b) when the identified Yomikata text object is a root word object corresponding to the entire input sequence and the root word object is predefined to appear unsuffixed, determining the product of the frequency of use value associated with each identified Yomikata text object and a predefined relative frequency; and

(c) when the identified Yomikata text object is a combination of a root word object and one or more suffix objects, determining the product of the frequency of use value associated with the root word object and the relative frequency of use values associated with the one or more suffix objects.

11. The system of claim 10, wherein said frequency component further comprises an ordering component for resolving order when the determined frequency of two or more identified Yomikata text objects are the same,

wherein, when two or more identified Yomikata text objects have the same determined frequency of use value, said ordering component identifies the identified Yomikata text object with the longer root word object and orders the identified Yomikata text object with the longer root word object before the other identified Yomikata text objects;

wherein, when two or more identified Yomikata text objects with the same determined frequency have different root word objects of the same length, the identified Yomikata text object with the root word object that is first in the root word tree structure is ordered prior to the other identified Yomikata text objects with the same determined frequency having root word objects of the same length; and

wherein, when two or more identified Yomikata text objects with the same determined frequency have the same root word objects, the identified Yomikata text object with the suffix object that is first in a suffix tree structure is ordered prior to the other identified Yomikata text objects with the same determined frequency.

12. The system of claim 2, wherein the suffix classes are separated into a set of one or more verb suffix classes, a set of one or more noun suffix classes, and a set of one or more adjective suffix classes.

13. The system of claim 12, wherein the suffix objects are stored in the memory in suffix tree structures within the sets of verb, noun, and adjective suffix classes, said tree structures are comprised of a plurality of nodes, each node being associated with at least a portion of an input sequence and with one or more Yomikata objects, and wherein said root word objects are stored in the memory in a root tree structure, said root tree structure being comprised of a plurality of nodes, each node being associated with at least a portion of an input sequence and a root word object.

14. The system of claim 13, wherein each suffix object comprises a frequency of use value for indicating the suffix object's frequency of use value relative to other suffix objects within the suffix class set, and each root word object comprises a frequency of use value for indicating the root word object's frequency of use relative to the other root word objects.

15. The system of claim 14, wherein the relative frequency of use value associated with the suffix object is a logarithmic value.

16. The system of claim 14, wherein said processor identifies from the memory all Yomikata text objects according to the generated input sequence and the associated class specifiers.

17. The system of claim 16, wherein the processor comprises a frequency component for determining a frequency of use value of each of the identified Yomikata text objects, determining the order of the identified Yomikata text objects according to the determined frequency of use values, and instructing the display to display the identified Yomikata text objects according to the determined order.

18. The system of claim 17, wherein the frequency component determines the frequency of use value of each of the identified Yomikata text objects by:

(a) when the identified Yomikata text object is a root word object corresponding to the entire input sequence and the root word object is predefined to appear suffixed, determining the frequency of use associated with each identified Yomikata text object;

(b) when the identified Yomikata text object is a root word object corresponding to the entire input sequence and the root word object is predefined to appear unsuffixed, determining the product of the frequency of use value associated with each identified Yomikata text object and a predefined relative frequency; and

(c) when the identified Yomikata text object is a combination of a root word object and the one or more suffix objects, determining the product of the frequency of use value associated with the root word object and the relative frequency of use values associated with the one or more suffix objects.

19. The system of claim 18, wherein said frequency component further comprises an ordering component for resolving order when the determined frequency of two or more identified Yomikata text objects are the same,

wherein, when two or more identified Yomikata text objects have the same determined frequency of use value, said ordering component identifies the identified Yomikata text object with the longer root word object and orders the identified Yomikata text object with the longer root word object before the other identified Yomikata text objects;

wherein, when two or more identified Yomikata text objects with the same determined frequency have different root word objects of the same length, the identified Yomikata text object with the root word object that is first in the root word tree structure is ordered prior to the other identified Yomikata text objects with the same determined frequency having root word objects of the same length; and

wherein, when two or more identified Yomikata text objects with the same determined frequency have the same root word objects, the identified Yomikata text object with the suffix object that is first in a suffix tree structure is ordered prior to the other identified Yomikata text objects with the same determined frequency.

Description

FIELD OF THE INVENTION

The invention relates generally to reduced keyboard systems, and more specifically to reduced keyboard systems generating text composed of the hiragana, katakana and kanji characters of the Japanese language.

BACKGROUND OF THE INVENTION

For many years, portable computers have been getting smaller and smaller. The principal size-limiting component in the effort to produce a smaller portable computer has been the keyboard. If standard typewriter-size keys are used, the portable computer must be at least as large as the keyboard. Miniature keyboards have been used on portable computers, but the miniature keyboard keys have been found to be too small to be easily or quickly manipulated by a user.

Incorporating a full-size keyboard in a portable computer also hinders true portable use of the computer. Most portable computers cannot be operated without placing the computer on a flat work surface to allow the user to type with both hands. A user cannot easily use a portable computer while standing or moving. In the latest generation of small portable computers, called Personal Digital Assistants (PDAs) or palm-sized computers, companies have attempted to address this problem by incorporating handwriting recognition software in the device. A user may directly enter text by writing on a touch-sensitive panel or screen. This handwritten text is then converted by the recognition software into digital data. Unfortunately, in addition to the fact that printing or writing with a pen is in general slower than typing, the accuracy and speed of the handwriting recognition software has to date been less than satisfactory. In the case of the Japanese language, with its large number of complex characters, the problem becomes especially difficult. To make matters worse, today's handheld computing devices which require text input are becoming smaller still. Recent advances in two-way paging, cellular telephones, and other portable wireless technologies has led to a demand for small and portable two-way messaging systems, and especially for systems which can both send and receive electronic mail ("e-mail").

It would therefore be advantageous to develop a keyboard for entry of text into a computer device that is both small and operable with one hand while the user is holding the device with the other hand. Prior development work has considered use of a keyboard that has a reduced number of keys. As suggested by the keypad layout of a touch-tone telephone, many of the reduced keyboards have used a 3-by-4 array of keys. A number of the keys in the array are associated with multiple characters. There is therefore a need for a method for the user to indicate which of the characters associated with a given key is the desired character.

One suggested approach for unambiguously specifying hiragana characters entered on a reduced keyboard requires the user to enter two or more keystrokes to specify each kana. The keystrokes may be entered either simultaneously (chording) or in sequence (multiple-stroke specification). Neither chording nor multiple-stroke specification has produced a keyboard having adequate simplicity and efficiency of use. Multiple-stroke specification is inefficient, and chording is often complicated to learn and use.

Each syllable in the Japanese syllabary consists of either a single vowel, or a consonant followed by a vowel. There are two exceptions: the syllable {character pullout} which has no vowel, and the "small" {character pullout} which is used to indicate the "doubling" or "hardening" of the pronunciation of the following consonant. These syllables can be written as hiragana (commonly used when writing native Japanese words) or katakana (commonly used when writing words of foreign origin). The term kana is used to refer to either hiragana or katakana. The syllabary is commonly represented as a table of rows and columns (shown in FIG. 20), wherein each row may have up to five entries in columns corresponding to the five Japanese vowels {character pullout} and {character pullout}. Each row corresponds to an initial consonant, although a given consonant may undergo sound changes for certain entries in a row (e.g. s(a) {character pullout}=>sh(i) {character pullout}; t(a) {character pullout}=>ts(u) {character pullout}; etc.). The first row consists of five syllables corresponding to each of the five vowels with no initial consonant. The 8.sup.th row consists of the palatalized vowels {character pullout} and {character pullout} (YI and YE are not used in modern Japanese). The diacritic marks " and .sup.o are used to indicate changes in the pronunciation of the consonant, generally indicating a change from an unvoiced to a voiced consonant. FIG. 21 shows the basic syllables formed by adding the diacritic marks " and .sup.o to syllables in FIG. 20. Smaller versions of the syllablesr {character pullout} and {character pullout} are also used in combination with syllables in the second, or {character pullout} columns of FIGS. 20 and 21 to represent syllables consisting of the corresponding consonant and the palatalized vowel (e.g. {character pullout} followed by "small" {character pullout} to represent {character pullout} {character pullout}). These syllables with palatalized vowels are thus written as a pair of kana, as shown in FIG. 22, which includes formns written with diacritic marks.

Lexicographic order in Japanese is generally represented by the sequence of syllables in the first column (corresponding to the vowel A) of FIG. 20: {character pullout} {character pullout} and {character pullout}, where each of these syllables (except {character pullout}) represents a sub-class of up to five syllables composed from the vowels {character pullout} and {character pullout}, in that order. Currently, products such as cellular telephones that require Japanese text input generally use a multiple-stroke specification method wherein each of nine keys is associated with each of the first nine rows ({character pullout} through {character pullout}). Multiple strokes on a key are used to indicate which of the syllables of the corresponding row is intended, wherein each additional stroke on a key sequentially changes the character to be output to the character appearing in the next column of FIG. 20 or 21. A separating key or a timeout method is used to allow entry of consecutive characters associated with the same key. A tenth key is used for the syllables {character pullout} {character pullout}, and the katakana "bo" symbol, which indicates a vowel-only syllable that repeats the vowel of the preceding syllable. The "small" {character pullout} and {character pullout} are also associated with the {character pullout} key, requiring additional keystrokes to be selected. An additional key is commonly used to add the diacritic marks following a syllable.

Entering Japanese hiragana (or katakana) using a reduced keyboard continues to be a challenging problem. With the current multi-stroking approach as described above, generating a single kana syllable requires an average of at least three keystrokes. Syllables with palatalized vowels which are represented by two characters (i.e. those in FIG. 22 consisting of a syllable from the second, {character pullout}, column of FIG. 20 or 24 followed by a "small" {character pullout} or {character pullout}) can require up to eight keystrokes to generate. It would therefore be desirable to develop a reduced keyboard system that tends to minimize the number of keystrokes required to enter hiragana, and is also simple and intuitive to use.

Typing standard Japanese text, which includes Chinese characters (kanji) in addition to kana, on a reduced keyboard is an even more challenging problem. Entering text on a standard computer with a full keyboard and a large display is generally achieved by first typing the pronunciation of the desired text using the letters of the Latin alphabet (called "romaji" in Japanese) corresponding to each hiragana syllable as shown in FIGS. 20-22. As the letters are typed, the input is automatically converted to the corresponding hiragana syllables and displayed on the screen. In many cases, the user then needs to convert the text which is initially displayed as hiragana into the specific textual interpretation desired. The hiragana that are displayed represent the phonetic reading of the combination of kanji and hiragana that the user actually wants to enter, and which conveys the user's intended meaning. Due to the large number of homophones in the Japanese language, there can be a number of possible meaningful combinations of kanji and hiragana that correspond to the hiragana input by the user. On a standard computer, a number of these alternative conversions can be displayed where, for example, each alternative is associated with a numeric key so that pressing the key converts the input hiragana to the displayed kanji interpretation. Additional complications arise when trying to implement this process on a small hand-held device due to the limited display size and the small number of keys available.

An alternative approach for specifying hiragana entered on a reduced keyboard allows the user to enter each hiragana with a single keystroke. Each key of the reduced keyboard is associated with multiple hiragana characters. As a user enters a sequence of keys, there is therefore ambiguity in the resulting output since each keystroke may indicate one of several hiragana. The system must therefore provide a means by which the user can efficiently indicate which of the possible interpretations of each keystroke was intended. Several approaches have been suggested for resolving the ambiguity of the keystroke sequence.

A number of suggested approaches for determining the correct character sequence that corresponds to an ambiguous keystroke sequence are summarized in the article "Probabilistic Character Disambiguation for Reduced Keyboards Using Small Text Samples," published in the Journal of the International Society for Augmentative and Alternative Communication by John L. Arnott and Muhammad Y. Javad (hereinafter the "Amott article"). The Arnott article notes that the majority of disambiguation approaches employ known statistics of character sequences in the relevant language to resolve character ambiguity in a given context. That is, existing disambiguating systems statistically analyze ambiguous keystroke groupings as they are being entered by a user to determine the appropriate interpretation of the keystrokes. The Arnott article also notes that several disambiguating systems have attempted to use word level disambiguation to decode text from a reduced keyboard. Word level disambiguation processes complete words by comparing the entire sequence of received keystrokes with possible matches in a dictionary after the receipt of an unambiguous character signifying the end of the word. The Arnott article discusses many of the disadvantages of word-level disambiguation. For example, word level disambiguation oftentimes fails to decode a word correctly, because of the limitations in identifying unusual words and the inability to decode words that are not contained in the dictionary. Because of the decoding limitations, word level disambiguation does not give error-free decoding of unconstrained English text with an efficiency of one keystroke per character. The Arnott article therefore concentrates on character level disambiguation rather than word level disambiguation, and indicates that character level disambiguation appears to be the most promising disambiguation technique. However, in contrast to alphabetic languages, each hiragana character in Japanese represents a syllable, rather than a single letter that represents what is essentially a phoneme. For this reason, character level disambiguation is inefficient in the Japanese language because there are almost no constraints on possible sequences of hiragana, and the probability distribution of hiragana sequences is not skewed enough for this approach to be effective.

Still another suggested approach is disclosed in a textbook entitled Principles of Computer Speech, authored by I. H. Witten, and published by Academic Press in 1982 (hereinafter the "Witten approach"). Witten discusses a system for reducing ambiguity from text entered using a telephone touch pad. Witten recognizes that for approximately 92% of the words in a 24,500 word English dictionary, no ambiguity will arise when comparing the keystroke sequence with the dictionary. When ambiguities do arise, however, Witten notes that they must be resolved interactively by the system presenting the ambiguity to the user and asking the user to make a selection between the number of ambiguous entries. A user must therefore respond to the system's prediction at the end of each word. Such a response slows the efficiency of the system and increases the number of keystrokes required to enter a given segment of text.

In the case of the Japanese language, users of word processing software are accustomed to having to select from a number of ambiguous interpretations following the entry of a word due to the large number of homophones in the language. The same sequence of kana can frequently be converted to two or more different kanji interpretations. Thus, after entering a sequence of kana, the user is generally required to select the desired kanji conversion from a set of possible choices, and often is also required to somehow confirm that the correct conversion was selected. When the hiragana are entered using a reduced keyboard, there is also ambiguity as to what the user actually intends as the sequence of hiragana to be converted to kanji. As a result, the number of possible interpretations is greatly increased.

Disambiguating an ambiguous keystroke sequence continues to be a challenging problem. As noted in the publications discussed above, satisfactory solutions that minimize the number of keystrokes required to enter a segment of text have failed to achieve the necessary efficiencies to be acceptable for use in a portable computer. It would therefore be desirable to develop a disambiguating system that resolves the ambiguity of entered keystrokes while minimizing the total number of keystrokes required, within the context of a simple and easy to understand user interface. Such a system would thereby maximize the efficiency of text entry.

An effective reduced keyboard input system for the Japanese language must satisfy all of the following criteria. First, the arrangement of the syllables of the Japanese language (kana) on the keyboard, and the method by which they are generated, must be easy for a native speaker to understand and learn to use. Second, the system must tend to minimize the number of keystrokes required to enter text in order to enhance the efficiency of the reduced keyboard system. Third, the system must reduce the cognitive load on the user by reducing the amount of attention and decision-making required during the input process. Fourth, the approach should minimize the amount of memory and processing resources needed to implement a practical system.

Kisaichi et al. [JP 8-314920; U.S. Pat. No. 5,786,776; EP 0 732 646 A2] disclose an approach wherein the keys 1-0 of a telephone keypad are labeled with the hiragana syllables {{character pullout}}, {{character pullout}}, {{character pullout}}, {{character pullout}}, {{character pullout}}, {{character pullout}}, {{character pullout}}, {{character pullout}}, {{character pullout}}, and {{character pullout}}, respectively. This corresponds to what is the de facto standard for Japanese telephone keypads wherein the keys 1-9 of the telephone keypad are labeled with the hiragana syllables {character pullout} {character pullout} and {character pullout} respectively. The single hiragana appearing on each key represents the complete set of hiragana assigned to that key, corresponding to the entire row of hiragana appearing in FIG. 20 in which the single hiragana appears in the first column. The 0 key is often labeled explicitly with {{character pullout}}.

Kisaichi et al. disclose a word-level disambiguation approach, wherein the user ambiguously inputs a sequence of characters (hiragana) by pressing the key with which each character is associated a single time. At the end of each input sequence, the user presses a "Conversion/Next Candidate" key to display the first textual interpretation of one of the possible sequences of hiragana associated with the input key sequence. Kisaichi et al. disclose a dictionary structure wherein all textual interpretations of a given input key sequence are stored consecutively in a contiguous block of memory. Each additional press of the "Conversion/Next Candidate" key displays the next textual interpretation stored in the dictionary, if one exists. If no more textual interpretations exist, an error message is displayed and optional anomaly processing may be performed. When the desired textual interpretation is displayed, a special "Confirmation" key must be pressed to confirm that the desired text has been displayed before the user can go on to enter the next text object.

There are a number of difficulties with the approach disclosed by Kisaichi et al. One is that, due to the fact that there is ambiguity both in specification of the hiragana string and in the conversion of each possible hiragana candidate string, there tend to be a very large number of possible textual interpretations of a given key sequence. This can require the user to step through a large number of interpretations using the "Conversion/Next Candidate" key in order to find the desired interpretation. Further, in stepping through the possible interpretations, the user sees various kanji and/or hiragana strings that correspond to a variety of hiragana strings due to the ambiguity in the input. This can be distracting, and require additional attention from the user in trying to find the desired interpretation. In addition, the database of textual interpretations is arranged such that all data consists only of complete words, and all data for all key sequences of a given length is also stored consecutively in a contiguous block of memory. Kisaichi et al. do not disclose any approach to enable the display of an appropriate stem corresponding to a longer, yet uncompleted word at those points in an input sequence that do not correspond to any completed word. At such points in the input, the system of Kisaichi et al. can only display a default indication of each key entered, such as a numeral or a default letter or character. This is confusing to the user, and fails to provide feedback which is effective in helping the user to confirm that the intended keys have been entered. Finally, the user is required to press the "Confirmation" key for each word input, having to enter an additional keystroke for each input. Thus, the system disclosed by Kisaichi et al. fails to satisfy the criteria discussed above.

Another significant challenge facing any application of word-level disambiguation is successfully implementing it on the kinds of hardware platforms on which its use is most advantageous. As mentioned above, such devices include two-way pagers, cellular telephones, and other hand-held wireless communications devices. These systems are battery powered, and consequently are designed to be as frugal as possible in hardware design and resource utilization. Applications designed to run on such systems must minimize both processor bandwidth utilization and memory requirements. These two factors tend in general to be inversely related. Since word-level disambiguation systems require a large database of words to function, and must respond quickly to input keystrokes to provide a satisfactory user interface, it would be a great advantage to be able to compress the required database without significantly impacting the processing time required to utilize it. In the case of the Japanese language, additional information must be included in the database to support the conversion of sequences of kana to the kanji intended by the user.

Another challenge facing any application of word-level disambiguation is providing sufficient feedback to the user about the keystrokes being input. With an ordinary typewriter or word processor, each keystroke represents a unique character which can be displayed to the user as soon as it is entered. But with word-level disambiguation this is often not possible, since each keystroke represents multiple characters, and any sequence of keystrokes may match multiple words or word stems. It would therefore be desirable to develop a disambiguating system that minimizes the ambiguity of entered keystrokes, and also maximizes the efficiency with which the user can resolve any ambiguity which does arise during text entry. One way to increase the user's efficiency is to provide appropriate feedback following each keystroke, which includes displaying the most likely word following each keystroke, and in cases where the current keystroke sequence does not correspond to a completed word, displaying the most likely stem of a yet uncompleted word.

In order to create an effective reduced keyboard input system for the Japanese language, a system has been designed that does meet all of the criteria mentioned above. First, the arrangement of the syllables of the Japanese language (kana) on the keyboard, and the method by which they are generated, are easy for a native speaker to understand and learn to use. Second, the system tends to minimize the number of keystrokes required to enter text. Third, the system reduces the cognitive load on the user by reducing the amount of attention and decision-making required during the input process, and by the provision of appropriate feedback. Fourth, the approach disclosed herein tends to minimize the amount of memory and processing resources required to implement a practical system.

SUMMARY OF THE INVENTION

The present invention provides a reduced keyboard using word level disambiguation to resolve ambiguities in keystrokes to enter text in the Japanese language. The keyboard may be constructed with full-size mechanical keys, preferably twelve keys arrayed in three columns and four rows as on a standard telephone keypad. Alternatively, the keyboard can be implemented on a display panel which is touch sensitive, wherein contact with the surface of the display generates input signals to the system corresponding to the location of contact.

A plurality of kana characters and symbols are assigned to each of at least several of the keys, so that keystrokes by a user are ambiguous. A user enters a keystroke sequence wherein each keystroke is intended to be the entry of one kana. Each keystroke sequence is thus intended to represent the phonetic reading of a word or common phrase (hereinafter referred to by the Japanese term "Yomikata"). Because individual keystrokes are ambiguous, the keystroke sequence could potentially match more than one Yomikata with the same number of kana.

The keystroke sequence is processed by comparing the keystroke sequence with one or more stored vocabulary modules to match the sequence with corresponding Yomikata. The various Yomikatas associated with a given key sequence are stored in the vocabulary module in the order determined by their expected frequency of occurrence in general usage, where the expected frequency of a Yomikata is calculated as the sum of the frequencies of occurrence of all possible textual interpretations of that Yomikata (including words composed of kanji, hiragana, katakana, or any combination thereof) in general usage (hereinafter referred to by the Japanese term "Midashigo"). In another preferred embodiment, the Yomikata and Midashigo are initially stored in the order determined by their expected frequency of occurrence in general usage, and this order is modified to reflect the frequency of actual usage by the system user. The most frequent Yomikata that matches the sequence of keystrokes and corresponds to at least one completed word or phrase is automatically identified and presented to the user on a display as each keystroke is received. If there is no completed word or phrase whose Yomikata matches the sequence of keystrokes, the most commonly occurring stem of a yet uncompleted word or phrase is automatically identified and presented to the user on the display. The term "selection list" is used generically to refer to any list of textual interpretations (either Yomikata or Midashigo) generated by the system corresponding to an input keystroke sequence. On devices with sufficient display area available (hereinafter referred to as "large-screen devices"), the selection list may be shown (in whole or in part) in a "selection list region" of the display. On such devices, as each keystroke is received, the various Yomikata corresponding to the input sequence are simultaneously presented to the user in a list on the display in descending order of expected frequency in the selection list region. On devices with limited display area, the selection list is maintained internally, and text objects in the list are displayed one at a time in response to activations of a Select key as described below. For each Yomikata in the stored vocabulary module that is associated with one or more alternate textual interpretations, or Midashigo, the Midashigo are stored in order of decreasing frequency of expected occurrence in general usage, so that the most commonly used Midashigo is presented first. As briefly noted above, in an alternate embodiment, the system keeps track of which Midashigo are selected for output by the user most frequently, and modifies the order of presentation to first present the Midashigo most frequently selected.

In accordance with one aspect of the invention, the user presses an unambiguous Select key to delimit an entered keystroke sequence. After receiving the Select key, the disambiguating system automatically selects the most frequently occurring Yomikata and adds the kana to the text being constructed when the user continues to enter additional text. By default, the Yomikata is shown on the display in the form of hiragana, unless the kana is one of the few katakana for which there is no corresponding hiragana (e.g. {character pullout}). In another embodiment, the Yomikata is displayed in the form of katakana, or, in some of the alternate keyboard arrangements described below, in the form of romaji.

In accordance with another aspect of the invention, the Select key that is pressed to delimit the end of a keystroke sequence is also used to select less commonly occurring Yomikata. If the most commonly occurring Yomikata presented on the display is not the desired Yomikata, the user presses the Select key again to advance from the most frequently occurring Yomikata to the second most frequently used Yomikata, which replaces the Yomikata first displayed. If this is not the desired Yomikata, the user presses the Select key again to advance to the third most frequently used Yomikata, and so on. By repetitively pressing the Select key, the user may therefore select the desired Yomikata from the stored vocabulary module. In accordance with another aspect of the invention, upon reaching the end of the Yomikata found in the stored vocabulary, the first and most frequently occurring Yomikata is again displayed, and the cycle repeats.

In accordance with yet another aspect of the invention, each keystroke of the input sequence is also interpreted as a numeral associated with the key, so that the last item displayed following the associated Yomikata is the number corresponding to the input key sequence. This number may be selected for output, thus eliminating the need for a separate numeric mode in the system.

In accordance with another aspect of the invention, once the user has selected the desired Yomikata corresponding to the input key sequence, if the desired Midashigo is identical to the Yornikata which has been selected and is already shown on the display as kana text (i.e. no conversion is required), the user may simply proceed to press the keys corresponding to the next desired text to be input. No additional confirmation or conversion keystroke is required--the selected text has already been provisionally sent to the display for output, and unless it is explicitly changed (e.g. by additional presses of the Select key), it will remain as part of the output text. The user can immediately proceed to enter additional following text, move the text cursor location, or select some other system function. If the desired Midashigo is not the selected Yomikata on the display, i.e., the desired Midashigo consists of kanji, kanji plus hiragana, or katakana, the user presses a Convert key until the desired Midashigo is displayed. If the first (default) Yomikata displayed after the entry of a key sequence is the desired Yomikata, a user need not press the Select key, and may immediately press the Convert key to obtain the desired Midashigo.

The present invention also discloses a method for unambiguously generating the syllables of the Japanese language from ordered pairs of keystrokes on a reduced keyboard in such a way as to meet two of the criteria mentioned above. First, the arrangement of the syllables of the Japanese language (kana) on the keyboard, and the method by which they are generated, are easy for a native speaker to understand and learn to use. Second, the arrangement tends to minimize the number of keystrokes required to unambiguously enter the syllables of the Japanese language. In this aspect of the invention, a sequence of two keystrokes is entered to specify each syllable unambiguously, including the syllables with palatalized vowels shown in FIG. 22 that are written with two kana each.

Input sequences of keystrokes are interpreted as ordered pairs of keystrokes which select a character according to its position in a two-dimensional matrix. The first keystroke of each ordered pair specifies the row of the matrix in which the desired character appears, and the second keystroke of each pair specifies the column. The organization of the characters in the first five columns of the matrix conforms to the manner in which the Japanese syllabary is learned and conceptualized by a native Japanese speaker, as they are shown in FIG. 20. An additional three columns may be organized in a manner that corresponds with the natural model of how the syllables with palatalized vowels are formed (each as a combination of two kana), although these are generally regarded as a separate matrix from the basic syllabary (FIG. 22). Two more columns may be added to handle two special cases (small {character pullout} and {character pullout}) that do not fit into the simple patterns of the first eight columns. These two characters can also be handled somewhat differently in a variety of alternate embodiments. The simplicity and logical organization of this matrix approach makes it possible to use the matrix even when there is no display available to provide feedback to the user. When a display is available, the matrix can be used to organize how feedback is provided to make the operation of the system transparent to the user.

The Japanese syllabary includes 108 syllables (counting the "small" {character pullout} {character pullout} and {character pullout} as separate syllables from the full-sized {character pullout} {character pullout} and {character pullout} since they are written and pronounced in a distinct fashion). There are some additional seldom used syllables, such as the "small" versions of the vowel syllablesr {character pullout} and {character pullout} that are primarily used in katakana. These seldom used syllables may also be easily generated by using the matrix system as discussed above. Of the 108 syllables, 37 are generated by simply adding one of the diacritic marks, dakuten (") or handakuten (.sup.o), to one of the other 71 syllables. These 71 syllables without diacritic marks can be logically organized into a single matrix of nine or ten rows and eight to ten columns. A plurality of the keys on the reduced keyboard of the present invention may be labeled with two kana, one representing the consonant associated with a given row of the matrix, and second kana representing the vowel associated with a given column of the matrix.

The organization is logical and intuitive for a native speaker of Japanese for 106 of the 108 syllables, and the method for generating the remaining two syllables, i.e., small {character pullout}, and {character pullout}, is simple and easily learned. Every syllable is generated by a single pair of keystrokes, including syllables with palatalized vowels that are represented by two separate kana. This results in significantly fewer keystrokes than is required by the currently used multiple-stroke method for entering kana on a reduced keyboard. Thus, the present invention provides a reduced keyboard that is easily understood and quickly learned by native speakers of Japanese, and that is efficient in terms of reducing the length of input keystroke sequences.

In yet another aspect of the invention, both ambiguous and unambiguous methods of specification of syllables as described above may be combined to achieve greater efficiencies in the input method. In one preferred embodiment, the first syllable of each word or phrase to be generated is specified unambiguously by entering an ordered pair of keystrokes using the matrix approach as discussed above, while the remaining syllables of the word or phrase are specified ambiguously with a single keystroke for each syllable using the word level disambiguation method.

In accordance with yet another aspect of the invention, multiple interpretations of the keystroke sequence are provided to the user in the selection list. The keystroke sequence is interpreted as forming one or more words, where the most frequently occurring corresponding word is displayed, and where other corresponding words may also be displayed in a selection list. Simultaneously, the keystroke sequence is interpreted as a number (as explained above), as a word entered using the two-stroke method of the present system or the well-known multiple-stroke specification method, and as a stem of an uncompleted word. On large-screen devices, the multiple interpretations are simultaneously presented to the user in a selection list region for each keystroke of a keystroke sequence entered by the user. On any device, the user may select from the alternate interpretations by pressing the Select key a number of times.

According to a further aspect of the invention, users explicitly disambiguate an already completed key sequence by entering a respell mode. In respell mode, digit keystrokes are taken to be the second keystroke of a two-stroke explicit entry (the first keystroke being the keystroke in the existing key sequence). A menu giving the keystrokes which are available for the current character position and the character they will generate is automatically presented. The cursor automatically advances to the next character with every keystroke. The selection list, pruned to show only the objects compatible with the new explicit characters, is continually updated and presented. The mode is exited when the last character is disambiguated or when the user presses Select or Convert, those keys having their normal function in this mode, also.

In accordance with still another aspect of the invention, the principle database of words and phrases that is used to disambiguate input key sequences is preferably stored in a vocabulary module using tree data structures. Words corresponding to a particular keystroke sequence are constructed from data stored in the tree structure in the form of instructions. The instructions modify the set of words and word stems associated with the immediately preceding keystroke sequence (i.e., the particular keystroke sequence without the last keystroke) to create a new set of words and word stems associated with the keystroke sequence to which the current keystroke has been appended. Constructing words in this manner reduces the storage space of the vocabulary module, since the instructions to build word stems are stored only once, at the top of the tree structure, and are shared by all words constructed from the word stems. The tree structure also greatly reduces processing requirements, since no searching is required to locate stored objects, i.e., words and word stems, for example. The objects stored in the tree data structure may contain frequency or other ranking information which indicates which object is to be displayed first to the user, thus further reducing processing requirements. Furthermore, this tree data structure may be modified using a special algorithm which further compresses the total size required for the database, without engendering an additional processing burden when the database is utilized to retrieve objects associated with keystroke sequences.

In yet another aspect of the present invention, the tree data structure includes two types of instructions. Primary instructions create the Yomikata of the words and phrases stored in a vocabulary module which consist of sequences of kana corresponding to the pronunciation of the words and phrases. Corresponding to each Yomikata is a list of secondary instructions which create the Midashigo associated with each Yomikata. Each Yomikata is created by a primary instruction which modifies one of the Yomikata associated with the immediately preceding keystroke sequence. Likewise, each Midashigo is created by a secondary instruction which modifies one of the Midashigo associated with the Yomikata which was modified by the primary instruction with which the secondary instruction is associated.

The internal, logical representation of the keys in an embodiment need not mirror the physical arrangement represented by the labels on the actual keys. For example, in a database constructed to represent a Japanese vocabulary module, four additional characters ({character pullout}) may also be associated with the key labeled only with the single character {character pullout}. Similarly, characters with special diacritic marks such as the dakuten and handakuten (" and .sup.o) can also be associated with a key. For example, the characters ({character pullout}and {character pullout}) may also be associated with the key labeled only with the single character {character pullout}. This allows the user to easily recall and type words containing characters with diacritic marks, performing only one key activation per character, simply by activating the logically associated physical key for the associated accented character.

Furthermore, in yet another aspect of the invention, greater efficiencies in database compression are achieved by storing each kanji character only once in the database structure for any particular associated reading. In general, a database may include a number of different instances of the same kanji with the same reading (e.g. the kanji {character pullout} (read as {character pullout}) in {character pullout} ({character pullout}) and {character pullout} ({character pullout})). In one preferred embodiment, starting immediately from the root of the tree structure, each reading associated with a given kanji is included in the database, together with a full specification of the code for the kanji. Other occurrences of the kanji having the same reading in the database (not starting immediately from the root of the tree structure) are defined though an indirect reference, which specifies the relative position of the fully specified kanji in the list of Midashigo associated with the reading starting immediately from the root of the tree structure.

Though the tree data structure described above is very efficient for encoding and accessing a large word list, it will be evident to one of ordinary skill in the art that vocabulary modules used in this invention can have other structures. In particular, an embodiment includes a mechanism for users to add words to the recognized set. Since the database with the bulk of the language is often stored in read-only memory, it cannot be modified at run time. Instead, new words are stored in a separate user database which, due to the small number of words involved, is most efficiently stored as a simple list of Yomikata and associated Midashigos.

The combined effects of the assignment of multiple characters to keys, the delimiting of words using a Select key, the selection of the desired Yomikata using a Select key optionally followed by the selection of the desired Midashigo using a Convert key, the presentation of the most commonly occurring word or word stem as the first word in the selection list, the inclusion of multiple interpretations in the selection list, the automatic addition of a selected word to a sentence by the first keystroke of the following word, the ability to compress a large database for disambiguation without incurring any significant processing penalties, and the ability to generate words with characters with diacritic marks by typing the key associated with the characters without a diacritic mark produces a surprising result: for the Japanese language, well over 99% of words found in a representative corpus of text material can be typed on the system with extremely high efficiency. On average, in comparison with entering text on a full keyboard containing one key for each possible basic kana (i.e. 50 keys including those shown in FIG. 20 plus the "small" {character pullout}, {character pullout} and {character pullout}), only 0.61 additional keystrokes per word are required using the reduced keyboard of the present invention with only twelve keys. Compared with a conventional keyboard where kana are entered by spelling the desired word using romaji, on average the system actually requires even fewer keystrokes. When words include characters with diacritics, additional keystroke savings can be achieved. When the words are presented in frequency of use order, the desired word is most often the first word presented and in many cases is the only word presented. The user can then proceed to enter the next word with no additional keystrokes required. High speed entry of text is therefore achieved using a keyboard having a small number of keys.

Japanese is a highly agglutinative language. As such morphemes (inflections, articles, prepositions, etc.), which would be represented as separate words in Indo-European languages, are written as suffixes to words in Japanese. Therefore, it is difficult to get satisfactory coverage of all words a user would like to input without dynamically creating words from lists of valid stems and suffixes. To address this, an alternate embodiment of the present invention provides one or more base trees, with information about the roots of words (lexemes), and one or more suffix trees, with information about the suffixes of words (morphemes). In addition to generating the roots and suffixes themselves, these trees also contain information necessary to allow only legal combinations of roots and suffixes and to properly order the generated complete words (roots and/or roots with suffixes). The process of dynamically generating words from roots and suffixes is referred to in this document as "auto-inflection."

In a system with auto-inflection and a user database, another aspect of this invention greatly expands the power of user-defined words by providing a full set of inflections of them. The suffix class of the user-defined word can be assumed to be the most likely class (a general noun) or it can be specified by the user using a simple menu interface or other method known to the art.

The reduced keyboard disambiguation system disclosed herein reduces the size of the computer or other device that incorporates the system. The reduced number of keys allows a device to be constructed to be held by the user in one hand, while being operated with the other hand. The disclosed system is particularly advantageous for use with cellular telephones, PDAs, two-way pagers, or other small electronic devices that benefit from accurate, high-speed text entry. The system efficiently compresses a large database for disambiguating keystroke sequences without requiring additional processing bandwidth when utilizing the compressed database. The system can provide both efficiency and simplicity when implemented on a touchscreen based device or a device with a limited number of mechanical keys that may also have limited display screen area.

BRIEF DESCRIPTION OF THE DRAWINGS

The foregoing aspects and many of the attendant advantages of this invention will become more readily appreciated as the same becomes better understood by reference to the following detailed description, when taken in conjunction with the accompanying drawings, wherein:

FIG. 1a is a schematic view of an embodiment of a cellular telephone incorporating a reduced keyboard disambiguating system of the present invention;

FIG. 1b is a schematic view of a cellular telephone keypad incorporating an embodiment of the reduced keyboard system of the present invention with limited or no display capabilities;

FIG. 1c is a schematic view of a cellular telephone keypad incorporating an embodiment of the reduced keyboard system of the present invention with display capabilities, showing the display following an activation of key 2 as the first of an ordered pair of keystrokes in the unambiguous two-stroke method;

FIG. 2a is a hardware block diagram of the reduced keyboard disambiguating system of FIG. 1a;

FIG. 2b is a schematic view of an embodiment of a portable computer touchscreen incorporating a reduced keyboard system of the present invention, showing the keypad displayed prior to the first keystroke of an ordered pair of keystrokes in the unambiguous two-stroke method;

FIG. 2c is a schematic view of the touchscreen of FIG. 2b, showing the keypad displayed following an activation of the key associated with the syllables {character pullout} and {character pullout} as the first of an ordered pair of keystrokes;

FIG. 3A is a flow chart of an embodiment of word-level disambiguating software for a reduced keyboard disambiguating system for the Japanese language;

FIG. 3B is a flow chart of respell mode, a mode for explicitly specifying characters for keys already entered;

FIG. 4 is a schematic view of an alternate embodiment of a portable computer touchscreen incorporating a reduced. keyboard system of the present invention;

FIG. 5 is a schematic view of yet another alternate embodiment of a portable computer touchscreen incorporating a reduced keyboard system of the present invention having nine keys;

FIG. 6 compares the physical association of symbols to keys with an instance of a logical association including additional accented variations of the characters appearing on the physical key;

FIG. 7 is an example of a table associating logical symbols to key indices;

FIG. 8A depicts an internal arrangement of data in a node of a tree of a vocabulary module;

FIG. 8B depicts the semantic components of an embodiment of a primary instruction to build a Yomikata text object;

FIG. 8C depicts the semantic components of an embodiment of four different types of secondary instructions used to build Midashigo text objects;

FIG. 8D depicts the semantic components of another preferred embodiment of two of the four different types of secondary instructions used to build Midashigo text objects;

FIG. 8E depicts the information added to instructions to allow for efficient auto-inflection;

FIG. 9 depicts four examples of possible internal data items in the structure of nodes in an embodiment;

FIG. 10 depicts the preferred tree structure of an uncompressed vocabulary module;

FIG. 11 depicts example states of object lists, which are the preferred embodiment for intermediate storage of objects in the process of being retrieved from the vocabulary modules;

FIGS. 12A-E are flowcharts of alternate embodiments of a software process for retrieving text objects from a vocabulary module given a list of key presses;

FIG. 13 is a flowchart of an embodiment of a software process for traversing the tree structure of the vocabulary module given a single key press and altering the state of the object lists;

FIG. 14 is a flowchart of an embodiment of a software process for building a folded, compressed vocabulary module;

FIG. 15 is a flowchart of an embodiment of a software process for folding the tree data structure of a vocabulary module;

FIG. 16 is a flowchart of an embodiment of a software process for locating a second node in a tree of a vocabulary module which has the greatest redundancy in comparison to a given node;

FIG. 17 is a flowchart of an embodiment of a software process for computing the redundancy between two nodes of a tree in a vocabulary module;

FIG. 18 is a chart showing the partial contents of the database of the present invention for a sequence of three consecutive keystrokes on a key, which is ambiguously associated with the syllables {character pullout} and {character pullout};

FIG. 19 shows four representative examples of system operation, showing the contents of the text display of the system illustrated in FIG 1a following each keystroke on a sequence of keys entered while inputting text;

FIG. 20 is a table showing basic Japanese syllabary;

FIG. 21 is a table showing additional Japanes syllabary using diacritics;

FIG. 22 is a table showing Japanaes syllabary with palatalized vowels;

FIG. 23a is a table showing a classifying matrix for Japanes syllabary;

FIG. 23b is a table showing an alternative classifying matrix for Japanese syllabary; and

FIG. 24 is a table showing another alternative classifying matrix for Japanese syllabary.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT

I. System Construction and Basic Operation

With reference to FIG. 1a, a reduced keyboard disambiguating system formed in accordance with the present invention is depicted as incorporated in a portable cellular telephone 52 having a display 53. Portable cellular telephone 52 contains a reduced keyboard 54 implemented on the standard telephone keys. For purposes of this application, the term "keyboard" is defined broadly to include any input device including a touch screen having defined areas for keys, discrete mechanical keys, membrane keys, etc. An arrangement of the kana on each key in the keyboard 54 is depicted in FIG. 1a, corresponding to what has become a de facto standard for Japanese telephones. Note that keyboard 54 thus has a reduced number of data entry keys as compared to a standard QWERTY keyboard, or a keyboard which includes at least 46 keys, where one key is assigned for each of the kana in the basic Japanese syllabary shown in FIG. 20. More specifically, the preferred keyboard shown in this embodiment contains ten data keys numbered 1 through 0 arranged in a 3-by-4 array, together with a Select key 60, and a Convert key 62. Optionally, the keyboard may also include a Clear key 64 to delete previous keystrokes; a Mode key 67 for entering modes to type unambiguous characters, numbers, and symbols; and a Diacritic key 68 to add dakuten and handakuten to previously entered kana.

Data are input into the disambiguation system via keystrokes on the reduced keyboard 54. In a first preferred embodiment, as a user enters a keystroke sequence using the keyboard, text is displayed on the telephone display 53. When the system is implemented on a device with limited display space such as the cellular telephones depicted in FIGS. 1a and 1b, only the currently selected or most likely word object is displayed at the insertion point 88 in the text being generated. As keys are pressed in sequence to enter a desired word, the most likely word corresponding to the input sequence is displayed in some distinguishing format. In the preferred embodiment depicted in FIG. 1a, the current word is displayed with a dotted underline. As explained in more detail below, after the Select key 60 or Convert key 62 is pressed, the dotted underline is changed to a solid underline.

In a second preferred embodiment illustrated in FIGS. 2b and 2c, two regions are defined on the display 53 to display information to the user. A text region 66 displays the text entered by the user just as described for the first embodiment described above, serving as a buffer for text input and editing. As shown in FIGS. 2b and 2c, a selection list region 77, typically located below the text region 66, shows a list of words and other interpretations corresponding to the keystroke sequence entered by a user. The selection list region aids the user in resolving the ambiguity in the entered keystrokes by simultaneously showing both the most frequently occurring interpretation of the input keystroke sequence, and other less frequently occurring alternate interpretations displayed in descending order of frequency.

A block diagram of the reduced keyboard disambiguating system hardware is provided in FIG. 2a. The keyboard 54 and the display 53 are coupled to a processor 100 through appropriate interfacing circuitry. Optionally, a speaker 102 is also coupled to the processor. The processor 100 receives input from the keyboard, and manages all output to the display and speaker. Processor 100 is coupled to a memory 104. The memory includes a combination of temporary storage media, such as random access memory (RAM), and permanent storage media, such as read-only memory (ROM), floppy disks, hard disks, or CD-ROMs. Memory 104 contains all software routines to govern system operation. Preferably, the memory contains an operating system 106, disambiguating software 108, and associated vocabulary modules 110 that are discussed in additional detail below. Optionally, the memory may contain one or more application programs 112, 114. Examples of application programs include word processors, software dictionaries, and foreign language translators. Speech synthesis software may also be provided as an application program, allowing the reduced keyboard disambiguating system to function as a communication aid.

Returning to FIG. 1a, the reduced keyboard disambiguating system allows a user to quickly enter text or other data using only a single hand. Data are entered using the reduced keyboard 54. Each of the data keys 1 through 0 has multiple meanings, represented on the top of the key by characters, numbers, and other symbols. (For the purposes of this disclosure, each data key will be identified by the number and character(s) appearing on the data key, e.g., 3 {character pullout} to identify the upper right data key.) Since individual keys have multiple meanings, keystroke sequences are ambiguous as to their meaning. As the user enters data, the various keystroke interpretations are therefore displayed in multiple regions on the display to aid the user in resolving any ambiguity. On large-screen devices, a selection list of possible interpretations of the entered keystrokes is also displayed to the user in the selection list region. The first entry in the selection list is selected as a default interpretation and displayed in the text region 66 at an insertion point 88. In the preferred embodiment, this entry is displayed with a dotted underline drawn beneath it at the insertion point 88 (and in the selection list region on large-screen devices). The formatting signifies that this object is implicitly selected by virtue of being the most frequently occurring object in the current selection list. If the display includes a selection list region as in FIG. 2b, this formatting also establishes a visual relationship between object at the insertion point 88 and the same object displayed in the selection list region 77. In FIG. 1a, no selection list is displayed, and only the default object (the object that would be displayed first in the selection list prior to any activation of the Select key), or the currently selected object if one has been explicitly selected, is displayed at the insertion point 88.

The selection list of the possible interpretations of the entered keystrokes may be ordered in a number of ways. In a normal mode of operation, the keystrokes are initially interpreted as the entry of kana to spell a Yornikata corresponding to the desired word (hereinafter the "word interpretation"). For example, as shown in FIG. 2b, a keystroke sequence {character pullout}, {character pullout}, and {character pullout} has been entered by a user. As keys are entered, a vocabulary module look-up is simultaneously performed to locate Yomikata that match the keystroke sequence. The Yomikata are returned from the vocabulary module according to frequency of use, with the most commonly used Yomikata listed first. Using the example keystroke sequence, the Yomikata "{character pullout}", "{character pullout}" and "{character pullout}" are identified from the vocabulary module as being the three most probable Yomikata corresponding to the keystroke sequence. Of the eight identified Yomikata in this selection list, "{character pullout}" is the most frequently used, so it is taken as the default interpretation and provisionally posted as hiragana text at the insertion point 88. As shown in FIG. 1a, prior to pressing the Select key 60, this first Yomikata is taken as the default interpretation and is posted at the insertion point 88 using a distinctive format. This format indicates that a subsequent keystroke on one of the data keys will be appended to the current key sequence rather than start a new sequence. For example, as in FIG. 1a, the distinctive formatting consists of displaying the Yomikata as hiragana text with a dotted underline. The list of other potential matching Yomikata is kept in memory, sorted according to their relative frequency.

In the preferred embodiment, following entry of the keystroke sequence corresponding to the desired Yomikata, the user simply presses the Select key 60. The dotted underline beneath the default Yomikata {character pullout} displayed at the insertion point 88 is replaced with a solid underline. If the default Yorikata displayed is not the desired Yomikata, the Select key 60 is pressed repeatedly until the desired Yomikata appears. In one preferred embodiment, after all of the Yomikata in memory that match the key sequence have been displayed through repeated activation of the Select key 60, the key sequence is interpreted as a number, where each keystroke generates the digit appearing on the label of the key. This allows numbers to be generated without a separate numeric mode, and also serves as an easily recognizable indicator of the end of the selection list of Yomikata interpretations. The next press of the Select key 60 cycles back to the first Yomikata in the selection list.

Once the desired Yomikata is displayed, if the desired Midashigo (textual interpretation) is in fact identical to the Yomikata that is already displayed in hiragana text, the user proceeds to press the data key corresponding to the first kana of the next Yomikata to be entered. On the other hand, if the desired Midashigo consists of kanji, kanji plus hiragana, katakana, or some combination thereof, the user presses the Convert key 62. This causes the displayed Yomikata to be replaced with the most frequently occurring Midashigo that is associated with that Yomikata in the vocabulary module. Repeated presses of the Convert key 62 replace the displayed Midashigo with other associated Midashigo in descending order of frequency. In one preferred embodiment, after all of the Midashigo in memory that are associated with the selected Yomikata have been displayed through repeated activation of the Convert key 62, the selected Yomikata is displayed as katakana (for the embodiment with auto-inflection, only the root portion of the word is shown in katakana). This allows katakana words to be generated without a separate mode, and also serves as an easily recognizable indicator of the end of the selection list of Midashigo interpretations. In another preferred embodiment, if the user wishes to choose a Midashigo that is associated with the first (default) Yomikata associated with the input key sequence, the Convert key 62 can be pressed immediately to obtain the desired Midashigo without first pressing the Select key 60.

After one or more presses of either or both the Select key 60 and the Convert key 62, any data key that is pressed removes the special formatting (solid underline in the preferred embodiments of the displayed Yomikata or Midashigo, and becomes the first keystroke of a new key sequence to be interpreted by the system. No special keystroke is required to confirm the interpretation of the preceding keystroke sequence.

In the preferred embodiment described above, pressing the Select key 60 cycles forward through the Yomikata in memory that are associated with the current key sequence (in descending order of frequency). In another preferred embodiment, pressing-and-holding the Select key 60 past a predetermined time threshold cycles backward through the Yomikata in memory in ascending order of frequency. Thus, when the numeric interpretation is included at the end of the sequence of associated Yomikata in-memory as described above, a press-and-hold of the Select key 60 prior to any regular press of the Select key 60 cycles backward immediately to the numeric interpretation. Repeatedly pressing-and-holding the Select key 60 then cycles back up through the associated Yomikata in ascending order of frequency. Likewise, pressing-and-holding the Convert key 62 cycles backward through the Midashigo associated with the currently selected Yomikata in ascending order of frequency. Similarly, a first press-and-hold of the Convert key 62 prior to any regular press of the Convert key 62 cycles backward immediately to the katakana interpretation.

Still referring to FIG. 1a, in another preferred embodiment; when entering data keys, the Clear key 64 can be pressed to delete the previously entered data key. If all data keys in the current key sequence are thus deleted, pressing the Clear key 64 deletes the character on the text display 53 to the left of the insertion point 88, where a standard text cursor is displayed when the current selection list is empty. After one or more presses of either or both the Select key 60 and the Convert key 62, pressing the Clear key 64 replaces the currently selected textual interpretation at the insertion point 88 with the default Yomikata interpretation of the current key sequence, but does not delete any of the data keys from the key sequence. In other words, the first press of the Clear key 64 after any number of presses of the Select key 60 and/or the Convert key 62 effectively "deletes" all of the activations of the Select key 60 and the Convert key 62, returning the system to the state immediately prior to the first press of either the Select key 60 or the Convert key 62. In another preferred embodiment, after one or more presses of the Convert key 62, pressing the Select key 60 replaces the currently selected Midashigo at the insertion point 88 with the Yomikata with which the Midashigo is associated. Further presses of the Select key 60 continue to cycle forward from that point through the other Yomikata in memory that are associated with the current key sequence (in descending order of frequency).

In another preferred embodiment, activation of any other means which explicitly generates an unambiguous character (such as entering a special Symbols mode and pressing a key that is unambiguously associated with a single specific character) serves to terminate the current key sequence. As a result, any special formatting (dotted or solid underline in the preferred embodiment) of the displayed Yomikata or Midashigo at the insertion point 88 is removed, and the specific unambiguous character is appended to the output word at a new insertion point 88.

Provisionally posting the selected Yomikata or Midashigo to the text region at the insertion point 88 allows the user to maintain their attention on the text region without having to refer to the selection list. At the user's option, the system can also be configured such that, upon receipt of the first press of the Select key 60 (or Convert key 62), the Yomikata (or Midashigo) provisionally posted at the insertion point 88 can expand (vertically or horizontally) to display a copy of the current selection list. The user may select the maximum number of words to be displayed in this copy of the selection list. Alternatively, the user may elect to have the selection list always displayed at the insertion point 88, even prior to the first activation of the Select key. The disambiguating system interprets the start of the next word (signaled by the activation of an ambiguous data key or the generation of an explicit unambiguous character) as an affirmation that the currently selected entry is the desired entry. The selected word therefore remains at the insertion point 88 as the choice of the user, the underline disappears completely and the word is redisplayed in normal text without special formatting.

In the majority of text entry, keystroke sequences are intended by the user as kana forming a Yomikata. It will be appreciated, however, that the multiple characters and symbols associated with each key allow the individual keystrokes and keystroke sequences to have several interpretations. In the preferred reduced keyboard disambiguating system, various different interpretations are automatically determined and displayed to the user at the same time as the keystroke sequence is interpreted and displayed to the user as a list of words.

For example, the keystroke sequence is interpreted in terms of the word stems corresponding to possible valid sequences of kana that a user may be entering (hereinafter the "stem interpretation"). Unlike word interpretations, word stems are incomplete words. By indicating the possible interpretations of the last keystrokes, the word stems allow the user to easily confirm that the correct keystrokes have been entered, or to resume typing when his or her attention has been diverted in the middle of the word. There are key sequences which correspond to the partial entry of a long word or phrase, but which do not correspond to any completed word or phrase. In such cases, the most useful feedback that can be provided to the user is to show the kana that correspond to the stem of the word that has been entered up to that point. In the example shown in FIG. 2b, the keystroke sequencers {character pullout}, {character pullout}, {character pullout} can be interpreted as forming the valid stem "{character pullout}" (leading to the word "{character pullout}"). The stem interpretations are therefore provided as entries in the selection list. Preferably, the stem interpretations are sorted according to the composite frequency of the set of all possible words that can be generated from each stem by additional keystrokes on the data keys. The maximum number and the minimum composite frequency of such entries to be displayed may be selected by the user or configured in the system, so that some stem interpretations may not be displayed. When listing a stem interpretation in the selection list, the stem is omitted if a stem interpretation duplicates a word that appears in the selection list. When the stem is omitted, however, the word corresponding to the omitted stem may be marked with a symbol to show that there are also longer words which have this word as their stem. Stem interpretations provide feedback to the user by confirming that the correct keystrokes have been entered to lead to the entry of a desired word.

FIG. 3A is a flow chart of a main routine of the disambiguation software that processes a selection list and determines what is to be displayed at the insertion point 88 to aid the user in disambiguating ambiguous keystroke sequences. At a block 150, the system waits to receive a keystroke from the keyboard 54. Upon receipt of a keystroke, at a decision block 151, a test is made to determine if the received keystroke is a mode selection key. If so, at a block 172 the system sets a flag to indicate the current system mode. At a decision block 173, a test is made to determine if the system mode has changed. If so, at a block 171 the display is updated as needed to reflect the current system mode. If block 151 determines the keystroke is not a mode selection key, then at a decision block 152, a test is made to determine if the received keystroke is the Select key. If the keystroke is not the Select key, then at decision block 152A, a test is made to determine if the received keystroke is the Convert key. If the keystroke is not the Convert key, then at decision block 153, a test is made to determine if the system is in a special explicit character mode such as the explicit Symbols mode. If so, at decision block 166 a test is performed to determine if any provisionally selected item is present in the selection list. If so, at a block 167 the item is accepted and is output as normal text. Then, at a block 168, the explicit character corresponding to the keystroke is output to the text area. Then, at decision block 169, a test is made to determine if the system mode should be automatically changed, as in the case of Symbols mode. If so, execution proceeds to block 170 and the system mode is returned to the previously active mode, otherwise execution returns to block 150.

If at block 153 no explicit character mode is active, at a block 154 the keystroke is added to a stored keystroke sequence. At block 156, objects corresponding to the keystroke sequence are identified from the vocabulary modules in the system. Vocabulary modules are libraries of objects that are associated with keystroke sequences. An object is any piece of stored data that is to be retrieved based on the received keystroke sequence. For example, objects within the vocabulary modules may include numbers, characters, words, components of words, stems, phrases, or system functions and macros. Each of these objects is briefly described in the following table:

    Object        Corresponding data
    Numbers       A number, each digit of which corresponds to
                  a single keystroke, e.g., the two-digit
                  sequence "42".
    Characters    A character or sequence of characters corresponding
                  to pairs of keystrokes, e.g., the three
                  character sequence "{character pullout}". Each pair of
                  keystrokes is used to disambiguate using
                  the two-stroke specification method of inputting
                  characters unambiguously.
    Word          A Yomikata or Midashigo corresponding to single
                  or multiple keystrokes, e.g., the four character
                  word "{character pullout}".
    Stem          A sequence of kana representing a valid portion
                  of a longer sequence of kana forming a word, e.g.,
                  "{character pullout}" as a stem of the word "{character
     pullout}."
    Phrase        A user-defined or system-defined phrase
                  corresponding to single or multiple
                  keystrokes, e.g., "{character pullout}".
    System        A word and associated code describing a system
    Macro         or user-defined function, e.g., "<clear>"
                  to clear the current text region. In addition to the
                  descriptive word, in the vocabulary module the
                  system macro object is associated with the executable
                  code necessary for performing the specified function.