System and method for lossless data compression and decompression

A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for compressing input data comprising a plurality of data blocks, the method comprising the steps of:

• detecting if the input data comprises a run-length sequence of data blocks;
• outputting an encoded run-length sequence, if a run-length sequence of data blocks is detected;
• maintaining a dictionary comprising a plurality of code words, wherein each code word in the dictionary is associated with a unique data block string;
• building a data block string from at least one data block in the input data that is not part of a run-length sequence;
• searching for a code word in the dictionary having a unique data block string associated therewith that matches the built data block string;
• and
• outputting the code word representing the built data block string.

A method for decompressing an encoded data stream comprising a plurality of code words, the method comprising the steps of:

• maintaining a dictionary comprising a plurality of code words utilized to generate the encoded data stream, wherein the code words in the dictionary comprise control code words and code words that are each associated with a unique data block string;
• decoding and outputting a run-length sequence of data blocks associated with an input code word of the encoded data stream, if the input code word is a control code word in the dictionary that indicates an encoded run-length sequence;
• outputting a unique data block string in the dictionary that is associated with an input code word of the encoded data stream, if the input code word is found in the dictionary;
• and
• if the input code word is not found in the dictionary, building a new data block string comprising (1) the unique data block string associated with a previous control word found in the dictionary and (2) the first data block of the unique data block string, adding the new string to the dictionary and outputting the new string.

A system for compressing input data comprising a plurality of data blocks, the system comprising:

• a dictionary comprising a plurality of code words, wherein the code words comprise control code words and code words that are each mapped to a unique data block string;
• a run-length encoder for encoding a sequence of similar data blocks in the input data using at least one code word in the dictionary;
• and
• a dictionary encoder for encoding a data block string comprising at least one data block in the input data using a code word in the dictionary, wherein output of the run-length encoder and dictionary encoder are combined to form an encoded data stream.