9. A method operating on an ARPA table for a modeled natural language in which each entry of the ARPA table includes an n-gram Az, an associated backoff value Az.p equal to the conditional probability p(z|A) that symbol z follows context A in the modeled natural language, and an associated backoff weight value Az.b for the context A, the method comprising: computing a max-ARPA table from the ARPA table by using an electronic data processing device to perform the operations of: sorting the entries of the ARPA table in descending n-gram order to generate a sorted ARPA table; (1) after the sorting, computing and adding for each entry from top-to-bottom of the sorted ARPA table an associated maximum backoff weight product value Az.m; and (2) after performing operation (1), computing and adding for each entry from top-to-bottom of the sorted ARPA table an associated max-backoff value Az.w where Az.w=max h p(z|hA) is the maximum backoff value for any head h preceding the context A of the n-gram Az; wherein each entry of the max-ARPA table includes an n-gram Az and its associated backoff value Az.p, backoff weight value Az.b, maximum backoff weight product value Az.m, and max-backoff value Az.w; computing by said electronic data processing device a max-backoff value w(A,z) for an n-gram Az that is not in the ARPA table by applying the recursive equation: w ⁡ ( A , z ) = { p ⁡ ( A , z ) if ⁢ ⁢ Az ∉ T m ⁢ ⁢ A ⁢ ⁢ and ⁢ ⁢ A ∉ T m ⁢ ⁢ A p ⁡ ( A , z ) × A · m if ⁢ ⁢ Az ∉ T m ⁢ ⁢ A ⁢ ⁢ and ⁢ ⁢ A ∈ T m ⁢ ⁢ A Az · w if ⁢ ⁢ Az ∈ T m ⁢ ⁢ A where the values A.m and Az.w are obtained from the .m and .w columns of the max-ARPA table T mA , respectively, and p(A,z) is computed from the .p and .b columns of the max-ARPA table, and the computing of the max-backoff value w(A,z) is performed by the electronic data processing device; and sampling a language model of the natural language represented by the ARPA table by generating an upper bound on the language model and then sequentially refining the upper bound during the sampling process using the computed max-backoff value w(A,z) wherein the generating and sequential refining are performed by the electronic data processing device.
9. A method operating on an ARPA table for a modeled natural language in which each entry of the ARPA table includes an n-gram Az, an associated backoff value Az.p equal to the conditional probability p(z|A) that symbol z follows context A in the modeled natural language, and an associated backoff weight value Az.b for the context A, the method comprising: computing a max-ARPA table from the ARPA table by using an electronic data processing device to perform the operations of: sorting the entries of the ARPA table in descending n-gram order to generate a sorted ARPA table; (1) after the sorting, computing and adding for each entry from top-to-bottom of the sorted ARPA table an associated maximum backoff weight product value Az.m; and (2) after performing operation (1), computing and adding for each entry from top-to-bottom of the sorted ARPA table an associated max-backoff value Az.w where Az.w=max h p(z|hA) is the maximum backoff value for any head h preceding the context A of the n-gram Az; wherein each entry of the max-ARPA table includes an n-gram Az and its associated backoff value Az.p, backoff weight value Az.b, maximum backoff weight product value Az.m, and max-backoff value Az.w; computing by said electronic data processing device a max-backoff value w(A,z) for an n-gram Az that is not in the ARPA table by applying the recursive equation: w ⁡ ( A , z ) = { p ⁡ ( A , z ) if ⁢ ⁢ Az ∉ T m ⁢ ⁢ A ⁢ ⁢ and ⁢ ⁢ A ∉ T m ⁢ ⁢ A p ⁡ ( A , z ) × A · m if ⁢ ⁢ Az ∉ T m ⁢ ⁢ A ⁢ ⁢ and ⁢ ⁢ A ∈ T m ⁢ ⁢ A Az · w if ⁢ ⁢ Az ∈ T m ⁢ ⁢ A where the values A.m and Az.w are obtained from the .m and .w columns of the max-ARPA table T mA , respectively, and p(A,z) is computed from the .p and .b columns of the max-ARPA table, and the computing of the max-backoff value w(A,z) is performed by the electronic data processing device; and sampling a language model of the natural language represented by the ARPA table by generating an upper bound on the language model and then sequentially refining the upper bound during the sampling process using the computed max-backoff value w(A,z) wherein the generating and sequential refining are performed by the electronic data processing device. 10. The method of claim 9 wherein performing operation (1) comprises performing the algorithm: For A in T sorted A.m ← 1 For x in V s.t.xA in T sorted : A.m ← max(A.m,xA.b × xA.m) where T sorted is the sorted ARPA table, the algorithm is performed from top-to-bottom of the sorted ARPA table T sorted , and V is the vocabulary of the modeled natural language, and the maximum backoff weight product value for entry A is assigned the value A.m computed by performing the algorithm.