Variable bit-length reiterative lossless compression system and method

• US 8,878,705 B1
• Filed: 03/28/2014
• Issued: 11/04/2014
• Est. Priority Date: 03/28/2014
• Status: Active Grant

• Current Assignee: Npression Technologies, LLC
• Original Assignee: Npression Technologies, LLC
• Inventors: Dunayer, Sidney
• Primary Examiner(s): JEANGLAUDE, JEAN BRUNER
• Application Number:
  US14/229,515
• Time in Patent Office: 221 Days
• Field of Search: 341/50, 341/51, 341/87
• US Class Current: 341/87
• CPC Class Codes: H03M 7/3068 Precoding preceding compression, e.g. Burrows-Wheeler transformation
• CPC Class Codes: H03M 7/40 Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code
• CPC Class Codes: H03M 7/6035 Handling of unkown probabilities
• CPC Class Codes: H03M 7/6088 according to the data type

Abstract

A computer-implemented method of performing lossless compression of a digital data set uses an iterative compression process in which the number of symbols N and bit length per symbol n may vary on successive iterations. The process includes analyzing at least a part of the data set to establish a partition thereof into N symbols of symbol length n, and to determine whether the N symbols can be further compressed, and, if so, a model to be used in encoding the N symbols.

Claims

1. A computer-implemented method of performing lossless compression of a digital data set, the method comprising:

performing a compression process including;

analyzing at least a part of the data set to establish a partition thereof into N symbols of symbol length n, and to determine whether the N symbols can be further compressed, and, if so, a model to be used in encoding the N symbols;

if it has been determined that the N symbols can be further compressed, encoding the N symbols using the model and storing the encoded data in an iteration store;

if it has been determined that the N symbols cannot be compressed, storing the N symbols in the iteration store;

determining whether any part of the digital data set remains to be processed, and if so, then repeating the compression process for an additional part of the digital data set; and

if not, then substituting the contents of the iteration store for the data set and repeating the compression process on the data set thus updated until a specified end condition has been met, and then providing an output from the iteration store.

11. A computer-implemented method of performing lossless compression of a digital data set according to claim 1 and thereafter decompressing the resulting compressed digital data set, the method further comprising:

performing a decompression process including;

for each partition in the compressed digital data set,

examining a partition header for the partition to determine if its data is compressed or uncompressed and if the partition is the last partition;

if the partition'"'"'s data is determined to be compressed,

retrieving from the partition header a value of little-n for the partition and a value identifying the model;

if the partition is determined to be the last partition, retrieving from the header a number of bits in the last decompressed symbol from the partition that must be discarded;

decoding the partition data using the model identified for the partition and the value of little-n for the partition and storing the decoded partition data in a decompression store;

if the partition'"'"'s data is determined to be uncompressed,

retrieving from the partition header a value indicating the number of bits of uncompressed data in the partition;

using the value indicating the number of bits of uncompressed data in the partition, copying the partition'"'"'s data to the decompression store;

if an endpoint condition has not been reached, then substituting the contents of the decompression store for the compressed digital data set and repeating the decompression process;

otherwise, providing an output from the decompression store.

2. A computer-implemented method of analyzing a digital data set to establish a partition thereof into N symbols of symbol length n, and to determine whether the N symbols can be further compressed, and, if so, a model to be used in encoding the N symbols, the method comprising:

in a computer process, storing for later retrieval a set of values for a natural number n that is greater than 0;

performing an analysis loop process including;

retrieving a distinct one of the stored values for n,

for each symbol of length n in the data set, performing an entropy calculation including;

receiving such symbol from the digital data set at an input;

for each model in a set of models,

computing an entropy value and adding the computed entropy value to an entropy accumulator for such model; and

using the value in the entropy accumulator, computing, for such symbol, a compression score and an updated value of partition size N for such model;

using the values in the entropy accumulators for each of the models, identifying the model having the best compression score; and

storing the identified model, its corresponding value of N, and its compression score;

determining whether a processing end point has been reached, and if not, then

repeating the analysis loop process for an additional value of n;

otherwise

evaluating the stored compression scores for each value of n to identify the value of n having the best compression score; and

returning the identified value of n, and its corresponding model and its corresponding value of N.

3. A method according to claim 2, wherein the processing end point is completion of processing for all values of n.

4. A method according to claim 2, wherein the processing end point is when the compression score for at least one value of n and using at least one model is deemed sufficient.

5. A method according to claim 2, wherein performing the analysis loop process includes performing a first analysis loop process for a first distinct value for n in parallel with performing a second analysis process for a second distinct value for n.

6. A method according to claim 2, wherein storing the set of values for n includes storing the values in a FIFO and retrieving a distinct one of the stored values for n includes retrieving it from the FIFO.

7. A method according to claim 5, wherein the processing end point is completion of processing for all values of n.

8. A method according to claim 5, wherein the processing end point is when the compression score for at least one value of n and using at least one model is deemed sufficient.

9. A computer-implemented method of performing lossless compression of a digital data set, the method comprising:

performing an analysis process including;

analyzing at least a part of the data set to establish a partition thereof into N symbols of symbol length n, and to determine whether the N symbols can be further compressed, and, if so, a model to be used in encoding the N symbols;

storing, in an analysis FIFO, a set of values of n, N, and the model for the just-analyzed portion of the digital data set;

determining whether any part of the digital data set remains to be processed, and if so, then repeating the analysis process for an additional part of the digital data set;

for each set of values in the analysis FIFIO, performing an encoding process including;

retrieving, from the analysis FIFO, such set of values of n, N, and the model;

if it has been determined that the N symbols can be further compressed, encoding the N symbols using the retrieved model and retrieved value of n and storing the compressed data in an iteration store;

if it has been determined that the N symbols cannot be compressed, storing the N symbols in the iteration store;

substituting the contents of the iteration store for the data set and repeating the analysis process and the compression process on the data set thus updated until a specified end condition has been met, and then providing an output from the iteration store.

10. A method according to claim 9, wherein the analyzing process and the compression process operate in parallel at least some of the time.

12. A non-volatile storage medium in which is stored a compressed digital data set, the compressed data set comprising:

a sentinel indicating whether or not the results of decompressing said compressed digital data set results in an endpoint condition;

a set of partitions, wherein at least one of the partitions includes compressed digital data, and each partition includes;

a partition header, the header including;

a type field indicating whether the partition contains compressed or uncompressed data;

a sentinel indicating whether the partition is the last partition in the compressed digital data set;

if the type field indicates that the partition contains uncompressed data, a length field indicating the number of bits of uncompressed data in the partition;

if the type field indicates that the partition contains compressed data, a symbol field containing a value of little-n in the partition, a model field containing a value identifying the model used in the partition, and if the last partition, a discard field indicating a number of bits in the last decompressed symbol from the partition that must be discarded; and

data of the partition, such data having content and format characterized by the partition header.