Methods and apparatus to compress datasets using proxies

• US 7,587,401 B2
• Filed: 03/10/2005
• Issued: 09/08/2009
• Est. Priority Date: 03/10/2005
• Status: Expired due to Fees

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Yeo, Boon-Lock, Zhang, Zhenhua
• Primary Examiner(s): Vo; Tim T.
• Assistant Examiner(s): Meng; Jau-Shya
• Application Number:
  US10/547,140
• Publication Number:
  US 20060259448A1
• Time in Patent Office: 1,643 Days
• Field of Search: None
• US Class Current: 1/1
• 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
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

Methods and apparatus to compress a dataset include: obtaining a first block of a dataset to be compressed; computing a proxy for at least a portion of the first block; comparing the proxy to a set of proxies representative of previously stored blocks; and, if the proxy for the at least the portion of the first block matches a proxy in the set of proxies, storing a data structure that maps the at least the portion of the first block to at least a portion of a previously stored block associated with the matching proxy without storing the at least the portion of the first block.

Claims

1. A method to reduce electronic storage space consumption comprising:

executing machine readable instructions within a computing device to;

obtain a first block of a first computer readable file to be from a buffer in the computing device;

compute a full proxy of the entire first block, a first half proxy for a first half of the first block, a second half proxy for a second half of the block, and a first quarter proxy, a second quarter proxy, a third quarter proxy, and a fourth quarter proxy for a first quarter of the first block, a second quarter of the first block, a third quarter of the first block, and a fourth quarter of the first block, respectively;

compare the full proxy to a set of proxies representative of previously stored blocks, at least some of the previously stored blocks being from a second computer readable file, the second computer readable file being different from the first computer readable file;

when the full proxy of the first block matches a first proxy in the set of proxies, to store a first data structure in the computing device that maps the entire first block to at least a portion of a first previously stored block associated with the first matching proxy without storing the first block;

when the full proxy of the first block does not match any proxy in the set of proxies, to compare at least one of the first half proxy, the second half proxy, the first quarter proxy, the second quarter proxy, the third quarter proxy or the fourth quarter proxy to the set of proxies representative of previously stored blocks;

when one of the first half proxy, the second half proxy, the first quarter proxy, the second quarter proxy, the third quarter proxy or the fourth quarter proxy matches a second proxy in the set of proxies, to store a second data structure in the computing device that maps the one of the first half proxy, the second half proxy, the first quarter proxy, the second quarter proxy, the third quarter proxy or the fourth quarter proxy to at least a portion of a second previously stored block associated with the second matching proxy without storing the portion of the first block corresponding to the one of the first half proxy, the second half proxy, the first quarter proxy, the second quarter proxy, the third quarter proxy or the fourth quarter proxy; and

to obtain a second block of the first computer readable file, the first and second blocks being sequential, wherein when the full proxy for the first block matches a proxy in the set of proxies, the second block does not overlap with the first block, and when none of the full proxy, the first half proxy, the second half proxy, the first quarter proxy, the second quarter proxy, the third quarter proxy or the fourth quarter proxy of the first block matches a proxy in the set of proxies, the second block at least partially overlaps with the first block;

wherein at least one of the first previously stored block and the second previously stored block is from the second computer readable file, and a first amount of storage space of the computing device used to store the first data structure, the second data structure, the first computer readable file and the second computer readable file by executing the machine readable instructions is less than a second amount of storage space of the computing device required to store the first and second computer readable files without executing the machine readable instructions.

2. The method as defined in claim 1, further comprising when none of the full proxy, the first half proxy and the first quarter proxy for the first block matches any proxy in the set of proxies, storing at least the first quarter of the first block.

3. The method as defined in claim 2, wherein storing the at least the first quarter of the first block comprises compressing the at least the first quarter of the first block prior to storing the at least the first quarter of the first block.

4. The method as defined in claim 1, further comprising:

computing a second proxy for at least a portion of the second block;

comparing the second proxy for the at least the portion of the second block to the set of proxies representative of previously stored blocks;

when the second proxy for the at least the portion of the second block matches a proxy in the set of proxies, storing a data structure that maps the at least the portion of the second block to at least a portion of a previously stored block associated with the matching proxy without storing the at least the portion of the second block; and

when the second proxy for the at least the portion of the second block does not match any proxy in the set of proxies, storing the at least the portion of the second block.

5. The method as defined in claim 1, further comprising, when none of the full proxy, the first half proxy, the second half proxy, the first quarter proxy, the second quarter proxy, the third quarter proxy and the fourth quarter proxy for the first block matches any proxy in the set of proxies, storing the full proxy, the first half proxy, the second half proxy, the first quarter proxy, the second quarter proxy, the third quarter proxy and the fourth quarter proxy for the first block in the set of proxies.

6. The method as defined in claim 1, wherein computing the full proxy for the first block comprises computing a hash function of the entire first block.

7. The method as defined in claim 1, wherein storing the data structure that maps the entire first block to the at least the portion of the previously stored block associated with the matching proxy comprises storing at least one of a file name associated with the previously stored block, a file offset correlating a start of the at least the portion of the first block to a start of the at least the portion of the previously stored block, or a block length of the first block.

8. The method as defined in claim 2, wherein storing the at least the first quarter of the first block comprises storing at least one of a block index and a block length of the at least the first quarter of the first block.

9. The method as defined in claim 1, further comprising when none of the full proxy, the first half proxy, the first quarter proxy and the second quarter proxy matches any proxy in the set of proxies, storing at least the first half of the first block.

10. The method as defined in claim 1, wherein when none of the full proxy, the first half proxy, the first quarter proxy, the second quarter proxy, the second half proxy and the third quarter proxy matches any proxy in the set of proxies, storing at least the first half and the third quarter of the first block.

11. An apparatus to compress a dataset comprising:

a block database storing a plurality of blocks of a plurality of stored datasets;

a block map mapping a block of a previously stored dataset to a block stored in the block database;

a compressor to compare an entire first block of the dataset to be compressed to at least a subset of the blocks of the datasets stored in the block database, to compare a first half of the first block of the dataset to be compressed to at least the subset of the blocks of the datasets stored in the block database when the entire first block does not match a block in the at least the subset of blocks, to compare a first quarter of the first block of the dataset to be compressed to at least the subset of the blocks of the datasets stored in the block database when neither the entire first block nor the first half of the first block matches a block in the at least the subset of blocks, to add at least the first quarter of the first block of the dataset to be compressed to the block database when none of the entire first block, the first half of the first block and the first quarter of the first block matches at least one of the stored blocks in the subset, and to map at least the first quarter of the first block of the dataset to be compressed to at least a portion of a block stored in the block database without adding the at least the first quarter of the first block to the block database when the at least the first quarter of the first block matches at least a portion of at least one of the stored blocks in the subset;

the compressor further comprising;

a proxy calculator to calculate a full proxy for the entire first block of the dataset to be compressed, a first half proxy for a first half of the first block, a second half proxy for a second half of the block, and a first quarter proxy, a second quarter proxy, a third quarter proxy, and a fourth quarter proxy for a first quarter of the first block, a second quarter of the first block, a third quarter of the first block, and a fourth quarter of the first block, respectively;

a proxy comparator to compare the full proxy for the entire first block of the dataset to be compressed to proxies for at least portions of the blocks in the at least a subset of the blocks stored in the block database; and

a mapper to map the entire first block of the dataset to be compressed to at least a portion of a block stored in the block database when the full proxy comparator identifies a match;

the proxy calculator to obtain a second block of the dataset, the first and second blocks being sequential, wherein when the full proxy for the first block matches a proxy in the set of proxies, the second block does not overlap with the first block, and when none of the full proxy, the first half proxy, the second half proxy, the first quarter proxy, the second quarter proxy, the third quarter proxy or the fourth quarter proxy of the first block matches a proxy in the set of proxies, the second block at least partially overlaps with the first block;

at least one of the compressor, the proxy calculator, the proxy comparator and the mapper comprising machine readable instructions stored on a tangible machine readable medium.

12. The apparatus as defined in claim 11, wherein the proxy comparator compares the first half proxy to a set of proxies representative of portions of blocks stored in the block database;

and when the first half proxy matches a proxy in the set of proxies, the mapper maps the first half of the first block to a portion of a previously stored block associated with the matching proxy.