18. A computer program product, encoded on a computer readable medium, operable to cause data processing apparatus to perform operations comprising: receiving a collection of n-grams, each n-gram having a corresponding first probability of occurring; generating a trie using a first vector and a second vector, the trie assigning one or more values identifying each n-gram in the collection of n-grams, where the first vector is a left word vector identifying each distinct left word for a given right context in the collection, the second vector is a diversity count vector identifying a count of distinct left words for each right context in the collection; and using the trie to identify the probabilities of occurring for corresponding n-grams in a received string that includes one or more n-grams.
20. The computer program product of claim 18 , where identifying an integer value for an n-gram comprises: using a first key, the first key corresponding to a last word of the n-gram, and the second vector to identify a range in the first vector to search for a next-to-last word in the n-gram; and identifying a second key corresponding to the last word and next-to-last word of the n-gram using the identified range and the first vector.