WO2008116843A2 - Method for word recognition in character sequences - Google Patents

Abstract

The method according to the invention for word recognition in sequences of N characters, of which one or more characters may be ambiguous, uses a memory (15), a display (13), and a processor device (12). The memory comprises n-grams (character chains with a length n) and frequency values associated with said character chains, with the total number of all n-grams in a language sample used for word recognition being used as the frequency value of an n-gram. The display (12) shows selected n-grams and/or recognized words, wherein the processor device (12) is connected to the memory (15) and the display (13). A list L of all n-grams with N characters that may be formed from the individual characters in the N-character sequence, taking into account the ambiguity of the characters present in said sequence, is prepared from an examined character sequence. All n-gram combinations with a word probability of zero are removed from the list L of possible n-gram combinations, wherein the word probability p = ∏ pn is determined from the n-grams included in the character sequence with n = 1 to N-1. The words (14) represented by the remaining n-gram combinations from the list L are displayed.

Description

 PROCEDURE FOR WORK RECOGNITION IN CHARACTER SEQUENCES

The invention relates to a method for word recognition in sequences of N characters, one or more of which may be ambiguous.

Electronic recording of texts and language has become inzwi ^¬ rule routine. However, it is not error-free, takes too long, requires too much memory or is not flexible enough in terms of the devices or languages used.

The electronic recording of texts and speech is used, for example, when entering text in keyboards. The most efficient and most common is the normal computer keyboard, which provides a key for each letter key or for each character to be entered, or defines a Tastenkombina ^¬ tion. Other keyboards have fewer keys, such as cell phones for sending text messages or PDAs for appointment input, special keyboards such as QWERTY keyboards, keyboards for the disabled or keyboards from Special equipment. When entering text into such keyboards, it is necessary to multiple assignments of the keys, so that the keys usually have to be pressed several times to activate the desired letter (Mulitap method). In the case of a conventional mobile phone, for example, there is a common ABC A 2 key, and when typing the word "Baumhaus", for example, the key sequence 222886442887777 must be pressed (indicated in numbers), but this will result in a unique word. Assuming a usual German From ^¬ reproducing alphabet without upper / lower case

0 (2) = {a, ä, b, c}

0 (3) = {d, e, f}

0 (4) = {g, h, i}

0 (5) = {j, k, 1}

0 (6) = {m, n, o, ö}

0 (7) = {p, q, r, s, ß}

0 (8) = {t, u, ü, v}

0 (9) = {w, x, y, z}

arise for the word "tree house" (number sequence 22864287)

4 * 4 * 4 * 4 * 3 * 4 * 4 * 5 = 61,440

possible letter combinations, if for each letter of the entered word each key is pressed only once. These letter combinations go from "aatmgatw" to "baumhaus" to "ccvöicvß". Among these, impossible combinations such as "ääüöiäüq" (also numbered 22864287) must be excluded and a reasonable list of possible words (hypotheses) offered, eg for the number sequence 343 "the", "marriage", "oath", the former possibility most common. This is the task of word recognition ^methods .

There are also ambiguities in voice input, For example, for difficult sounds such as "s" and "f", whose message frequencies are mostly outside of 3.4 kHz (upper limit of the telephone transmission frequency). Also, there can be different spellings for the same phoneme, ie when writing is made, as is spoken, assignment and selection decisions are made (/ f / -> f, v, ph, / a / -> a, aa, ah) , Phonem dictionaries have already been used.

Also, for example, when reading electronic text files, such as when they contain input text or speech or are digital documents, there may be virtually similar problems in recognizing those files until the words are resolved.

The following description of the state of the art and of the invention relates primarily to text recognition when entering keyboards for which the invention was initially intended. However, the invention is not limited to this field of application, but also applicable to the above-described and other areas of text recognition and analysis or speech recognition.

For word recognition, various character disambiguation methods have been used to correct the ambiguities. Some are based on the use of so-called n-grams, ie of contiguous character sequences with n characters. n-grams have been used in the analysis of large amounts of data on specific contexts (or phrases), for example, by the intelligence service, such as the search of emails on selected topics etc .. They are also used for sentence recognition due to predetermined word sequences, the n- Gramme in this context. In the case of word recognition by means of n-grams, character sequences (also: strings) are compared with n-grams, which can have different lengths. A combination of different lengths of n-grams has proven useful where the shorter n-grams provide alternative predictions and the longer n-grams provide greater unambiguity, but have a high memory requirement, so that n> 6 does not occur in practice. Due to the different length of the n-grams, the frequencies of the individual letters, bigrams, trigrams and also short words are taken into account. The disadvantage of using the n-gram method is that the documents are only very short. Great attention has been given to the publication "Probalistic Character Disambiguation for Reduced Keyboards Using Small Text Samples" published in 1992 by JL Arnott and MY Javed, AAC Augmentative and Alternative Communication, Vol. 8, pages 215 to 223.

If, for example, the word "tree house" is decomposed into n-grams of lengths 2 to 5, the following n-grams Vn (baumhaus) result:

n = 2 V2 (tree house) = {ba, au, um, mh, ha, au, us} n = 3 V3 (tree house) = {construction, aum, umh, mha, hau, aus} n = 4 V4 (baumhaus ) = {tree, aumh, umha, mhau, house} n = 5 V5 (tree house) = {tree, aumha, umhau, mhaus}

The following frequencies are counted for some selected n-grams:

W2 (au) = 2

W3 (aum) = 1

W4 (tree) = 1

W5 (tree) = 1

Of course, n-grams that were not observed have a frequency of 0, e.g. W3 (lqü) = 0.

All known words of a language can now be composed of n-grams. For example, there are 30 letters in German (excluding upper and lower case), which limits the maximum number of possible n-grams: n = 2,900 n = 3 27,000 n = 4,810,000 n = 5 24,300,000

With the special application mobile phone of the intelligent text systems, without whose input the text input according to the Multitap method takes place, there are only a few developments introduced on the market.

Very common is the T9 method of Tegic Communications, Inc. for disambiguation of input character sequences described in US 6,307,549 Bl. A plotted character sequence is compared with stored vocabulary or word modules for correspondence. If there are several alternatives, these are presented in a selection list and an alternative selected by the user. For the vocabulary or word ^¬ modules a tree data structure may be provided. Each node of this structure represents a particular input character sequence, from which branch off several alternative sequences or possible ASCII character strings which are defined on the basis of a fixed key assignment. Where there is no path between nodes, there is no valid character sequence. For the expansion of the vocabulary an extra dictionary is provided. The disambiguation principle is therefore also referred to as dictionary-based disambiguation.

US 7 129 932 Bl deals with keyboards comprising keys with multiple occupancy, for example for PDAs etc. In a database, words and the frequency of occurrence of these words are stored in a language model used. For words that are not yet completely typed (<N), the most probable words are proposed using the existing word or the word from the typed characters using the database, see the example "completed", "complexes" (column 4, lines 25 ff.) - After entering a word ^¬ limit the character set of a just been surrounded word with the words is compared in the lexicon and suggested the most likely word in the lexicon, that is the word that most commonly chosen Language model occurs and at the same time derivable from the entered string.

The US 2002/0183100 Al discloses a method of Letter B ^¬ benauswahl when entering example of SMS messages. In the display, a character which statistically has the highest probability as a secondary character is respectively displayed as a sequence character depending on the preceding input, ie the already entered character sequence. The already entered string is fixed and will not be varied. The following character is calculated using a statistical database. Dictionaries are used for character selection, of which one contains word beginnings and words with up to three characters, the other words with four characters or more. Methods of this type are referred to as prefix-based disambiguation.

Also, a statistical approach to the subsequent letter uses a method described in EP 0 924 594 A2, which makes use of a two-dimensional table on the basis of a preceding letter as well as a three-dimensional trigram table on the basis of two preceding letters.

Also in the disambiguation method according to WO 2004/003953 A1 (eZiText method of Zi Corporation of Canada, Inc.) the first two letters of a word are clearly entered and confirmed by the user. At the beginning of the word, the frequencies of bi- and trigrams are used. The prediction is based on a user dictionary, which preferably contains whole words and their frequency. From EP 1 710 668 A1 a disambiguation method is known in which a memory with words and also n-gram objects as well as their frequencies is used. The n-gram objects can be words or parts of words and include mono-, bi- and trigrams.

The invention has for its object to provide a method for word recognition in character sequences, which is suitable for use in character ambiguities and in which the word recognition is carried out quickly.

This object is achieved in a method with the features of claim 1. Advantageous developments of the method according to the invention are the subject of the dependent claims.

In the method according to the invention for word recognition in sequences of N characters, of which one or more characters can be ambiguous, a memory, a display and a processor device are thus used. The memory contains n-grams (strings of length n) and frequency values associated with the strings, the frequency value of an n-gram being the total number of all n-grams in a speech sample used for word recognition. The display displays selected n-grams and / or recognized words, with the processor device connected to the memory and the display. From a considered sequence of characters, a list L of all n-gram combinations with N characters is created, which can be formed from the N-character sequence, taking into account the ambiguities of the individual characters contained therein. From the list L of the possible n-gram combinations, all n-gram combinations whose word probability is zero are removed, the word probability ^¬ p = π pn from the n-grams contained in the character sequence with n = 1 to NI is determined. From the display, those through the remaining n-gram combinations displayed words of the list L displayed.

A significant advantage of the method according to the invention is that, regardless of the language and key assignment used, it solves assignment problems of character strings and sequences, resulting in meaningful word hypotheses. This is because no words but n-grams are used to perform word recognition in strings. The n-grams, which are word parts or fragments, are used to make probable words. For this purpose, the n-grams with word probability zero are eliminated and those due to the remaining n-grams, i. the most likely word components representing possible words are displayed in list L. By using n-grams instead of words, word recognition is extremely flexible. Suggestions may be made of words that are not included in the lexicon (based on the language sample), e.g. Flowers hedgehog.

For a possible word or word suggestion, there are a number of associated n-gram combinations, as indicated above in the case of the word "baumhaus" for n = 2 to 5 f (V2 to V5). The list of probable Worthypo ^¬ thesen is generated after each keystroke in the input of a word, so that takes place with the tapping step continuous continuous updating of the hypotheses. From this list, if it contains more than one word hypothesis, the user can choose his correct word, if he has already typed the word completely. The way in which the selection is realized is arbitrary. If the word is not completely typed, the user will continue to type new characters.

The recognition method according to the invention can be applied to any languages, legal, technical areas, etc., by integrating the respective vocabulary into the statistics. Also the assignment of letters or others Characters for the keys, ie the output alphabets or key assignments, are freely selectable without requiring any changes or adaptations of the method. Already used language samples can be taken over unchanged, ie a language sample once created can be transferred without any effort to devices with other key arrangements or assignments. The adaptation to any languages with their individual characters such as the accent in French, Hebrew, Cyrillic, Greek etc. signs can be easily used. The counting of a complete language sample takes only a few minutes.

The method according to the invention is able to isolate, among competing characters (letters due to keystrokes or phonemes due to speech input or digital data sets) and the resulting ambiguities, possible words which may be a valid word. With every new typed or spoken letter, the possible recognized single letters are permuted, and each added letter can then be replaced by other ambiguities, which are resolved.

For word strings without spaces, when using the method according to the invention word ambiguities may exist in the word strings, with valid resolutions resulting when all resulting words are either valid whole words or valid words and at the same time have a valid word start or word end. This is illustrated by the following example, which uses the following labels:

(G) valid whole word

(W) valid word beginning, valid word end, valid words in the sense of pA, pE, pW (explained later)

(X) neither (G) nor (W), i. invalid word

Example: the weather is excellent Dissolution attempts: the weather is excellent

(G) (W) (G) (W) -> valid resolution the bet is excellent

(G) (W) (X) (W) -> no valid resolution because swetter is excellent

(G) (X) (W) -> no valid resolution that does not stand out

(G) (X) (X) (G) (G) (G) (G) (W) -> no valid resolution the weather is prominent

(G) (G) (G) (G) (G) (W) -> valid resolution

In the application of the method according to the invention to the text input, a keyboard is usually used which comprises keys which are assigned to a plurality of characters and which is connected to the processor device. In the text input of the N-character sequences, a word ^¬ recognition method is accordingly used, which operates according to the invention.

When the process of the invention for the speech input ver ^¬ applies is, a voice recording device is used, and when the voice input phonemes or phoneme sequences is carried out conversion into N-symbol-sequences, in particular of text characters. On the N-character sequences, a word recognition method is used which operates according to the invention.

The method according to the invention can also be advantageously used when reading, for example, digitally present text documents with character sequences. For this purpose, a reading unit is used for detecting the N-character sequences, and a word recognition method is used in reading the N-character sequences. By means of the invention, words in the stored character sequences can be found and identified very quickly and reliably.

In an advantageous variant of the method according to the invention are proceedings as whole-word n-grams, the words from the speech ^¬ sample determined whose length corresponds to the n-gram length, and wherein the display of the remaining n-gram combinations of the list L are first all words sorted by the full-word Probability pG = GN / NG is indicated, where GN is the whole word n-gram frequency and NG is the total number of all word n-grams of the speech sample. Thus, the whole-word n-grams are mostly short words that act like a lexicon for short words taking into account the frequency of occurrence, and a meaningful sorting of word hypotheses for short words of goodness (such as "the", "marriage", "oath") support. In the case of a language sample with the words "tree house", "hello", "you", "der", the bigram "you", trigram "the" and the five-gram "hello" and as whole word n-grams result

G2 (du) = 1, G3 (der) = 1, G5 (hello) = 1

Unobserved n-grams have the frequency 0, e.g. G3 (IqU) = O. In the speech sample, the total numbers NG (n) of all integer n-grams are calculated. These result from the sum of all frequencies of the whole-word n-grams of the respective length.

In an advantageous embodiment of the method according to the invention, the n-grams, which form the beginning of a word, are determined as word-beginning n-grams. The word initial probability pA = π on / NA is determined, to the word ^¬ initially-n-gram frequency and NA is the total number of all the word ^¬ initially-n-grams of the speech sample. In displaying the remaining possible words, all words are first sorted by the whole-word probability pG = GN / NG, where GN is the whole-word n-gram frequency and NG is the total number of all-word n-grams of the speech sample and the sort after pA ^• pW.

In the case of the mentioned language sample with the words "tree- house "," hello "," you "," der "result in the bigrams" ba "," ha "," you ", de", the trigrams "build", "hal", "the", the 4- Gramme "bäum", "hall" and the 5-Gramme "baumh" as well as "hello". The following frequencies of the beginning of the word n-grams result in the following quantities:

A2 (ba) = 1 A2 (ha) = 1 A2 (du) = 1 A2 (de) = 1

A3 (build) = 1 A3 (hal) = 1 A3 (der) = 1

A4 (tree) = 1 A4 (hall) = 1

A5 (tree) = 1 A5 (hello) = 1

Word-end n-grams are also preferably used, the word-n-grams being the n-grams that form the end of a word. The word-end probability pE = π En / NE is determined, where En is the word end n-gram frequency and NE is the total number of all word end n-grams of the speech sample. In displaying the remaining possible words, all words are first sorted by the whole word probability pG = GN / NG and the word start n gram probability pA = π An / NA, where GN is the whole word n gram frequency, NG is the total number of all word n-grams of the speech sample, the word-start n-gram frequency and NA is the total number of all word-first n-grams of the speech sample and sorting is done according to pA ^• pW ^• pE.

In the case of the mentioned language sample with the words "baumhaus", "hello", "you", "der", the bigrams "us", "lo", "you", "he" result as the word end n-grams. , Trigrams "out", "ho", "the", 4-gramme "house", "allo" and the 5-gramme "mhaus", "hal ^¬ lo". Counted the following frequencies result:

E2 (us) = 1 E2 (lo) = 1 E2 (du) = 1 E2 (er) = 1

E3 (off) = 1 E3 (llo) = 1 E3 (der) = 1

E4 (house) = 1 E4 (allo) = 1

E5 (mhaus) = 1 E5 (hello) = 1 Re-creates the words list L in the novel process for an N-character sequence with each additional character entered advantageous ie there is a kontinuier ^¬ Liche updating the hypotheses. From the list L, if it contains more than one n-gram combination, the user can choose the correct word representation if he has already typed the word completely. How the selection from a proposal offer is realized is arbitrary.

In the previous explanations, values of n = 2, n = 3, n = 4, n = 5 were used for the n-grams. These values are not rigidly fixed, but can be adapted according to the circumstances. When using the method according to the invention, values of n = 2, n = 3 are preferably used for the n-grams, for which the memory requirement is significantly lower than in the case of longer n-grams. Depending on the application, it is also possible to use n-grams with n = 1 (that is, individual letters).

Values of n = 4 and / or n = 5 are preferably also used for the n-grams. The longer the maximum n-grams are chosen (i.e., larger maximum values for n), the better the proposed word hypotheses become. But it will also require more extensive language samples.

The memory may store a list of characters or character sequences and their associated replacement characters, exchange character sequences, or replacement n-grams. In this way, adaptation to the habits of a user, certain characters or words (eg "sparrow" and not "rick"), certain short forms (English: "dont"->"donot", French: "cest") >"c'est"), special characters (eg smiley) to use, to a special vocabulary etc .. The short forms must then also be entered in their short form in the language sample with. It may also be expedient to supplement the n-grams in the memory in order to enable the recognition of new words or special entries. The input of unknown words is not necessary. Sufficient is the updating of corresponding n-grams (word-beginning n-grams, word-n-grams, word-end-n-grams, integer-n-grams). It does not make sense to store all possible frequencies of the n-grams An ('), Wn (-), En (O and Gn (-) (eg for n = 5 there are over 24 million possible n-grams) is also not necessary.Not of these n-grams occur in the language, ie the frequency of most n-grams is 0. On their storage can be omitted.

Word-end n-grams convey the statement that it is a valid complete word, and other features may recognize a word as such in terms of the acquired speech data. In order to isolate the individual words, it is also particularly useful for file reading applications where word boundaries, in particular word ends, are additionally entered to separate the word string into individual complete words, e.g. "Baumhaus" also in "Baume Haus", to share.

The method according to the invention can also be equipped with a word prediction. This may be done so that, based on an input N-character sequence, word recognition is performed for a character sequence having an assumed length of N + (1 to 1) characters, where 1 is the prediction length, ie the number of predicted input steps. After creating the list L, a further list L 'containing all the n-gram combinations of the list L is created therefrom, these n-gram combinations being n-grams or n-gram combinations having the length 1 to 1 are supplemented. From the list L ', all n-gram combinations whose word probability is zero are removed, the n-gram combinations remaining in the list L' are sorted, and the n-gram combinations of the lists L and L 'are displayed , This way can not work for you yet completely input word, a prediction will be made as to which word or words the user has in mind in the input.

In this word prediction method, all n-gram combinations are first sorted according to the whole-word probability pG = GN / NG in the list L ', where GN is the whole-word n-gram frequency and NG is the total number of all the whole-word n Gramme of the language sample is. The sorting then takes place after the start word n-gram and the end word n-gram probability after pA ^• pW ^• pE.

In the above, the determination of the n-grams and their USAGE ^¬ dung have been explained. The following is a representation of the determination of the word probabilities.

The language statistics contained in the various n-gram groups is used to to shut one hand word hypotheses from ^¬ that are no words for the current language is most likely, and to the other to bring the remaining hypotheses in an order according to their probable correctness. In this case, w = wlw2w3. , .wN is a word w of length N, composed of the letters wlw2w3. , .WN. The following occurrence probabilities are determined:

For a word w, the probabilities that w is a valid word in terms of n-grams of length n are calculated

Wn (v) pnW (w) = 11 NW (n) vεVn (w)

From these word-probabilities, which differ according to n-gram length, a whole

Word probability of the word w are calculated for the total of all trained n-gram lengths:

pW (w) = 11 nW (w) n

As soon as even one of the word n-gram frequencies Wn (-) = 0, the word probability pW (w) = 0 is also.

This will be explained further using the example of the word "Baumhaus". For the determination of bigrams and assuming that there are a total of NW (2) = 100 bigrams, we obtain:

p2W (tree) = W2 (ba) / NW (2) ^• W2 (au) / NW (2) ^• W2 (um) / NW (2) ^• W2 (mh) / NW (2) ^• W2 (ha) / NW (2) ^• W2 (au) / NW (2) ^• W2 (us) / NW (2) = 1/100 ^• 2/100 ^• 1/100 ^• 1/100 ^• 2/100 ^• 2/100 ^• 1 / 100

For trigrams follows:

p3W (tree) = W3 (construction) / NW (3) ^• W3 (aum) / NW (3) ^• W3 (umh) / NW (3) ^• W3 (mha) / NW (3) ^• W3 (hau) / NW (3) ^• W3 (off) / NW (3)

From these results ultimately results

pW (tree house) = ... ^• p2W (tree house) ^• p3W (tree house) ^• ...

A great help in assessing whether there is a word w are the word-beginning probabilities. For if there are no words in the language sample with the word-beginning n-grams of the word w, this will most likely not be a valid word of the language. Accordingly, the probability that a word w exists in the sense of the beginning of the word is calculated At (wl ... wn) pA (w) = 11 NA (n) n

As soon as even one of the word-beginning n-gram frequencies An (-) = 0, the word-beginning probability pA (w) = 0 is also present.

An example will explain this in more detail. Suppose that you want to calculate the word beginning probability for n-grams of length 2 to 5 and the word w = tree. Given the frequencies from the list of top-of-the-word bigrams illustrated above, which in this example always has the value 1. Some exemplary total numbers of word start n-grams are NA (2) = 12, NA (3) = 10, NA (4) = 13, NA (5) = 11. This yields

pA (tree house) = A2 (ba) / NA (2) ^• A3 (construction) / NA (3) ^• A4 (tree) / NA (4) ^• A5 (tree) / NA (5) = 1/12 ^• 1 / 10 ^• 1/13 ^• 1/11.

Another great help in assessing whether there is a word w is, as mentioned, the word end probabilities. If there are no words in the language sample that end in the same string of letters as the word w, then this is probably not a word of the language. The word end probabilities can be calculated directly from the word end n-grams:

En (wN-n + l., WN) p E (w) = IT NE (n) n

As soon as even one of the word end n gram frequencies En ( ^• ) = 0, the word end probability pE (w) = 0 is also.

An unknown end of the word does not necessarily indicate a meaningful word hypothesis, but may as well be an indication that a word is not yet fully entered.

This is illustrated by the following example: Assume that the word end probability for n-grams of length 2 to 5 and the word w = tree is to be calculated. Let the Frequently ^¬ opportunities given from the above-illustrated collection of Wortend- bigrams that always have the value 1 in this example, and some exemplary overall numbers of Wortend-n-grams are NE (2) = 22, NE (3) = 20, NE (4) = 23, NE (5) = 21. This yields

pE (tree) = E2 (us) / NE (2) ^• E3 (off) / NE (3) ^• E4 (house) / NE (4) ^• E5 (mhaus) / NE (5) = 1/22 ^• 1 / 20 ^• 1/23 ^• 1/21

The following applies to the whole-word probabilities: If the word w to be evaluated is so short that whole-word n-grams of the same length have been determined from the speech sample, the occurrence probability of w can be simply specified as

pG (w) = GN (wl ... WN) / NG (N)

An example will explain this in more detail. Suppose that the whole-word probability is calculated for the words w = der, w = du and w = lqü. Given the frequencies from the above-mentioned speech sample (always 1 or 0) and some exemplary total numbers of whole-word n-grams, let NG (2) = 33, NG (3) = 30. This yields

pG (der) = G3 (der) / NG (3) = 1/30 pG (du) = G2 (der) / NG (2) = 1/33 pG (lqü) = G3 (der) / NG (3) = 0/30

The concrete procedure will now be described in more detail on the basis of the example "tree house" in order to select from the multitude of possible character combinations for a word (here as already stated above: 61.440) to create a meaningful list of word alternatives.

From the list L of possible words represented by n-gram combinations, all n-gram combinations whose probabilities pW (w) = 0 or pA (w) = 0 are removed. These words are almost certainly not a correct word. For performance reasons, it makes sense to apply this criterion when building the first list L of n-gram combinations and to include only n-gram combinations in the list for which pW ( w) ≠ 0 and pA (w) ≠ 0.

From the few remaining word hypotheses a sorted list is generated, whereby the order of the individual words results from the following three criteria:

(a) First all words with pG (w) ≠ 0 are listed, sorted in descending order according to pG (w). This gives priority to words for which whole-word n-grams exist.

(b) Then all words come with pE (w) ≠ 0, sorted in descending order according to pA (w) ^• pW (w) ^• pE (w). This gives words that represent a complete word priority over those that are (so far) only partially entered.

(c) All remaining words follow, sorted in descending order by pA (w) ^• pW (w). Compared to the previous word group from (b), words are placed behind, which are only partly entered. It makes sense that the entry of 2286428 as a hypothesis, although the sub-word "tree" finds, but may prefer better hypotheses, which after (b) already represent an entire word.

The invention will be explained below with reference to exemplary embodiments and the drawing. In the drawing show:

1 shows a processor device for carrying out the invention method according to the invention when entering text into a keyboard,

2 shows a processor device for carrying out the method according to the invention in voice recording,

3 shows a flow diagram of the method according to the invention for word recognition,

Fig. 4 is a flowchart for supplementing the n-grams in the memory and

Fig. 5 is a flow chart for predicting words in already input partial words.

Fig. 1 shows a processor device including peripherals, with which the inventive method can be used in the text input. A keyboard 10 with keys 11, a display 13 and a memory 15 are connected to a processor device 12. The keys 11 of the keyboard 10 are associated with several characters, so that in the character input not immediately unique identifiable strings, words, etc. arise. The memory 15 contains n-grams and frequency values assigned to these n-grams, which are symbolized by the reference symbol 16. The screen 14 of the display 13 illustrates the remaining words determined using the stored n-grams and their frequency values as possible words, here the three alternative words "the", "marriage", "eid".

FIG. 2 shows a processor device with peripherals for word recognition during voice recording. A Sprachauf ^¬ acquisition device such as a microphone 20, a display 13 and a memory 15 are connected to a processor device 21st Voice input not immediately clearly identi fiable ^¬ phonemes or derivable therefrom grapheme, N-character created Sequences of strings or words, etc. Basically, the approach is analogous to that in text input. The memory 15 contains n-grams and frequency values assigned to these n-grams, which are symbolized by the reference symbol 16. The screen 14 of the display 13 illustrates the remaining words determined using the stored n-grams and their frequency values as possible words, here the three alternative words "the", "marriage", "eid".

FIG. 3 shows that the method for word recognition is essentially characterized by the following method steps. In step 101, the method has the current status of the input, for example a sequence of N key presses available. From this input, the list L of all possible word hypotheses is generated in step 102 on the basis of the existing input ambiguities by permutation of all possible combinations. In step 103, the whole-word true ^¬ probabilities p G, the word probabilities pW that Wortend probabilities pE and the word initial probabilities pA are calculated for each word hypothesis list L. Based on these probabilities, in method step 104 all word hypotheses are removed from the list L whose word probabilities pW or word-start probabilities pA are zero and which therefore do not represent a valid word with great certainty. If a word ^¬ prediction is to be performed, branches off the query 112 to generate the creation of the predictive list L illustrated and explained in greater detail below in FIG. 5 '. If valid whole words exist in the list L, characterized by hypotheses with non-zero integer probabilities, the query 105 branches to the process step 106, which displays all valid whole words, descending sorted by their whole word probabilities, on the screen 14. Method step 107 removes all the hypotheses displayed in method step 106 from the list L and thus avoids the multiple output of one and the same hypothesis. If in the List L valid complete words, characterized by hypotheses with non-zero word-end probabilities, query 108 branches to step 109, which sorts all valid complete words, descending by product of their word-end probabilities, word-start probabilities and word probabilities, attached to the previous edition on the screen 14. Method step 110 removes all the hypotheses displayed in method step 109 from the list L and thus avoids the multiple output of one and the same hypothesis. All remaining hypotheses of the list L are added to the previous output on the screen 14 in step 111, sorted in descending order of the product of their word-start probabilities and word probabilities. If a word prediction is to be performed, query 112 branches to output list L ', added to the previous output on screen 14. If the user accepts one of the displayed words, query 115 branches to step 116 which selects the selected word provides any application and deletes the current character or input sequence, so that in the next input, the method of FIG. 3 in step 101 begins with an empty character sequence, ie a new word.

The practical embodiment of the complement of the pre-preserved in the memory 15 n-grams with new words (unknown or accepted) is described by the following method steps, shown by way ^¬, in Fig. 4. In method step 201, the determination of all n-grams Vn (w) of the word w to be integrated into the memory 15 is carried out as the basis of the supplement. If the word w has a length covered by the whole-word n-grams, the query 202 branches to the process step 203 which updates the frequency of the whole-word n-gram associated with the word w. In method step 204, the word w is integrated into the data base of the word-beginning n-grams in the memory 15 by the frequencies of the word-beginning n-grams of all n-grams Vn (w) representing valid word-beginning n-grams of the word w. In step 205, the word w is integrated into the database of word n-grams in memory 15 by updating the frequencies of the word n-grams of all n-grams Vn (w). In step 206, the word w is integrated into the database of word-end n-grams in the memory 15 by updating the frequencies of the word-end n-grams of all n-grams Vn (w), the valid word-end n-grams of the word represent w.

FIG. 5 describes the steps for generating a word prediction list L ', referenced in FIG. 3, method ^¬ step 114. From a list L in process step 301 a new list L' generated which for each hypothesis from the list L all concatenation this hypothesis with all permutations of the known output alphabet in the lengths of 1 to 1 characters. From the list L ', in the step 302, all hypotheses are removed which have either a word probability of zero or a word start probability of zero or a word end probability of zero. The remaining hypotheses of the list L 'are sorted in step 303 so that all hypotheses that represent a valid whole-word and are decreasing by the whole ^¬ word probability pG, followed by the other Hypo ^¬ theses and these in descending order according to the product of their Word end probabilities, beginning of word probabilities and word probabilities are sorted. The output 304 of the prediction method is thus the sorted list L '.

In the following, the method according to the invention will be explained further using concrete exemplary embodiments in German and Latin using a telephone keypad.

For the first example, an extensive language sample of 688,000 words has been used, containing many compound words as well as books from the trivial literature. The n- Gram occupancy is as follows:

Table 1

On this table it is well recognized that much knowledge is represented by the n-grams with n = 4 and n = 5, because a large part (95% -99.99%) of all four- and five-letter combinations do not occur in the language sample.

The word recognition procedure is now "ready" for the words "actual", "the tree house", "prom", "beer box", "foreign trade turnover", "soccer game" by means of their numbers 478 327 22864287 72466 337844. 2272458772255, 2437527836, 287364263357867289, 387225577435 are recognized. For comparison, the results are given using the T9 technology Tegic.

Table 2 shows the result, with the searched or typed word shown in bold. Behind it stands the respective word hypothesis list,

Die Unterschiede zwischen den beiden Worterkennungsverfahren liegen im wesentlichen nicht bei der Bearbeitung der einfachen, gängigen Wörter. Viele zusammengesetzte Wörter, die sich bei Anwendung des erfindungsgemäßen Verfahrens erschließen, können mit dem herkömmlichen T9-Verfahren nicht gefunden werden. Dabei liegt die Rechenzeit zur Erstellung der o.g. Worthypothesenliste im nichtmessbaren Bereich.Table 2

The differences between the two word recognition methods are essentially not in the processing of simple, common words. Many compound words that can be obtained using the method according to the invention can not be found with the conventional T9 method. The calculation time for creating the above-mentioned word hypothesis list is in the non-measurable range.

The following example refers to Latin on a 6-key keyboard with the following key mapping:

0 1 a b c d e f g h

2 3 j l m n o p q r

4 5 s t u v x y

The letters j, k, w, z do not appear in Latin and are therefore omitted. The example shows how easily the text ^¬ input can be adapted to both new languages, as well as on other keyboards. This results in the following output alphabet:

0 (0) = {a, b, c, d}

0 (1) = {e, f, g, h}

0 (2) = {i, l, m, n}

0 (3) = {o, p, q, r}

0 (4) = {s, t, u}

0 (5) = {v, x, y}

The language statistics was determined from a voice sample, which consisted solely a number of longer Latin Origi ^¬ naltexten (eg Caesar "Commentariorum Libri VII de Bello Gallico", "Commentariorum Libri III de Bello Civili", "Libri Incertorum Auctorum") with a total of 128,000 words , After counting, the following are documented by the possible n-grams:

Table 3

From Table 3 it can be seen again that a lot of information is supplied by the n-grams with n = 4 and n = 5, which does not contain the speech sample itself.

In the following should

Multa legas facito, perlectis negie multa.

Qualis artifex pereo! [Cato Maior: "See that you read a lot and when you read it, much of it is ignored." and "What great artist is going away with me!"] On the basis of her inputs 24240 21104 100243, 313210424 2112111 24240. 340224 0342115 31313! be recognized. The complete sorted list of hypotheses is given for each word, the correct hypothesis in bold:

Table 4

Claims

claims A method of word recognition in sequences of N characters of which one or more characters may be ambiguous using a memory, a display and a processor means, the memory storing n-grams (strings of length n) and the strings contains associated frequency values, wherein the total number of n-grams is used in a used for word recognition speech sample as a frequency value of a n-gram, wherein the display selected n-grams and / or he ^¬ knew displaying words, wherein the processor means to the memory and connected to the display, in which from the considered character sequence a list L of all n-gram combinations with N characters is created, which can be formed from the N-character sequence, taking into account the ambiguities of the individual characters contained in this, in the be removed from the list L of possible n-gram combinations all n-gram combinations whose Word probability is zero, where the word probability p = π pn is determined from the n-grams contained in the character sequence with n = 1 to NI and the display shows the words represented by the remaining n-gram combinations the L list. A method according to claim 1, characterized in that it is applied to a keyboard for text input, the keyboard comprising keys comprising a plurality of characters and the keyboard is connected to the processor device, and in the text input of the N-character sequences a word recognition method is applied. 3. Method according to claim 1, characterized in that it is used for voice input, and wherein a voice recorder is used, and in the voice input of the phoneme or phoneme sequences, a conversion into N-character sequences, in particular of text characters, takes place, and a word recognition method is applied to the N-character sequences. 4. The method according to claim 1, characterized in that it is used for reading character sequences, wherein a reading unit is used, and in reading the N-character sequences, a word recognition method is used. 5. The method according to any one of claims 1 to 4, characterized in that the words are determined from the voice sample whose length corresponds to the n-gram length as the whole-word n-grams, and in the display of the remaining n-gram combinations the list L is first displayed all words sorted by the whole word probability pG = GN / NG, where GN is the whole word n-gram frequency and NG is the total number of all word n-grams of the speech sample. 6. The method according to any one of claims 1 to 4 and 5, characterized in that the word beginning n-grams the n-grams are determined which form the beginning of a word, the word-beginning probability pA = π An / NA is determined, where An is the beginning of the word n-grams frequency and NA is the total number of all word-beginning n-grams of the speech sample, and in displaying the remaining possible words, first all words sorted by the whole-word probability pG = GN / NG are displayed, where GN is the whole-word n-gram frequency and NG is the total number of all whole-word n-grams of the speech sample and the Sort by pA ^• pW, where pW = π pnW is the word probability and pnW = π Wn / NW, Wn is the word n-gram frequency and NW is the total number of all word n-grams. 7. The method according to any one of claims 1 to 4 and 5 or 6, characterized in that the n-grams are determined as the word end n-grams, forming the end of a word, the word end probability pE = π En / NE determined is, where En the Wortend-n-gram frequency and NE is the Ge ^¬ total number of all Wortend-n-grams of the speech sample, and wherein the display of the remaining possible words first all words sorted by the whole-word likelihood pG = GN / NG and the word beginning n-gram probability pA = π An / NA, where GN is the whole-word n-gram frequency, NG is the total number of all whole-word n-grams of the speech sample, to the beginning of word n-gram Frequency and NA is the total number of all word-beginning n-grams of the speech sample, sorting according to pA ^• pW ^• pE. 8. The method according to any one of claims 1 to 4 and one of claims 5 to 7, characterized g e k e n e c i n e t that for an N-character sequence with each further input character, the list L of the n-gram combinations is recreated. 9. The method according to any one of claims 1 to 8, characterized in that for the n-grams values of n = 2, n = 3 are used. 10. The method according to claim 9, characterized marked ^¬ net that values of n = 4 and / or n = 5 are used for the n-grams. 11. The method according to claim 9 or 10, characterized marked ^¬ records that for the n-grams of the value n = 1 ver ^¬ applies. 12. The method according to any one of claims 1 to 11, characterized ge ^¬ indicates that in memory a list of characters or character sequences and their associated from ^¬ exchange characters, exchange character sequences or exchange n-grams is stored. 13. The method according to any one of claims 1 to 12, characterized ge ^¬ indicates that the n-grams are added to the memory to allow the detection of new words or special inputs. 14. The method according to any one of claims 1 to 13, characterized ge ^¬ indicates that word boundaries, in particular word ends, are entered. 15. The method according to any one of claims 1 to 14, characterized ge ^¬ indicates that on the basis of an inputted N-character sequence, a words ^¬ recognition for a character sequence with an assumed length of N + (1 to 1) character is performed, wherein, after the list L has been prepared, another list L 'containing all the n-gram combinations of the list L is prepared from them, these n-gram combinations being n-grams or n-gram combinations of length 1 to 1 are added, from the list L 'all n-gram combinations are removed, whose word probability is zero, the n-gram combinations remaining in list L 'are sorted and the n-gram combinations of lists L and L' are displayed. 16. The method according to claim 15, characterized in that in the list L 'first all n-gram combinations are sorted by the whole word probability pG = GN / NG, where GN is the whole word n-gram frequency and NG the total number of all the word n-grams of the speech sample, and then the sorting is done after the start word n-gram and the end word n-gram probabilities after pA ^• pW ^• pE.