Patent ID: 8725509

Claim:
A computer-implemented method, comprising: obtaining, at a computing system including one or more processors, a language model including (i) a plurality of n-grams from a corpus, (ii) a relative frequency for each of the plurality of n-grams, and (iii) a back-off weight for each of the plurality of n-grams; generating, at the computing system, a modified language model, the modified language model being smaller than the language model, the modified language model being a trie representation of the language model, wherein generating the modified language model includes: sorting, at the computing system, the plurality of n-grams according to a sorting technique to obtain a sorted plurality of n-grams, wherein the sorting technique is one of: (a) a direct full n-gram sort that sorts the plurality of n-grams in a direct traversal order from a left-most word to a right-most word to obtain the sorted plurality of n-grams, (b) a reversed full n-gram sort that sorts the plurality of n-grams in a reverse traversal order from a right-most word to a left-most word to obtain the sorted plurality of n-grams, (c) a reversed context n-gram sort that sorts a context in a reverse traversal order from a right-most word to a left-most word and then sorts a future word within the same context to obtain the sorted plurality of n-grams, and (d) a combined reversed full n-gram sort that (i) sorts the plurality of n-grams from shortest n-gram to longest n-gram to obtain the sorted plurality of n-grams and (ii) identifies and inserts missing n-grams into the modified language model, encoding, at the computing system, the sorted plurality of n-grams using an encoding technique to obtain an array comprising a plurality of vectors, respectively, wherein a specific vector includes one or more keys values corresponding to one or more of the plurality of n-grams, and generating, at the computing system, the trie representation of the language model using the array to obtain the modified language model; and outputting, at the computing system, a probability for an n-gram in response to a request using the modified language model, wherein the probability is based on relative frequencies and back-off weights for any of the plurality of n-grams that are associated with a key value for the n-gram.