Content independent data compression method and system

• US 6,309,424 B1
• Filed: 11/03/2000
• Issued: 10/30/2001
• Est. Priority Date: 12/11/1998
• Status: Expired due to Term

• Current Assignee: Realtime Data LLC (Realtime Data Compression Systems, Inc.)
• Original Assignee: Realtime Data LLC (Realtime Data Compression Systems, Inc.)
• Inventors: Fallon, James J.
• Primary Examiner(s): WAMSLEY, PATRICK G
• Application Number:
  US09/705,446
• Time in Patent Office: 361 Days
• Field of Search: 341/51, 341/79, 341/60, 348/458, 386/96, 707/200, 375/240, 704/220, 710/68, 711/112, 382/253
• US Class Current: 341/51
• CPC Class Codes: G06T 9/00 Image coding bandwidth or redundancy reduction for static pictures H04N1/41; coding or decoding of static colour picture signals H04N1/64; methods or arrangements for coding, decoding, compressing or decompressing digital video signals H04N19/00
• 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

Systems and methods for providing content independent lossless data compression and decompression. A data compression system includes a plurality of encoders that are configured to simultaneously or sequentially compress data independent of the data content. The results of the various encoders are compared to determine if compression is achieved and to determine which encoder yields the highest lossless compression ratio. The encoded data with the highest lossless compression ratio is then selected for subsequent data processing, storage, or transmittal. A compression identification descriptor may be appended to the encoded data with the highest compression ratio to enable subsequent decompression and data interpretation. Furthermore, a timer may be added to measure the time elapsed during the encoding process against an a priori-specified time limit. When the time limit expires, only the data output from those encoders that have completed the encoding process are compared. The encoded data with the highest compression ratio is selected for data processing, storage, or transmittal. The imposed time limit ensures that the real-time or pseudo real-time nature of the data encoding is preserved. Buffering the output from each encoder allows additional encoders to be sequentially applied to the output of the previous encoder, yielding a more optimal lossless data compression ratio.

Claims

1. A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for providing content independent data compression, said method steps comprising:

receiving as input a block of data from a stream of data;

encoding said input data block with a plurality of encoders to provide a plurality of encoded data blocks;

determining a compression ratio obtained for each of said encoders

comparing each of said determined compression ratios with an a priori user specified compression threshold;

selecting for output said input data block and appending a null compression descriptor to said input data block, if all of said encoder compression ratios fall below said a priori specified compression threshold; and

selecting for output said encoded data block having the highest compression ratio and appending a corresponding compression type descriptor to said selected encoded data block, if at least one of said compression ratios exceed said a priori specified compression threshold.

2. The program storage device of claim 1, further comprising instructions for performing the steps of:

initializing a timer with a user-specified time interval upon commencing the encoding of said input data block; and

terminating said encoding step upon the earlier of one of the expiration of said timer and the completion of said encoding of said input data block by all of said plurality of encoders, wherein the step of determining the compression ratios is only performed for the encoders that have completed encoding of said input data block before expiration of said timer.

3. A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for providing content independent data compression, said method steps comprising:

receiving as input a block of data from a stream of data;

compressing said input data block with a plurality of encoders and appending a corresponding encoder desirability factor to said encoded data block output from each of said encoders;

determining a compression ratio obtained by each of said encoders;

comparing each of said determined compression ratios with an a priori user specified compression threshold;

selecting for output said input data block and appending a null compression descriptor to said input data block, if all of said encoder compression ratios fall below said a priori specified compression threshold;

calculating a figure of merit for each encoded data block having a compression ratio associated therewith that meets said a priori user specified compression threshold, said figure of merit comprising a weighted average of said a priori user specified compression threshold and said corresponding encoder desirability factor; and

selecting for output said encoded data block having the highest figure of merit and appending a corresponding compression type descriptor to said selected encoded data block.

4. The program storage device of claim 3, further comprising instructions for performing the steps of:

initializing a timer with a user-specified time interval upon commencing the encoding of said input data block; and

terminating said encoding step upon the earlier of one of the expiration of said timer and the completion of said encoding of said input data block by all of said plurality of encoders;

wherein the step of determining the compression ratios is performed only for the encoders that have completed encoding of said input data block before expiration of said timer.

5. A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for providing content independent data compression, said method steps comprising:

receiving as input a block of data from a stream of data;

compressing said input data block with a plurality of encoders, wherein each encoder comprises a plurality of serially-cascaded encoders;

appending a corresponding encoder desirability factor to each of said encoded data blocks output from each of said encoders;

determining a data compression ratio obtained by each of said encoders;

comparing each of said determined compression ratios with an a priori user specified compression threshold;

selecting for output said input data block and appending a null compression descriptor to said input data block, if all of said compression ratios fall below said a priori specified compression threshold;

calculating a figure of merit for each encoded data block which exceeds said a priori user specified compression threshold, said figure of merit comprising a weighted average of said a priori user specified threshold and said corresponding encoder desirability factor; and

selecting for output said encoded data block having the highest figure of merit and appending a corresponding compression type descriptor to said selected encoded data block.

6. The program storage device of claim 5, wherein said corresponding compression type descriptor indicates one of a single encoding type descriptor, a plurality of sequential encoding types descriptor, and a plurality of random encoding types descriptor.

7. The program storage device of claim 5, further comprising instructions for performing the steps of:

initializing a timer with a user-specified time interval upon commencing encoding of said input data block;

buffering the encoded data block output from each serially-cascaded encoder;

terminating said encoding by a serially-cascaded encoder upon the earlier of one of the expiration of said timer and the completion of said encoding of said input data block by the serially-cascaded encoder, wherein the step of determining the compression ratios for each encoder is performed by determining the compression ratio for the corresponding last serially-cascaded encoder that has completed encoding of said input data block before expiration of said timer.

8. A method for compressing data, comprising the steps of:

receiving an input data stream comprising a plurality of disparate data types;

compressing the input data stream using each of a plurality of different encoders;

generating an encoded data stream by selectively combining compressed data blocks output from each of the encoders based on compression ratios obtained by the encoders.

9. The method of claim 8, wherein the step of compressing the input data stream comprises compressing each data block in the input data stream using each of the encoders, and wherein the step of generating the encoded data stream comprises:

for each data block in the input stream,

determining a compression ratio obtained from each of the encoders;

selecting for output the input data block and appending a null compression descriptor to input the data block, if no compression ratio exceeds a predetermined threshold; and

selecting for output the encoded data block having the greatest compression ratio associated therewith that meets the predetermined threshold and appending a compression type descriptor to the selected encoded data block.

10. The method of claim 9, further comprising the step of applying a predetermined timing constraint to the compression process to provide real-time data compression of the input data stream.

12. The method of claim 8, wherein the step of generating the encoded data stream comprises tagging each compressed data block with a compression type descriptor.

13. The method of claim 8, wherein the step of generating the encoded data stream comprises combining uncompressed data blocks from the input data stream with the compressed data blocks and tagging each uncompressed data block with a null compression descriptor.

11. The method of 10, wherein the step of applying a predetermined time constraint comprises the steps of:

initializing a timer with a user-specified time interval upon commencing compression of an input data block; and

terminating said encoding step upon the earlier of one of the expiration of said timer and the completion of said encoding of said input data block by all of said plurality of encoders;

wherein the step of determining the compression ratios is only performed for the encoders that have completed encoding of said input data block before expiration of said timer.