Patent ID: 7171358

Claim:
A computer implemented method stored on a computer readable medium with executable instructions of perform compression of a language model of a continuous speech recognition system, wherein the language model is an N-gram including a plurality of arrays A[.], each array A[.] including ordered positive integer values stored in a memory, the integers representing a vocabulary of the language mode, the compressing for each array A[.] comprising: defining an inverse array I[.] of the ordered array A[.] as I[j] =inverse( A [.])=first( j+k, A[ .]): k= arg min l ( j+l∈A[.] ), l≧ 0, where a function first(j, A[.]) returns a location of a first instance of an jth entry in the array A[.], and a function min l (j+l∈A[.]) returns a smallest value l such that j+l is an entry in the array A[.]; defining a kth split inverse I k [.]=splitinverse k (A[.]) of the array A[.] as I k [.]=inverse(A[.]>>k), where A[.]>>k is an array obtained by right-shifting each entry of the array A[.] by k bits; defining a kth split of the array A[.] as A k [.]=A[.]&Mask[k], where Mask ⁡ [ k ] = ∑ j = 0 k - 1 ⁢ 2 k · A ⁡ [ · ] represents an array obtained by masking all but the last k bits of each of entry of the array A[.]; defining a null array A 0 [.] having the same length as the array A[.], defining a function Size(A[.]) for returning a total number of bits required to store the array A[.] in a compressed form as Size(A[.])=length(A[.])×width(A[.]), where width(A[.])=ceil(log 2 (max(A[.]))) is the number of bits required to store a largest integer value in the array A[.]; defining a function MinSize for determining a minimum number of bits required to store the array A[.] in terms of the split arrays and split inverse arrays by MinSize(A[.])=min k {Size(I k [.])+Size(A k [.])+C k }, where C k is overhead required to store pointers to the split arrays, length of the split arrays, and an indication that the array A[.] is stored in terms of the split arrays and the split inverse arrays; defining a function OptSize(.) for determining a size of the array A[.] in terms of the split arrays and the split inverse arrays as OptSize(A[.])=min k (OptSize(I k [.])+Size(A k [.])+C k }, wherein {circumflex over (k)} is an optimal value of k; determining an optimal size for the array A j [.] using the function OptSize; storing the array A j [.] if k j =width(A j [.]), and otherwise separating the array A j [.] into the split inverse arrays I k j j and the split arrays A k j j , and storing the split arrays A k j j , and setting the array A j+l [.] equal to the array I k j j , and repeating, beginning at the determining step, for j=j+1 to generate the arrays A k 0 0 [.], A k1 1 [.], A k 2 2 [.], . . . , A kJ−l J−l [.], and the array A J [.], where J is the value of j upon completion.