17. A method comprising: receiving, at one or more data processing apparatuses, an input string having a plurality of tokens, the input string being divided into one or more n-grams, each n-gram having a length k, wherein k is an integer between 1 and a maximum length N, inclusive, the length identifying a number of tokens in each n-gram; and using a language model to identify a probability for a particular n-gram in the input string, the language model including: a collection of n-grams from a corpus, each n-gram having a corresponding relative frequency in the corpus and an order n corresponding to a number of tokens in the n-gram, each n-gram corresponding to a backoff n-gram having an order of n−1, and a collection of backoff factors α k , one backoff factor for each value of k from 2 to N, inclusive, wherein: when the particular n-gram is present in the language model, the probability for the particular n-gram being the relative frequency of the particular n-gram in the language model, and when the particular n-gram is not found in the language model, the probability for the particular n-gram being identified as a backoff score S k for the particular n-gram, wherein the particular n-gram that is not found in the language model has a particular longest backoff n-gram that is present in the language model and that has a particular relative frequency f and a particular length m, and wherein the backoff score S k is a function of the collection of backoff factors, the particular length m and the particular relative frequency of the particular longest backoff n-gram in the language model.
18. The method of claim 17 , where identifying a probability includes looking up a calculated backoff score for the particular n-gram.