Adaptive compression

• US 8,427,346 B2
• Filed: 04/13/2010
• Issued: 04/23/2013
• Est. Priority Date: 04/13/2010
• Status: Expired due to Fees

• Current Assignee: Empire Technology Development LLC (Allied Inventors Management, LLC)
• Original Assignee: Empire Technology Development LLC (Allied Inventors Management, LLC)
• Inventors: Potkonjak, Miodrag
• Primary Examiner(s): LAUTURE, JOSEPH J
• Application Number:
  US12/996,972
• Publication Number:
  US 20120265737A1
• Time in Patent Office: 1,106 Days
• Field of Search: 341/50, 341/51, 341/64, 375/240, 382/251, 709/247, 710/68, 702/183
• US Class Current: 341/50
• 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

Technology for adaptive compression is described (“the technology”). The technology may identify two or more partitions of a data stream; optionally pre-process data in each partition; create one or more evaluation functions to evaluate a suitability for compression of the data in each partition using a set of potential compression methods; process the created one or more evaluation functions; choose a subset of the set of potential compression methods for each segment at least partly by analyzing the evaluation functions; select a compression method for each segment based on a compression ratio of compressing the sequence of used compression methods and a compression rate of the data; compress the data in each partition using the selected compression method for the partition; compress a subsequence that indicates which compression method is used for each segment.

Claims

1. A method performed by a computing system for compressing data, comprising:

identifying two or more partitions of a data stream;

optionally pre-processing data in each partition;

creating one or more evaluation functions to evaluate a suitability for compression of the data in each partition using a set of potential compression methods;

processing the created one or more evaluation functions;

choosing a subset of the set of potential compression methods for each partition at least partly by analyzing the evaluation functions;

selecting using a dynamic programming technique a compression method for each partition based at least on a compression rate of the data in the partition;

compressing the data in each partition using the selected compression method for the partition, thereby creating a sequence of compression methods wherein each member of the sequence indicates a compression method used to compress a corresponding partition; and

compressing a subsequence of the sequence of compression methods.

2. The method of claim 1 wherein the identifying includes setting all partitions to have an equal length.

3. The method of claim 2 wherein the length is set using a binary search for a highest compression ratio.

4. The method of claim 1 wherein the optionally pre-processing includes using delta modeling, transformation in other domain using linear transformation, or application of any other compression method.

5. The method of claim 1 further comprising characterizing selected subsets based on their suitability for high rate compression is performed using probability distribution functions (PDFs) of single or multiple consecutive characters.

6. The method of claim 5 wherein a function for evaluating suitability for compression of data in each partition is at least one of an entropy, a mutual entropy, a PDF monotonicity, or a moving average of autocorrelation.

7. The method of claim 1 wherein processing the created one or more evaluation functions includes employing parametric or nonparametric statistical techniques such as smoothing or regression.

8. The method of claim 1 wherein processing the created one or more evaluation functions is conducted using re-sampling or boosting statistical techniques, or other machine learning technique.

9. The method of claim 1 wherein choosing compression methods includes identifying compression techniques that had a highest score according to processed evaluation functions.

10. The method of claim 1 wherein selecting the compression method for each partition is performed using dynamic programming to minimize the overall compression rate.

11. The method of claim 1 wherein compression of each partition is conducted using a compression method such as run-length encoding, dictionary coders, entropy encoding, arithmetic coding, discrete cosine transform, wavelet compression, linear predictive coding or a compression method that employs statistically processed prediction models.

12. The method of claim 1 wherein compression of each partition is conducted using a lossless compression method such as run-length encoding, dictionary coders, entropy encoding, arithmetic coding, or universal codes.

13. The method of claim 1 wherein the data is compressed on-line with at most a specified latency, and prediction models are used to predict a most likely most beneficial or average most beneficial compression technique for each partition.

14. The method of claim 13 wherein dynamic programming is used with latency L to calculate a most beneficial selection of a compression method for a specified number of partitions that are completed at most L time units earlier.

15. The method from claim 1 wherein information from a global positioning system, some other location discovery system, a clock, a speedometer, or some other type of sensor is used to adaptively select a compression technique for a selected partition.

16. A computer-readable storage medium storing computer-executable instructions that, when executed, perform a method for compressing multiple streams of data, comprising:

identifying two or more partitions of each of two or more signals;

optionally pre-processing one or more signals to make it more suitable for high rate of compression;

creating one or more evaluation functions to evaluate a suitability for compression of the data in each partition using a set of potential compression methods wherein some of the functions are defined over two or more signals;

processing the created evaluation functions;

choosing a subset of the set of potential compression methods for each partition of each signal at least partly by analyzing the evaluation functions;

selecting a compression method for each partition of each signal based at least on a compression rate of the data in the partition;

compressing the data in each partition of all signals using the selected compression method, thereby creating a sequence of compression methods wherein each member of the sequence indicates a compression method used to compress a corresponding partition; and

compressing a subsequence of the sequence of compression methods.

17. The computer-readable storage medium of claim 16 wherein the partitions have constant lengths for different signals.

18. The computer-readable storage medium of claim 16 wherein the length of partitions have a small least common multiplier.

19. The computer-readable storage medium of claim 16 further comprising pre-processing wherein different signals are mutually time shifted relative to each other.

20. The computer-readable storage medium of claim 16 wherein selecting a compression method for each partition of each signal includes employing joint PDFs information.

21. The computer-readable storage medium of claim 16 wherein the compression is performed using linear combinations of the considered signals.

22. The computer-readable storage medium of claim 16 wherein the partitions have different lengths for different signals.

23. A system for compressing data, comprising:

a component configured to identify two or more partitions of a data stream;

a component configured to optionally pre-process data in each partition;

a component configured to create one or more evaluation functions to evaluate a suitability for compression of the data in each partition using a set of potential compression methods;

a component configured to process the created one or more evaluation functions;

a component configured to choose a subset of the set of potential compression methods for each partition at least partly by analyzing the evaluation functions;

a component configured to select a compression method for each partition based on a compression ratio of compressing a sequence of compression methods used to compress the data in a corresponding partition and a compression rate of the data in the corresponding partition;

a component configured to compress the data in each partition using the selected compression method for the partition; and

a component configured to compress a subsequence of the sequence of compression methods.