Patent ID: 7870160

Claim:
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).