Patent Document ID: 4831550
Application ID: 06844904
Patent Flag: 1

Claim One:
1. In a speech recognition system, a computer-implemented method of evaluating the likelihood of a word from a vocabulary of words occurring next after a string of known words, based on counts of word sequences occurring in a sample text which is sparse relative to possible word sequences, the method comprising the steps of: (a) characterizing word sequences as m-grams, each m-gram occurring in the sample text representing a key of words followed by a word; (b) storring a discounted probability P for each of at least some m-grams occurring in the sample text; (c) generating a freed probability mass value .beta..sub.L for each key occurring in the sample text, the .beta..sub.L for a key of length L being allocated to those m-grams which (i) include the subject key and (ii) have no respective discounted probabilites stored therefor; (d) generating .gamma..sub.L factors, each .gamma..sub.L factor being valued to normalize the probability distribution of only those m-grams which (i) are formed from a key of length L and (ii) are not included in a greater-included m-gram having a key of known words; (e) storing for each key of length L, a value .alpha..sub.L =.beta.L.gamma.L and (f) evaluating a likelihood of a selected word following a string of known words including the steps of: (i) searching successively shorter keys of the known words until a key is found which, when followed by the at least one selected word, represents an m-gram having a discounted probability P; stored therefor, and retrieving P; (ii) retrieving the stored .alpha..sub.L value for each longer key searched before the stored m-gram is found; and (iii) computing a likelihood value of the selected word following the string of known words based on the retrieved .alpha..sub.L values and the retrieved P value.