Lossless compression of ordered integer lists

• US 20040138883A1
• Filed: 01/13/2003
• Published: 07/15/2004
• Est. Priority Date: 01/13/2003
• Status: Abandoned Application

• 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.
• Application Number:
  US10/341,307
• Publication Number:
  US 20040138883A1
• Time in Patent Office: Days
• US Class Current: 704/236
• CPC Class Codes: G10L 15/285 Memory allocation or algorithm optimisation to reduce hardware requirements
• CPC Class Codes: H03M 7/30 Compression speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N; Expansion; Suppression of unnecessary data, e.g. redundancy reduction

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 an array A[.] of ordered positive integer values stored in a memory:

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<sup>k−

1</sup>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₀[.] 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_kis 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+1[.] equal to the array I_kj^j, and

repeating, beginning at the determining step, for j=j+1 to generate the arrays A^k₀⁰[.], A_k1¹[.], A_k2²[.], . . . , A<sub>kJ−

1</sub><sup>j−

1</sup>[.], and the array A^J[.], where J is the value of j upon completion.