Content estimation data compression

• US 9,792,308 B2
• Filed: 05/02/2013
• Issued: 10/17/2017
• Est. Priority Date: 12/11/1998
• Status: Expired due to Fees

• Current Assignee: Realtime Data LLC (Realtime Data Compression Systems, Inc.)
• Original Assignee: Realtime Data LLC (Realtime Data Compression Systems, Inc.)
• Inventors: Fallon, James J., Pickel, Paul F., McErlain, Stephen J., Buck, John
• Primary Examiner(s): Mobin, Hasanul
• Application Number:
  US13/875,884
• Publication Number:
  US 20130297575A1
• Time in Patent Office: 1,629 Days
• Field of Search: None
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: H03M 7/3088 employing the use of a dictionary, e.g. LZ78
• CPC Class Codes: H03M 7/4043 Adaptive prefix coding
• CPC Class Codes: H03M 7/4062 Coding table adaptation

Abstract

The present disclosure is directed to systems and methods for providing fast and efficient data compression using a combination of content dependent, content estimation, and content independent data compression. In one aspect of the disclosure a method for compressing data comprises the steps of: analyzing a data block of an input data stream to identify a data type of the data block, the input data stream comprising a plurality of disparate data types; performing content dependent data compression on the data block, if the data type of the data block is identified; performing content estimation data compression if the content is estimable; and performing content independent data compression on the data block, if the data type of the data block is not identified or estimable. In another aspect of the present invention LZDR compression is applied to simultaneously perform one method of compression while computing statistics useful in estimating the optimal form of compression to be applied.

Claims

1. A system for content estimation data compression, the system comprising:

a memory configured to store a data block; and

one or more processors including a run length encoder and a dictionary compression encoder configured to execute on the one or more processors,

wherein the one or more processors are configured to;

determine whether the data block is parsable, and in response to determining that the data block is parsable, compress the data block using content dependent data compression;

in response to determining that the data block is not parsable, determine whether the data block content is estimable by applying run length encoding and dictionary encoding, performing a compression error check on results of the applying, and compiling one or more compression statistics on the data block, wherein the applying of run length encoding occurs before the applying of dictionary encoding;

in response to determining that the data block is not parsable and that the data block content is not estimable based on the results of the applying, compress the data block using content independent data compression; and

in response to determining that the data block is not parsable and that the data block content is estimable based on the results of the applying, estimate the content of the data block, aggregate the data block with a second data block of estimated data content to produce an accumulated data block for generating a higher compression ratio relative to individually compressed blocks, select one or more encoders to be applied to the accumulated data block based on the estimated content of the data block, wherein the one or more selected encoders to be applied to the data block utilize the one or more compression statistics, and compress the accumulated data block with the one or more selected encoders to a smaller size than the first and second data blocks in uncompressed form.

2. The system of claim 1, wherein the one or more applied encoders output encoded data when a compression ratio of compressed data exceeds a compression threshold.

3. The system of claim 1, wherein the one or more applied encoders output unencoded data when a compression ratio of compressed data is less than a compression threshold.

4. The system of claim 1, wherein the applying run length encoding includes utilizing an LZDR compression technique.

5. The system of claim 1, wherein the applying dictionary encoding includes utilizing a Huffman encoding technique.

6. The system of claim 1, wherein the performing the compression error check includes determining whether a failure has occurred in creating a compression table during the application of the dictionary encoding.

7. The system of claim 1, wherein the one or more processors are further configured to compress the accumulated data block in response to determining that a predefined minimum quantity of data has been aggregated.