Method and Apparatus for Data Compression

• US 20110113016A1
• Filed: 11/06/2009
• Published: 05/12/2011
• Est. Priority Date: 11/06/2009
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Smith, Mark A., Pieper, Jan H., Gruhl, Daniel F.
• Granted Patent: US 8,380,688 B2
• Time in Patent Office: Days
• US Class Current: 707/661
• 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

A method, system, and article for compressing an input stream of uncompressed data. The input stream is divided into one or more data segments. A hash is applied to a first data segment, and an offset and length are associated with this first segment. This hash, together with the offset and length data for the first segment, is stored in a hash table. Thereafter, a subsequent segment within the input stream is evaluated and compared with all other hash entries in the hash table, and a reference is written to a prior hash for an identified duplicate segment. The reference includes a new offset location for the subsequent segment. Similarly, a new hash is applied to an identified non-duplicate segment, with the new hash and its corresponding offset stored in the hash table. A compressed output stream of data is created from the hash table retained on storage media.

Claims

1. A data compression method comprising:

processing a first input stream of uncompressed data for a first file, including dividing the input stream into a plurality of segments;

for each segment, applying a hash to a first segment and associating an offset and length with the hashed segment for identifying the location and size of the hash;

storing a hash and corresponding offset and length for the first segment into a hash table;

comparing a subsequent segment within the input stream with all other hashes in the hash table;

based upon the comparison, writing a reference to a prior hash for an identified duplicate segment with a new offset location for the subsequent segment and absent applying the hash to the identified duplicate, and applying a new hash to an identified non-duplicate segment and storing the new hash and corresponding new offset into the hash table; and

a compressed output stream of data from the hash table retained on storage media.

2. The method of claim 1, further comprising identifying a length of each segment and storing the identified length with the offset for the segment.

3. The method of claim 1, wherein the step of dividing the input stream into a plurality of segments employs a segmenting algorithm selected from the group consisting of:

fixed block size, absent content knowledge, and content aware.

4. The method of claim 1, further comprising storing all hash information from the hash table into an archive.

5. The method of claim 4, further comprising writing the archive to a storage device.

6. The method of claim 1, further comprising re-generating hashes from the compressed output stream, including re-processing data stored in a hash table archive to provide original hash information.

7. The method of claim 1, further comprising a second input stream of data for a second file, and employing the hash table from first file for creating a unique hash and associated offset for all non-duplicate segments.

8. The method of claim 1, further comprising a user setting the segment size.

9. A system for data compression, comprising:

a processor in communication with storage media;

a first input stream of data for a first file local to the storage media configured to be processed for compression;

a compression manager in communication with the first input stream, the manager to divide the first input stream into a plurality of segments;

the compression manager to apply a hash to each segment, and an offset and length identifier associated with the hashed segment to identify the location and size of the hash;

the compression manager to store the hash and corresponding offset and length for each unique segment in a hash table;

a director in communication with the compression manager, the director to compare of a subsequent segment within the first file with all other hashes in the hash table;

based upon the comparison, the director to reference a prior hash written with a new offset for an identified duplicate segment absent application of the hash to the identified duplicate, and to apply a new hash to an identified non-duplicate segment and to store the new hash and corresponding new offset and length data into the hash table; and

a compressed output stream of data retained on storage media.

10. The system of claim 9, further comprising the compression manager to identify a length of each segment and to store the identified length with the offset for the segment.

11. The system of claim 9, wherein the division of the input stream into a plurality of segments by the manager employs a segmenting algorithm selected from the group consisting of:

fixed block size, absent content knowledge, and content aware.

12. The system of claim 9, further comprising the director to store all hash information from the hash table into an archive.

13. The system of claim 12, further comprising the compression manager to write the archive to a storage device.

14. The system of claim 9, further comprising a de-compression manager in communication with the compression manager, the de-compression manager to re-generate a hash from the compressed output stream and to re-process data stored in a hash table archive to provide original hash information.

15. The system of claim 9, further comprising a second input stream of data for a second file, and the compression manager to employ the hash table from first file to create a unique hash and associated offset for all non-duplicate segments.

16. The system of claim 9, further comprising a user to set the segment size.

17. An article for compressing data, comprising:

a first input stream of uncompressed data for a first file;

a computer readable carrier including computer program instructions configured to compress data of the first file, the instructions comprising;

instructions to divide the input stream into a plurality of segments;

for each segment, instructions to apply a hash to the segment and to associate an offset with the hashed segment to identify the location of the hash;

instructions to store a hash and corresponding offset and a length for each unique segment into a hash table;

instructions to compare a subsequent segment within the same file with all other hashes in the hash table; and

based upon the comparison, instructions to write a reference to a prior hash with a new offset location for an identified duplicate segment absent applying the hash to the identified duplicate, and instructions to apply a new hash to an identified non-duplicate segment and to store the new hash and corresponding new offset and length into the hash table; and

a compressed output stream of data retained on storage media.

18. The article of claim 17, further comprising instructions to identify a length of each segment and to store the identified length with the offset for the segment.

19. The article of claim 17, wherein instructions to divide the input stream into a plurality of segments employs a segmenting algorithm selected from the group consisting of:

fixed block size, absent content knowledge, and content aware.

20. The article of claim 17, further comprising instructions to store all hash information from the hash table into an archive.

21. The article of claim 20, further comprising instructions to write the archive to a storage device.

22. The article of claim 17, further comprising instructions to re-generate hashes from the compressed output stream, including instructions to re-process data stored in a hash table archive to provide original hash information.

23. The article of claim 17, further comprising a second input stream of data for a second file, and instructions to employ the hash table from first file to create a unique hash and associated offset for all non-duplicate segments.