US20070094024A1 - System and method for improving text input in a shorthand-on-keyboard interface - Google Patents

Abstract

A word pattern recognition system improves text input entered via a shorthand-on-keyboard interface. A core lexicon comprises commonly used words in a language; an extended lexicon comprises words not included in the core lexicon. The system only directly outputs words from the core lexicon. Candidate words from the extended lexicon can be outputted and simultaneously admitted to the core lexicon upon user selection. A concatenation module enables a user to input parts of a long word separately. A compound word module combines two common shorter words whose concatenation forms a long word.

Description

CROSS-REFERENCE TO RELATED APPLICATIONS
• This application relates to the following co-pending U.S. patent application Ser. No. 10/325,197, titled “System and Method for Recognizing Word Patterns Based on a Virtual Keyboard Layout,” Ser. No. 10/788,639, titled “System and Method for Recognizing Word Patterns in a Very Large Vocabulary Based on a Virtual Keyboard Layout,” and Ser. No. 11/121,637, titled “System and Method for Issuing Commands Based on Pen Motion on a Graphical Keyboard,” all of which are assigned to the same assignee as the present application, and are incorporated herein by reference.
FIELD OF THE INVENTION
• The present invention generally relates to lexicon-based text entry and text prediction systems. More specifically, the present invention relates to text entry using shorthand-on-keyboard, an efficient method of entering words by drawing geometric patterns on a graphical on-screen keyboard.
BACKGROUND OF THE INVENTION
• Shorthand on graphical keyboards (hereafter “shorthand-on-keyboard”) or Shorthand on a Keyboard as Graph (sokgraph), represent an input method and system for efficiently entering text without a physical keyboard, typically using a stylus. Shorthand-on-keyboard enables the user to trace letter or functional keys on the graphical keyboard to enter words and commands into a computer. Experienced users partly or completely memorize the geometric patterns of frequently used words and commands on the keyboard layout and may draw these patterns based on memory recall using, for example, a digital pen.
• Word-level recognition-based text entry systems such as shorthand-on-keyboard and handwriting/speech recognition as well as text prediction systems all rely on some form of lexicon that defines the set of words that these systems recognize. The input of the user is matched against choices in the lexicon. Words not included in the lexicon are usually not automatically recognized. In such a case, a special mode has to be provided. For example, in shorthand-on-keyboard the user may initially check a candidate list (N-best list). If no choice on the candidate list is the intended word, the user decides if the patterns drawn were incorrect. If the patterns drawn were correct, the user realizes the word intended is not in the lexicon. The user then enters the new word in the lexicon by tapping the individual letters. Ideally, the lexicon comprises all words a particular user needs to write, no more no less. A lexicon that is either too large or too small can introduce problems to the user.
• A larger lexicon could present certain challenges, since it tends to reduce the recognition accuracy due to the likelihood of a greater number of distracters for each user input. In any language, there tends to be a core set of vocabulary that is common to all individuals. Beyond this core set, vocabulary tends to be specialized for a particular individual. For instance, an engineer may compose emails comprising highly technical terms and abbreviations for a particular field or business area. For other users, these specialized terms can be irrelevant and can introduce noise in the recognition process, making the recognition process less robust.
• A smaller lexicon is typically a more robust lexicon in that user input is more likely to be correctly recognized, provided the intended word is in the lexicon. A smaller lexicon provides more flexibility and tolerance for the input of the user, allowing the input to be imprecise and inaccurate compared to the ideal form of the intended input choice. A further advantage of a small lexicon is that the search space is smaller. Consequently, a small lexicon allows reduction in the latency of a search. This is especially important in mobile devices where processing power is severely limited.
• However, when a small lexicon does not contain the word the user needs, the user experience can be frustrating. A user does not know, prior to entry, whether a word is in the lexicon, causing uncertainty for the user. The lack of recognition of a word by a conventional system can occur either when the word is input incorrectly or when the word is not in the lexicon. Consequently, it can be difficult for the user to determine why a word is not recognized. In general, the user cannot know whether a word is in the lexicon except by repeatedly trying the word. When the user is certain that the word is not in the lexicon, the user adds that word to the lexicon via an interface provided by the recognition system by tapping as described earlier. A smaller lexicon requires a user to add words to the lexicon more often.
• There are several conventional solutions to the lexicon size issue. A commonly used method is to use a large lexicon and then take advantage of higher order language regularities such as a word-level trigram-model to filter out highly unlikely candidates. The downside of a language model approach is generally the overhead of creating and making efficient use of a large language model. Moreover, a language model can introduce errors and mistakenly filter out the intended words. This is especially true if the language model is generic rather than customized to a particular user. In practice, efficient customization of a language model is difficult. Furthermore, a language model is difficult to integrate with a recognition technique that already has a high precision, such as shorthand-on-keyboard.
• An alternative conventional approach creates a customized lexicon for a user by mining the written text generated by the user, for example, written emails and other documents. Although this approach does result in a lexicon more closely tailored to a specific user, a previously written corpus generated by a user may be to be too small to cover all of the desired words. Furthermore, in practice, it is difficult to write a computer program code that can open and read all and various email and document formats that the user may be using. This approach often requires the user to locate and select the previous written documents, which is inconvenient for the user. A customized lexicon may also be difficult to carry over across different devices.
• Although these conventional solutions are adequate for their intended purpose, it is desirable to find a solution that enables a lexicon to have a relatively small number of irrelevant distracters to the user's desired input and yet allows easy access to almost all words the user may need, including more specialized words that are infrequently used by most users. Overall, there is a desire to include all words possibly needed by the user in a very large lexicon. However a very large lexicon implies that more words match the pattern drawn on the keyboard given the same matching threshold, reducing the signal-to-noise ratio in the input system. Consequently, a larger lexicon corresponds to less flexibility and robustness to the user. Thus, there is a need for a lexicon configuration for a shorthand-on-keyboard system that balances ease of use with flexibility and robustness.
• Another challenge to a conventional shorthand-on-keyboard input method is a requirement of entering text exactly at the word level, one word at a time. Some words are long. For relatively new users, it can be cognitively difficult to draw a long word with shorthand-on-keyboard in one stroke. This difficulty is particularly acute in some European languages in which compound long words are more common than in English. Furthermore, a user can find entry more convenient if common affixes can be drawn as a separate stroke from the stem of the word. For example, to write the word “working” with shorthand-on-keyboard, the user may wish to draw the pattern of w-o-r-k on a graphical keyboard, then draw i-n-g and combine the two into one word. Thus, there is a need for an effective system and method to automatically combine partial words on the keyboard (“sokgraphs”) into one word as intended by the user.
• What is therefore needed is a system, a computer program product, and an associated method for a system and method for improving text input in a shorthand-on-keyboard interface. The need for such a solution has heretofore remained unsatisfied.
SUMMARY OF THE INVENTION
• The present invention satisfies this need, and presents a system, a computer program product, and an associated method (collectively referred to herein as “the system” or “the present system”) for improving text input in a shorthand-on-keyboard interface. The present system comprises a core lexicon and an extended lexicon. The core lexicon comprises commonly used words in a language. The core lexicon typically comprises approximately 5,000 to 15,000 words, depending on an application of the present system. The extended lexicon comprises words not included in the core lexicon. The extended lexicon comprises approximately 30,000 to 100,000 words.
• The core lexicon allows the present system to target commonly used words in identifying a gesture as a highest-ranked candidate word, providing more robust recognition performance associated with a smaller lexicon. Only words from the core lexicon can be directly outputted in the present system. Additional candidate words are available from the extended lexicon, allowing a user to find lesser-known words on the candidate list, but only through menu selection. The present system enhances word recognition accuracy without sacrificing selection of words from a large lexicon. The core lexicon provides more flexibility and tolerance for the input of the user to be imprecise and inaccurate from the ideal form of the intended input choice.
• The present system further comprises a recognition module, a pre-ranking module, and a ranking module. The recognition module generates an N-best list of candidate words corresponding to an input pattern. The pre-ranking module ranks the N-best candidate words according to predetermined criteria. The ranking module adjusts ranking of the N-best list of candidate words to place words drawn from the core lexicon higher than words drawn from the extended lexicon, generating a ranked list of word candidates. Only words in the core lexicon are presented as output by the present system. The present system lists candidate words found in the extended lexicon only in the N-best list; these words require user selection to become output. Once selected by a user from the N-best list, a word from the extended lexicon is admitted to the core lexicon.
• More specifically, in a preferred embodiment, only words in the core lexicon are outputted by the recognition system. Words in the extended lexicon can only be listed in the N-best list and need explicit user selection to be outputted. Once selected, the words in the extended lexicon also gets admitted to the core lexicon.
• The present system reduces the overhead inflicted upon the user in the case the word gestured by the user is not in the vocabulary of the core lexicon. Instead of being unsure whether the word is included in the lexicon or if the system misrecognized the input, the user can scan the N-best list and select the desired candidate word.
• The present system further comprises a concatenation module and a compound word module. The concatenation module enables a user to input parts of a long word separately; the present system automatically combines words and part-of-words that are partial “sokgraphs” into one word that is intended by the user. Word parts can be stems, such as “work” and affixes, such as “ing” or “pre”. The compound word module combines two or more common shorter words whose concatenation forms a long word, such as short+hand in English. The concatenation of several short words into one compound word is more common in some European languages such as Swedish or German.
• The present system allows user interaction to adjust concatenation of aword1 and aword2 and decoupling of a combined word. When the user clicks on a concatenated word, for example “smokefree”, a menu option “split to “smoke free”” or an equivalent option is given to the user. Alternatively a pen trace motion, such as a downward motion crossing the word smokefree, can be defined as a split command. For concatenable words with no action due to low confidence, a menu option is embedded inword1 andword2. When the user clicks onword1, the option “snap to right” or an equivalent option is selectable. When the user clicks onword2, the option “snap to left” or an equivalent option is selectable. Alternatively a pen gesture, such as a circle crossing bothword1 andword2, is defined as the command to join the two words as one concatenated long word.
BRIEF DESCRIPTION OF THE DRAWINGS
• The various features of the present invention and the manner of attaining them will be described in greater detail with reference to the following description, claims, and drawings, wherein reference numerals are reused, where appropriate, to indicate a correspondence between the referenced items, and wherein:
• FIG. 1 is a schematic illustration of an exemplary operating environment in which a word pattern recognition system of the present invention can be used;
• FIG. 2 is a block diagram of a high-level architecture of the word pattern recognition system ofFIG. 1;
• FIG. 3 is a process flow chart illustrating a method of operation of the word pattern recognition system ofFIGS. 1 and 2 in ranking candidate words according to location in a core lexicon or an extended lexicon;
• FIG. 4 is a diagram illustrating an N-best list generated by the word pattern recognition system ofFIGS. 1 and 2 in which words from the core lexicon and words from the extended lexicon are displayed differently;
• FIG. 5 is a diagram illustrating an N-best list generated by the word pattern recognition system ofFIGS. 1 and 2 in which words from the core lexicon are grouped and ranked higher than words from the extended lexicon;
• FIG. 6 is a process flow chart illustrating a method of operation of the word pattern recognition system ofFIGS. 1 and 2 in recognizing a word candidate as a suffix or a prefix and concatenating the recognized prefix or suffix to a recognized word in a language appropriate manner;
• FIG. 7 is a process flow chart illustrating a method of operation of the word pattern recognition system ofFIGS. 1 and 2 in combining words into a compound word;
• FIG. 8 is comprised ofFIGS. 8A, 8B, and8C and represents a diagram illustrating a menu of the word pattern recognition system ofFIGS. 1 and 2 in which the menu enables a user to split a compound word into a stem and a suffix;
• FIG. 9 is a diagram illustrating a pen gesture formed by a user on a compound word presented by the word pattern recognition system ofFIGS. 1 and 2 in which the pen gesture splits a compound word into a stem and a suffix;
• FIG. 10 is comprised ofFIGS. 10A, 10B, and10C and represents a diagram illustrating a menu of the word pattern recognition system ofFIGS. 1 and 2 in which the menu is applied to a stem to enable a user to combine a stem and a suffix into a compound word;
• FIG. 11 is a diagram illustrating a menu of the word pattern recognition system ofFIGS. 1 and 2 in which the menu is applied to a suffix enabling a user to combine a stem and a suffix into a compound word; and
• FIG. 12 is a diagram illustrating a pen gesture formed by a user on a stem and a suffix presented by the word pattern recognition system ofFIGS. 1 and 2 in which the pen gesture combines the stem and the suffix into a compound word.
DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS
• The following definitions and explanations provide background information pertaining to the technical field of the present invention, and are intended to facilitate the understanding of the present invention without limiting its scope:
• Lexicon: a collection of elements defining the recognizable elements that can be matched against a user's input in a recognition system.
• PDA: Personal Digital Assistant. A pocket-sized personal computer. PDAs typically store phone numbers, appointments, and to-do lists. Some PDAs have a small keyboard; others have only a special pen that is used for input and output on a virtual keyboard.
• Sokgrah: Shorthand on a Keyboard as a Graph. A pattern representation of words on a virtual keyboard.
• Virtual Keyboard: A computer simulated keyboard with touch-screen interactive capability that can be used to replace or supplement a keyboard using keyed entry. The virtual keys are typically tapped serially with a stylus. It is also called graphical keyboard, on-screen keyboard, or stylus keyboard.
• FIG. 1 portrays an exemplary overall environment in which a system, a computer program product, and an associated method for improving text input in a shorthand-on-keyboard interface (the wordpattern recognition system10 or the “system10”) according to the present invention may be used.System10 includes a software program code or a computer program product that is typically embedded within, or installed on a computer. The computer in whichsystem10 is installed can be a mobile device such as aPDA15 or acellular phone20.System10 can also be installed in devices such astablet computer25,touch screen monitor30, electronicwhite board35, anddigital pen40.
• System10 can be installed in any device using a virtual keyboard or similar interface for entry, represented byauxiliary device45.System10 can be saved on a suitable storage medium such as a diskette, a CD, a hard drive, or like devices.
• System10 determines a word from the shape and location of a pen stroke formed by a user on a graphical keyboard.System10 sends the determined words to a software recipient such as, for example, an application, an operating system, etc.
• FIG. 2 illustrates a high-level hierarchy ofsystem10.System10 comprises alexicon205. Thelexicon205 comprises acore lexicon210 and anextended lexicon215. Thecore lexicon210 comprises commonly used words in a language. Thecore lexicon210 typically comprises approximately 5,000 to 15,000 words, depending on an application ofsystem10. Theextended lexicon215 comprises words not included in thecore lexicon215. Theextended lexicon215 comprises approximately 30,000 to 100,000 words.
• System10 further comprises arecognition module220, apre-ranking module225, and a selector/rankingmodule230. Therecognition module220 generates an N-best list of candidate words corresponding to aninput pattern235. Thepre-ranking module225 ranks the N-best candidate words according to predetermined criteria. Theranking module230 adjusts ranking of the N-best list of candidate words to place words drawn from thecore lexicon210 higher than words drawn from theextended lexicon215, generating a ranked list ofword candidates240. As explained earlier, words drawn from the extended lexicon are not outputted; only words from the core lexicon are outputted.
• System10 further comprises aconcatenation module245 and acompound word module250. Theconcatenation module245 concatenates words selected from the ranked list ofword candidates240; e.g., concatenating “ing” with “code” to form “coding”. Thecompound word module250 combines words selected from the ranked list ofword candidates240 into larger words. Anoutput word255 is a word selected from the ranked list ofword candidates240 and processed by theconcatenation module245 and thecompound word module250, as necessary. Only words in thecore lexicon210 are presented as theoutput word255 bysystem10.System10 lists candidate words found in theextended lexicon215 only in the N-best list; these words require user selection to become theoutput word255. Once selected by a user,system10 admits a word from theextended lexicon215 to thecore lexicon210.
• System10 adapts recognition of theinput pattern235 by therecognition module220 to the vocabulary of the user while maintaining maximum signal to noise ratio in the recognition system.System10 allows thecore lexicon210 and theextended lexicon215 to participate in the recognition process of therecognition module220. However, only words in thecore lexicon210 directly enter output of therecognition module220; these words are a default output. Words in theextended lexicon215 that match theinput pattern235 are only listed in an “N-best” list for selection by the user. When a user selects one of these candidate words from the N-best list to replace the default output, the selected word is admitted tocore lexicon210. After a word is admitted to thecore lexicon210, the admitted word can directly enter the output of the recognition module when the word matches theinput pattern235.
• FIG. 3 illustrates amethod300 ofsystem10 in generating an N-best list of candidates that match theinput pattern235. The user gestures a word on a shorthand-on-keyboard interface (step305). Therecognition module220 generates an N-best list of word candidates (step310); thepre-ranking module225 ranks the N-best list of word candidates from thecore lexicon210 and theextended lexicon215 according to a criterion such as a confidence value or a similarity measure (step315).
• Theranking module230 determines whether the highest ranked word in the N-best list of candidate words is drawn from the core lexicon210 (decision step320). If yes, theranking module230 outputs the ranked N-best list of word candidates as the ranked list of word candidates240 (step325). If the highest ranked candidate in the N-best list of candidate words is not present in thecore lexicon210, theranking module230 searches the N-best list of candidate words to locate the highest ranking word candidate drawn from the core lexicon210 (step330).
• If a word candidate drawn from thecore lexicon210 is not found in the N-best list of candidate words (decision step335), theranking module230 outputs the ranked N-best list of word candidates as the ranked list ofword candidates240. Otherwise, theranking module230 moves the found word candidate to the highest-ranking position in the N-best list of word candidates (step335). The ranking module outputs the ranked N-best list of word candidates as the ranked list of word candidates240 (step340).
• To allow users to select a candidate word that is not highest ranked, a user interface component displays the next best candidate list (N-best list) from which a user can see alternative candidate words that closely match theinput pattern235. In one embodiment, the position of a candidate word on the list is determined by a rank associated with the candidate word independent of whether the candidate word is found in thecore lexicon210 or theextended lexicon215, with the exception of the highest ranked word must always be found in the core lexicon with the exception when no word in the core lexicon matches the user's input. In another embodiment, candidate words are grouped by lexicon origin; i.e., candidate words from thecore lexicon210 are grouped together and candidate words from theextended lexicon215 are grouped together.
• The origin of the candidate words can optionally be indicated by emphasizing different perceptual features that are associated with the candidate words, to facilitate the recognition of the source of the candidate words, e.g., from the core or extended lexicon. Exemplary perceptual features include, for example: color, background shading, bold fond, italicized font, etc. If a user selects no word,system10 outputs the highest ranked word in the N-best list of candidate words from the core lexicon. If a user does not select a word,system10 outputs the highest ranked word in the N-best list of candidate words from the core lexicon.
• Words drawn from theextended lexicon215 are accessed from the N-best list of candidate words. Consequently, error tolerance ofsystem10 in generating the highest-ranked candidate is greatly enhanced, since the highest-ranked candidate that is displayed by the system is drawn from thesmaller core lexicon210. In rare situations in which the desired word is not found in thecore lexicon210, the user activates the N-best list and selects the desired candidate.
• FIG. 4 illustrates an exemplary N-best list ofcandidate words400 generated by theranking module230. Candidate words from thecore lexicon210comprise candidate word1,405,candidate word2,410, andcandidate word3,415, collectively referenced ascore candidate words420. Candidate words from theextended lexicon215comprise candidate word4,425,candidate5,430,candidate word6,435,candidate word7,440, andcandidate word8,445, collectively referenced asextended candidate words450.Core candidate words420 andextended candidate words450 are displayed with different emphasis.
• In this example,core candidate words420 are shown in bold text andextended candidate words450 are shown in italicized text. Any form of emphasis may be used to differentiate thecore candidate words420 and theextended candidate words450 such as, for example, text color, color background, shading, etc. The candidate words in the exemplary N-best list ofcandidate words400 are positioned according to rank given by therecognition module220, with the exception of the topword candidate position455 that is reserved for a word drawn from thecore lexicon210 unless no word from the core lexicon matches the user's input, in which case topword candidate position455 may be taken by a word from the extended lexicon.
• FIG. 5 illustrates one embodiment in which an exemplary N-best list500 comprises candidate words ranked according to source and according to ranking criteria provided by therecognition module220. As forFIG. 4,core candidate words420 andextended candidate words450 are displayed with different emphasis. In this example,core candidate words420 are shown in bold text andextended candidate words450 are shown in italicized text.
• System10 greatly reduces the overhead inflicted upon the user in the case the word gestured by the user is not in the vocabulary of thecore lexicon210. Instead of being unsure whether the word is included in thecore lexicon210 or if the system misrecognized the input, the user can scan the N-best list and select the desired candidate word.
• For those familiar with the state of the art, it should be apparent that the division of words into separate lexicons is one implementation that is also a simple conceptual model. Alternatively thelexicon205 can be conceptualized as layers, a core lexicon layer and an extended lexicon layer, ranked by frequency or priori probability. When a word from the extended lexicon layer is selected from the N-best candidate interface, the frequency or priori probability of the selected word is adjusted to a threshold or other criterion having the effect that the selected word is adjusted to belong to the core layer.
• System10 further enables a user to input parts of a long word separately;system10 automatically combines partial “sokgraphs” into one that is intended by the user. Word parts can be stems, such as “work” and affixes, such as “ming”, or two or more common shorter words whose concatenation forms a long word, such as short+hand in English. The concatenation of several short words into one compound word is more common in some European languages such as Swedish or German.
• Concatenations are based on individually recognizing parts involved in the concatenated word. For the case of stem+suffix, the user initially gestures aninput pattern235 for a word that represents the stem, then gestures aninput pattern235 of the suffix. For example for the word “coding”, the user initially writes the gesture for “code”, then writes the gesture for “ing”. For an input trace on the keyboard, therecognition module220 finds the optimum matches and outputs these matches to an N-best list with strings S_(i),iε[1,N], where a rank i of a string signifies the confidence of therecognition module220 in the selected string matchinginput pattern235. The string with the rank i=1 is the top choice of therecognition module220. Therecognition module220 stores the last N-best list in a temporary buffer. The buffered N-best list for a regular word (stem) is denoted as S₀.
• In one embodiment, suffixes are stored in a list called concatenable suffixes whose sokgraphs, the geometric pattern on a graphical keyboard, are represented in the same way as a common word sokgraph. For example, for the suffix “ing”, its sokgraph is a continuous trace starting from the i key to the n key ending on the g key. The system recognizes aninput pattern235 for sokgraph “ing” in the same way as any other sokgraph, except the suffix “ing” is stored in the list of concatenable suffixes. Alternatively both suffixes and regular words can be stored in the same lexicon, but with an identifier differentiating the suffix from the regular word. In one embodiment, concatenable suffixes are stored in a lookup table in which each suffix entry, such as “ing”, is associated with a series of pointers that point to the entries in a lexicon that ends with that suffix
• FIG. 6 illustrates amethod600 ofsystem10 in combining concatenable suffixes with a stem word. A user gestures a word on a shorthand-on-keyboard interface (step605). Theconcatenation module245 obtains a highest ranked word for an output N-best list of word candidates240 (step610). Theconcatenation module245 determines whether the obtained word is a concatenable suffix by, for example, comparing the obtained word with a list of concatenable suffixes (decision step615). If the obtained word is not a concatenable suffix, theconcatenation module245 takes no action (step620).
• If the obtained word is a concatenable suffix, theconcatenation module245 finds concatenation candidates that end with the determined concatenable suffix (step625). Theconcatenation module245 strips the concatenable suffix from each concatenation candidate (step630). Words ending with a current suffix (e.g. “ing”) are denoted as S_1(i)(e.g. coding or working) and their remainders stripped of the suffix are denoted S_2(i)(e.g. “cod” or “work”).
• Theconcatenation module245 computes the string edit distance (specifically: the Morgan editing error using the Wagner-Fisher algorithm) between the stripped concatenation candidates and the concatenable suffix (step635). The remainders S_2(i)are then matched against the top choice S₀₍₁₎in the buffered N-best list. Since S₀contains whole words, not fragments of words (for example S₀₍₁₎=code) the matching is inexact.System10 uses edit-distance (the minimum number of edit operations chosen from insertion, deletion, or substitution of a single character) to match two strings) to find the string in s_2(i)(i=1,N) that is closest to s₀₍₁₎and denote it as s_{2 min}. Theconcatenation module245 sorts the concatenation candidates by the associated edit distance (step640). Theconcatenation module245 returns the concatenation candidate with the smallest edit distance (step645).
• In an alternative embodiment word frequencies or prior probabilities, or higher-order language regularities are used to rank concatenation candidates that share the same edit distance.
• The word corresponding to s_{2 min}in S_1(i)is returned as the concatenation candidate of choice. For example “code” is closer by edit-distance to “cod” (the stripped part of “coding”) than “code” to “work” (the stripped part of “working”). In one embodiment, a threshold can be set as the lowest acceptable edit-distance mismatch.
• In another embodiment suffixes are not linked to all words that end with the suffix. Instead, when a suffix is recognized, thesystem10 scans thelexicon205, finds words that end with the recognized suffix, strips the ending from the found words, matches the stripped remainders with the preceding word, and selects the closest match for concatenation as previously described. The difference between these two embodiments lies in computational time and memory space tradeoff. Scanning the lexicon implies that a separate list of pointers is not needed, hence reducing the storage requirement of the lexicon in the medium the software code is accessing. On the other hand, scanning the lexicon requires more time than to locate a word than a system comprising a lexicon that is indexed with a separate list of pointers.
• System10 treats prefix+stem in a manner similar to stem+suffix. Theconcatenation module245 initially recognizes a prefix-based word from the output of the ranked list ofword candidates240 from either a separate list of prefixes or a common lexicon with a prefix identifier. Theconcatenation module245 then recognizes the word that follows the prefix. Theconcatenation module245 matches all words containing the prefix, strips the matched word of the prefix, and returns the closest match for concatenation.
• The concatenation of two shorter words into a long one is not deterministic. For example, in Swedish both “smoke free” and “smokefree” are permitted, but their meanings are opposite (smoking allowed as opposed to smoking not allowed). Thecompound word module250 uses a statistical and interactive method to handle the concatenation of two words. To support this method,system10 stores in thelexicon205 the statistical information including the frequencies of all words (based on the total number of occurrence of each word in a corpus of text) and frequencies of all bigrams (based on the total number of occurrence of two ordered words).
• FIG. 7 illustrates amethod700 ofsystem10 in combining words into compound words.Method700 examines pairs of consecutive words (word1, word2) (step705). Thecompound word module245 determines whether the combined consecutive words (word1+word2=word3) are found in the lexicon205 (decision step710). If the combined word,word3, is not found, thecompound word module250 takes no action (step715). If a match (word3=word1+word2) is found, thecompound word module250 compares the frequency ofword3 with bigram (word1, word2) (step720). If the frequency ofword3 is greater than the frequency of bigram (word1, word2) compared to a predetermined threshold or the ratio of the frequency ofword3 with respect to the frequency of bigram (word1, word2) is greater than a predetermined threshold (decision step725), the compound word module replacesword1 andword2 with word3 (step730). Otherwise, no action is taken (step715). Alternatively, the comparison of the frequency ofword3 and the frequency of the bigram (word1, word2) is a weighted comparison.
• System10 provides a user interface that enables user interaction for adjusting concatenation and decoupling.FIG. 8 (FIGS. 8A, 8B,8C) illustrates decoupling of a combined word into two individual words or parts of words. Anexemplary screen805 displays to a user an exemplary concatenated word “coding”810. The user selects the displayed concatenated word “coding” by, for example, clicking on the word “coding”810 (FIG. 8A). Selecting the word “coding”810 displays amenu option815 comprising, for example, selectable instruction “Split to “Code” and “ing”” or an equivalent option (FIG. 8B). If the user selects the instruction shown inmenu option815,system10 splits the displayed concatenated word “coding”810 into stem “code”820 and suffix “ing”825 (FIG. 8C).
• FIG. 9 illustrates an exemplary alternativepen trace motion905 used to split the concatenated word “coding”810. Thescreen805 displays to the user a concatenated word “coding”810. The user forms thepen trace motion905 over the concatenated word “coding”810.System10 splits the displayed concatenated word “coding”810 into stem “code”820 and suffix “ming”825 as illustrated inFIG. 8C.
• For concatenable words with no action due to low confidence, a menu option is embedded inword1 andword2 as illustrated inFIG. 10. For example, thescreen805 displays to the user aword1 “code”1005 and aword2 “ing”1010 as shown inFIG. 10A. Selecting theword1 “code”1005 displays anoption menu1015 comprising a selectable instruction “snap to right” or an equivalent option (FIG. 10B). If the user selects the instruction “snap to right” shown in theoption menu1015,system10 concatenates theword1 “code”1005 and theword2 “ming”1010, forming the concatenated word “coding”1020 (FIG. 10C).
• FIG. 11 illustrates anexemplary option menu1105 displayed when the user selects theword2 “ming”1010. If the user selects the instruction “snap to left” shown in theoption menu1105,system10 concatenates theword1 “code”1005 and theword2 “ming”1010, forming the concatenated word “coding”1020 as shown inFIG. 10C.
• FIG. 12 illustrates an exemplary alternativepen trace motion1205 used to concatenate theword1 “code”1005 and theword2 “ing”1010. Thepen trace motion1205 comprises, for example, a circle crossing theword1 “code”1005 and theword2 “ming”1010.System10 recognizes the command represented by thepen trace motion1205 and concatenates theword1 “code”1005 and theword2 “ing”1010, forming the concatenated word “coding”1020 as shown inFIG. 10C.
• It is to be understood that the specific embodiments of the invention that have been described are merely illustrative of certain applications of the principle of the present invention. Numerous modifications may be made to the system and method for improving text input in a shorthand-on-keyboard interface described herein without departing from the spirit and scope of the present invention.

Claims (22)

1. A word recognition system for recognizing an input signal entered via a shorthand-on-keyboard interface, the system comprising:

a core lexicon comprising commonly used words;

an extended lexicon comprising words not contained in the core lexicon;

a recognition module for recognizing words associated with the input signal;

a selector module for outputting an output word associated with the input signal from the core lexicon; and

a module for admitting a candidate word associated with the input signal to the core lexicon, upon selection of the candidate word by the user.

2. The system ofclaim 1, further comprising a user selection interface presenting candidate words associated with the input signal from at least one of the core lexicon and the extended lexicon, for selection by the user.

3. The system ofclaim 2, wherein the user selection interface lists candidate words from the core lexicon and candidate words from the extended lexicon with different perceptual features for ease of distinction.

4. The system ofclaim 1, wherein the recognition module generates an N-best list of candidate words from the core lexicon and the extended lexicon.

5. The system ofclaim 4, further comprising a pre-ranking module for ranking the N-best list of candidate words according to at least one criterion.

6. The system ofclaim 5, wherein the ranking module outputs a highest ranked word from the core lexicon as the highest ranked word in the N-best list of candidate word.

7. A word recognition method for recognizing a input text entered via a shorthand-on-keyboard interface, the method comprising:

storing commonly used words on a core lexicon;

storing words not contained in the core lexicon in an extended lexicon;

recognizing words associated with the input signal;

outputting an output word associated with the input text from the core lexicon; and

admitting a candidate word associated with the input text to the core lexicon, upon selection of the candidate word by a user.

8. The method ofclaim 7, further comprising presenting candidate words associated with the input signal from at least one of the core lexicon and the extended lexicon, for selection by the user.

9. The method ofclaim 8, further comprising listing candidate words from the core lexicon and candidate words from the extended lexicon with different perceptual features for ease of distinction.

10. A computer program product having program codes stored on a computer-usable medium for word for recognizing an input signal entered via a user input interface, comprising:

a core lexicon comprising commonly used words;

an extended lexicon comprising words not contained in the core lexicon;

a program code for recognizing words associated with the input signal;

a program code for outputting an output word associated with the input signal from the core lexicon; and

a program code for admitting a candidate word associated with the input signal to the core lexicon, upon selection of the candidate word by the user.

11. A system for recognizing an input signal entered via a shorthand-on-keyboard interface and for allowing a stem and an affix of the input text to be combined, the system comprising:

a concatenation module for recognizing the input signal as an input affix;

the concatenation module further recognizing a candidate word as neighboring candidate word;

a compound output module for retrieving a set of words in a lexicon containing the input affix;

a ranking module for ranking the set of words containing the input affix according to a similarity function that compares each lexicon word in the set of words containing the input affix, with a string containing the candidate word and the input affix; and

the compound word module outputting a highest ranked lexicon word in the set of words containing the input affix.

12. The system ofclaim 11, wherein the input affix is a suffix.

13. The system ofclaim 12, wherein the compound word module compounds the suffix and the highest ranked lexicon word.

14. The system ofclaim 11, wherein the input affix is a prefix.

15. The system ofclaim 14, wherein the compound word module compounds the prefix and the highest ranked lexicon word.

16. The system ofclaim 14, wherein the similarity function includes a distance function.

17. The system ofclaim 14, wherein the neighboring candidate word includes any one of a candidate word that precedes the input affix or a candidate word that succeeds the input affix.

18. The system ofclaim 17, wherein if the input text is not recognized as the input affix, the compound word module creates a string resulting from a concatenation of the input text and the neighboring candidate word; determines a frequency of occurrence of the string in the lexicon; compares the frequency of occurrence of the string to frequencies of occurrence of the input text and the neighboring candidate word separately; and if the frequency of occurrence of the string exceeds the frequencies of occurrence of the input text and the neighboring candidate word separately, the compound word module concatenates the input text and the neighboring candidate word as a concatenated word, and replaces the string with the concatenated word.

19. The system ofclaim 18, wherein a comparison of the frequency of occurrence of the string relative to the frequencies of occurrence of the input text and the neighboring candidate word is a weighted comparison.

20. A method for recognizing an input text entered via a shorthand-on-keyboard interface and for allowing a stem and an affix of the input text to be combined, the method comprising:

recognizing the input text as an input affix;

if the input text is recognized as the input affix, recognizing a candidate word as neighboring candidate word;

retrieving a set of words in a lexicon containing the input affix;

ranking the set of words containing the input affix according to a similarity function by comparing each lexicon word in the set of words containing the input affix, with a string containing the candidate word and the input affix; and

outputting a highest ranked lexicon word in the set of words containing the input affix.

21. The method ofclaim 19, further comprising compounding the suffix and the highest ranked lexicon word.

22. A computer program product having program codes stored on a computer-usable medium for recognizing an input signal and for allowing a stem and an affix of the input text to be combined, comprising:

a program code for recognizing the input signal as an input affix, and for further recognizing a candidate word as neighboring candidate word;

a program code for retrieving a set of words in a lexicon containing the input affix;

a program code for ranking the set of words containing the input affix according to a similarity function that compares each lexicon word in the set of words containing the input affix, with a string containing the candidate word and the input affix; and

a program code for outputting a highest ranked lexicon word in the set of words containing the input affix.

Images