EFFICIENT DATA COMPRESSION & DECOMPRESSION OF NUMERIC SEQUENCES

• US 20090289819A1
• Filed: 05/21/2009
• Published: 11/26/2009
• Est. Priority Date: 05/21/2008
• Status: Active Grant

• Current Assignee: Quest Software, Inc.
• Original Assignee: Ocarina Networks, Inc. (Dell Technologies Inc.)
• Inventors: Mahoney, Matthew
• Granted Patent: US 7,864,083 B2
• Time in Patent Office: Days
• US Class Current: 341/51
• CPC Class Codes: H03M 7/24 Conversion to or from floating-point codes
• CPC Class Codes: H03M 7/4006 Conversion to or from arithmetic code

Abstract

Embodiments described herein relate to compression and decompression of data consisting of a one dimensional time series of floating point numbers. A compressor may comprise a lossless stage and in some embodiments a lossy stage in addition to the lossless stage. The lossy stage quantizes the data by discarding some of the least significant bits as specified by the user. The lossless stage uses a context mixing algorithm with two bit-wise predictive models whose predictions are combined and fed to an arithmetic coder. One model is a direct context model using the most significant bits of prior numeric samples as context. The other model is the output of an adaptive filter, in which the approximate predicted numeric value is used as context to model the actual value. A corresponding decompressor uses the same lossless model with the arithmetic coder replaced by an arithmetic decoder.

Claims

1. A computer system configured to compress and decompress data, the system comprising a processor and a memory, and configured by instructions in the memory when executed by the processor to:

receive a one dimensional time series of floating point numbers as an input;

predict with a plurality of submodels what the next bit of the input sequence will be, before it is compressed, to form a plurality of predictions, where one or more of the submodels uses an adaptive filter to compute all or part of its context;

combine said plurality of predictions with a mixer to produce a combined prediction;

refine the combined prediction using zero or more secondary symbol estimator (SSE) stages;

code the bit dependent on an output of a final of the SSE stages;

update said submodels to reduce their respective prediction errors;

update said mixer to favor a more accurate of the submodels;

update said SSE stages to reduce their respective output prediction errors; and

if the coded bit is the last bit of a floating point number, update the weights of all adaptive filters to reduce their respective prediction errors.

2. The computer system of claim 1, wherein the system is further configured to quantize the received input by rounding each floating point value to the nearest multiple of a fixed input value prior to coding.

3. A computer system configured to compress and decompress data, the system comprising a processor and a memory, and configured by instructions in the memory when executed by the processor to:

receive a one dimensional time series of floating point numbers as an input;

predict with a plurality of submodels what the next bit of the input sequence will be, before it is compressed, to form a plurality of predictions, where one or more of the submodels uses an adaptive filter to compute all or part of its context;

combine said plurality of predictions with a mixer to produce a combined prediction;

code the bit dependent upon the combined prediction;

update said submodels to reduce their respective prediction errors;

update said mixer to favor a more accurate of the submodels; and

if the coded bit is the last bit of a floating point number, update the weights of all adaptive filters to reduce their respective prediction errors.

4. The computer system of claim 3, wherein the system is further configured to quantize the received input by rounding each floating point value to the nearest multiple of a fixed input value prior to coding.

5. The computer system of claim 3, wherein the computer system is further configured to refine the combined prediction using one or more secondary symbol estimator (SSE) stages.

6. The computer system of claim 5, wherein the computer system is further configured to update said SSE stages to reduce their respective output prediction errors.

7. A computer system configured to compress and decompress data, the system comprising a processor and a memory, and configured by instructions in the memory when executed by the processor to:

receive compressed data as an input;

predict with a plurality of submodels what the next bit of the output sequence will be, before it is decompressed, to form a plurality of predictions, where one or more of the submodels uses an adaptive filter to compute all or part of its context;

combine said plurality of predictions with a mixer to produce a combined prediction;

refine the combined prediction using one or more secondary symbol estimator (SSE) stages;

decode the bit dependent on an output of a final of the SSE stages or the mixer;

update said submodels to reduce their respective prediction errors;

update said mixer to favor a more accurate of the submodels;

update said SSE stages to reduce their respective output prediction errors; and

if the decoded bit is the last bit of a floating point number, update the weights of all adaptive filters to reduce their respective prediction errors.