Method and apparatus for data compression using fingerprinting

A method of processing an input stream of data into a compressed code stream, the input stream of data including a plurality characters, the method comprising:

• dividing the input stream of data into a plurality of blocks, each block containing a particular number of characters of the plurality of characters;
• computing a plurality of fingerprints, each fingerprint of the plurality of fingerprints corresponding to a different one block of the plurality of blocks;
• comparing the plurality of blocks to the plurality of fingerprints to determine whether a match occurs between a particular fingerprint and any portion of a particular block;
• encoding, for each match, a identifier within the input stream of data, the identifier including at least a starting position within the input stream of data of the matching portion of the particular block and a length of the matching portion;
• and
• compressing the encoded input stream of data into the compressed code stream;
• wherein the compressing the encoded input stream of data operation is performed according to a Lempel-Ziv coding technique.

A data compression apparatus comprising:

• a receiver for receiving and dividing a input stream of data into a plurality of blocks, each block containing a particular number of characters of a plurality of characters from the input stream of data;
• an encoder for (i) computing a plurality of fingerprints, each fingerprint of the plurality of fingerprints corresponding to a different one block of the plurality of blocks, (ii) comparing the plurality of blocks to the plurality of fingerprints, the comparing the plurality of blocks to the plurality of fingerprints in the encoder further comprising:
• (a) computing an interim fingerprint for the block at each character of the particular number of characters contained in the block;
• and (b) comparing the interim fingerprint to the particular fingerprint, (iii) determining whether a match occurs between a particular fingerprint and any portion of a particular block, and (iv) encoding, for each match, an identifier of the match within the input stream of data;
• and
• a compressor for compressing the encoded input stream of data into a compressed code stream.

A data storage system for storing a digital data stream in compressed data form, the data storage system comprising:

• means for dividing the digital data stream into a plurality of data blocks, each block of the plurality of data blocks having a plurality of characters;
• means for storing the plurality of data blocks together with the plurality of fingerprints in a data structure;
• means for computing a plurality of fingerprints, each fingerprint of the plurality of fingerprints corresponding to a different one data block of the plurality of data blocks;
• means for traversing the plurality of blocks and means for computing a interim fingerprint for each block at each character of the plurality of characters for the block, the means for traversing the plurality of blocks operation serially traverses the blocks as a function of the plurality of characters of each block, and means for comparing the interim fingerprint to a particular fingerprint of the plurality of fingerprints, and if a match occurs between the particular fingerprint and the interim fingerprint, means for encoding the match within the digital data stream;
• and
• means for compressing the encoded digital data stream into the compressed data form.

An apparatus for processing a compressed digital signal, the compressed digital signal being produced by (i) dividing an input stream of digital data into a plurality of data blocks and each block of the plurality of blocks contains a plurality of characters, (ii) computing a plurality of fingerprints, each fingerprint of the plurality of fingerprints corresponding to a different one data block of the plurality of data blocks, (iii) comparing the input stream of digital data to the plurality of fingerprints, the comparing the input stream of digital data to the plurality of fingerprints further comprising:

• (a) computing an interim fingerprint for the block at each character of the plurality characters of the block;
• and (b) comparing the interim fingerprint to the particular fingerprint, and if a match occurs between a particular fingerprint and the input stream of digital data, encoding the match within the input stream of digital data, compressing the encoded input stream of digital data into the compressed digital signal, and applying the compressed digital signal to a communications channel, the apparatus comprising:
• a receiver for receiving the compressed digital signal from the communications channel;
• and
• a decompressor for decompressing the received compressed digital signal, and recovering the input stream of digital data from the decompressed digital signal.

A machine-readable medium having stored thereon a plurality of instructions, the plurality of instructions including instructions that, when executed by a machine, cause the machine to perform of a method of processing an input stream of data into a compressed code stream, the input stream of data including a plurality characters, dividing the input stream of data into a plurality of blocks, each block containing a particular number of characters of the plurality of characters, computing a plurality of fingerprints, each fingerprint of the plurality of fingerprints corresponding to a different one block of the plurality of blocks, comparing the plurality of blocks to the plurality of fingerprints such that the comparing the plurality of blocks to the plurality of fingerprints is performed as a function the characters in the block, and an interim fingerprint for the block is computed at each character of the plurality of characters and compared to the particular fingerprint, determining whether a match occurs between a particular fingerprint and any portion of a particular block, encoding, for each match, an identifier of the match within the input stream of data, the identifier including at least a starting position within the input stream of data of the matching portion of the particular block and a length of the matching portion, and compressing the encoded input stream of data into the compressed code stream.