Compression of language model structures and word identifiers for automated speech recognition systems

• US 20040138884A1
• Filed: 01/13/2003
• Published: 07/15/2004
• Est. Priority Date: 01/13/2003
• Status: Active Grant

• Current Assignee: Mitsubishi Electric Research Laboratories, Inc. (Mitsubishi Electric Corporation)
• Original Assignee: Mitsubishi Electric Research Laboratories, Inc. (Mitsubishi Electric Corporation)
• Inventors: Ramakrishnan, Bhiksha, Whittaker, Edward W. D.
• Granted Patent: US 7,171,358 B2
• Time in Patent Office: Days
• US Class Current: 704/236
• CPC Class Codes: G10L 15/197 Probabilistic grammars, e.g. word n-grams

Abstract

A method compresses one or more ordered arrays of integer values. The integer values can represent a vocabulary of a language mode, in the form of an N-gram, of an automated speech recognition system. For each ordered array to be compressed, and an inverse array I[.] is defined. One or more spilt inverse arrays are also defined for each ordered array. The minimum and optimum number of bits required to store the array A[.] in terms of the split arrays and split inverse arrays are determined. Then, the original array is stored in such a way that the total amount of memory used is minimized.

Claims

1. A computer implemented method for compressing 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

$\left[k\right]=\stackrel{k-1}{\underset{j=0}{\sum <br><br>}}<br><br>2^k·<br><br>A<br><br>[·<br><br>]$

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₀[.] 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₂(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_kj^j and the split arrays A_kj^j, and storing the split arrays A_kj^j, and setting the array A^j+l[.] equal to the array I_kj^j, and

repeating, beginning at the determining step, for j=j+1 to generate the arrays A_k0⁰[.], A_kl^l[.], A_k2²[.], . . . , A_kJ-l^J-l[.], and the array A^J[.], where J is the value of j upon completion.