Data compression method and apparatus with optimized transitions between compressed and uncompressed modes

• US 5,686,912 A
• Filed: 05/08/1995
• Issued: 11/11/1997
• Est. Priority Date: 05/08/1995
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Company (HP Inc.)
• Inventors: Heineck, Matthew P., Jung, Brian R., Clark, Airell R. II
• Primary Examiner(s): Gaffin, Jeffrey A.
• Assistant Examiner(s): HUYNH, TRANG N
• Application Number:
  US08/437,263
• Time in Patent Office: 918 Days
• Field of Search: 341/50, 341/60, 341/106, 341/51, 341/87
• US Class Current: 341/51
• CPC Class Codes: G06T 9/005 Statistical coding, e.g. Huffman, run length coding
• CPC Class Codes: H03M 7/3088 employing the use of a dictionary, e.g. LZ78
• CPC Class Codes: H03M 7/48 alternating with other codes during the code conversion process, e.g. run-length coding being performed only as long as sufficientlylong runs of digits of the same kind are present

Abstract

A method of compressing a stream of raw data including the steps of providing a memory device having compression active state and a compression inactive state, inputting a raw data segment into the memory device, generating a compressed data segment based on the raw data segment, creating output data based on the compressed data segment when the memory device is in the compression active state, otherwise based on the raw data segment when in the memory device is the compression inactive state, calculating a compression coefficient, and setting the state of the memory device based on the compression coefficient, such that compressed data is output only when compression has recently proven effective, and raw data is output when compression has recently proven ineffective. The method may also include decompression of the output data.

Claims

1. A method of compressing a stream of raw data:

providing a memory device having compression active state and a compression inactive state;

inputting a raw data segment into the memory device;

generating a compressed data segment based on the raw data segment;

creating output data based on the compressed data segment when the memory device is in the compression active state, otherwise based on the raw data segment when the memory device is in the compression inactive state;

calculating a compression coefficient as a function of a prior compression coefficient, and the sizes of the raw and compressed data segments; and

setting the state of the memory device based on the compression coefficient, such that compressed data is output only when compression has recently proven effective, and raw data is output when compression has recently proven ineffective.

2. The method of claim 1 wherein generating a compressed data segment includes searching for the raw data segment in a dictionary having a plurality of data segments each having an associated code, and if the raw data segment is found, defining the compressed data segment as the code associated with the raw data segment.

3. The method of claim 1 wherein calculating the compression coefficient comprises determining a ratio of the sizes of the raw data segment and the compressed data segment.

4. The method of claim 1 wherein calculating the compression coefficient comprises generating a moving average.

5. The method of claim 1 including storing the compression coefficient, such that it is retained for calculation of the next compression coefficient.

6. The method of claim 1 wherein calculating the compression coefficient comprises:

recalling a prior compression coefficient;

calculating a current compression ratio equal to the size of the raw data segment divided by the size of the compressed data segment; and

setting the compression coefficient equal to a weighted average of the prior compression coefficient and the current compression ratio.

7. The method of claim 6 wherein calculating the compression coefficient includes setting the prior compression coefficient equal to the compression coefficient.

8. The method of claim 1 wherein setting the state of the memory device comprises, if the compression coefficient is above a predetermined activation threshold, setting the memory device to the compression active state.

9. The method of claim 1 wherein setting the state of the memory device comprises, if the compression coefficient is below a predetermined deactivation threshold, setting the memory device to the compression inactive state.

10. The method of claim 1 including the steps of storing the output data in a storage device, then decompressing the output data from the storage device by determining for each segment in the output data whether the segment is a raw data segment or a compressed data segment, and if the segment is a compressed data segment, converting the segment to raw data, such that the resulting data stream is identical to the original data stream.

11. A method of storing and retrieving a stream of data comprising the steps:

inputting a sequence of raw data segments;

for a first raw data segment, calculating a compression coefficient;

after calculating a compression coefficient, determining based on the compression coefficient whether to operate in a raw mode in which subsequent data segments are not compressed, or in a compression mode in which subsequent data segments are compressed;

for each subsequent data segment,

compressing the segment if in the compression mode;

storing the segment;

generating a new compression coefficient as a function of a prior compression coefficient;

recalling the segment by determining whether or not the segment was compressed, and decompressing the segment if the segment was compressed; and

outputting the sequence of segments.

12. The method of claim 11 wherein compressing the segment includes searching for an identical segment entry in a dictionary having a plurality of data segment entries each having an associated code, and if the identical segment entry is found, defining the segment as the code associated with the segment entry.

13. The method of claim 11 wherein calculating the compression coefficient comprises generating a moving average.