Block compression algorithm

Abstract

A method for compressing a data stream based on a 3 byte sequence is used. Each three byte sequence is assigned a code word including a location and a length of the data associated with the code word. When a 6 byte sequence is located, a binary tree of 6 byte sequences sharing the same first three bytes is built, associating each 6 byte sequence with a position in the stream where the 6 byte sequence is found. When the length of a code word is changed, a byte sequence is emitted that identifies the code word to be changed and updating the length of the code word, so that when a match is found, a byte sequence is emitted that identifies the code word associated with the matched data. The method finds particular application in data streams that are sent to printers, and which contain large blocks of identical data.

1. A computer-implemented method for encoding a data stream, said method comprising the steps of:
 (a) receiving said data stream; 
 (b) providing a 6 byte window for said data stream; 
 (c) examining the first three bytes of said window; 
 (d) determining if the first three bytes of said window has a corresponding entry in a lookup table; 
 (e) storing a position in the data stream of the first three bytes of said window in the lookup table if the lookup table does not include an entry corresponding to the first three bytes of said window; 
 (f) if the lookup table includes an entry corresponding to the first three bytes of said window, modifying the entry to include a binary tree of 6 byte sequences each beginning with the same three bytes and associating each 6 byte sequence included in the binary tree with a respective position in the data stream where the 6 byte sequence was found; 
 (g) if the lookup table already contains a binary tree of 6 byte sequences, determining if a 6 byte sequence currently in the window is present in the binary tree contained in the lookup table; 
 (h) if the 6 byte sequence currently in the window is not present in the binary tree contained in the lookup table, modifying the binary tree contained in the lookup table to associate the 6 byte sequence currently in the window with a current position in the data stream; 
 (i) if the 6 byte sequence currently in the window is present in the binary tree contained in the lookup table, determining a length of a matching portion by reading first data from a first location in the data stream at which the 6 byte sequence currently in the window was found and comparing the first data with second data following the 6 bytes currently in the window, and storing the length of the matching portion in the tree and assigning a codeword to the sequence of bytes in the matching portion; 
 (j) if the 6 byte sequence currently in the window already has an associated length and the length of the matching portion is greater than zero and less than the associated length, the length of a codeword assigned to the 6 byte sequence currently in the window is shortened in accordance with the length of the matching portion; 
 (h) continuing processing at a location in the data stream of a next non-matching byte until the data stream has been fully processed, 
 wherein the method is performed by a computer programmed to perform steps (a)-(h). 
 
     
     
       2. A method according to  claim 1 , wherein said data stream is a print stream. 
     
     
       3. A computer-implemented method for compressing a data stream based on three byte sequences, the method comprising:
 assigning each three byte sequence a codeword with a location and a length of a data associated with the codeword; and 
 when a three byte sequence is located in the data stream,
 building a binary tree of 6 byte sequences each beginning with the same three bytes, 
 associating each 6 byte sequence with a position in the data stream where the 6 byte sequence is found, so that when the length of a codeword word is changed, a byte sequence is emitted that identifies the code word being changed and the length of the codeword is updated, so that when a match is found, a byte sequence is emitted that identifies a codeword associated with the matched data, 
 
 wherein the method is performed by a computer programmed to perform the method. 
 
     
     
       4. A method according to  claim 1 , further comprising a step of further processing blocks of unmatched data by a dictionary coder adapted to find small repetitions of data.