Patent ID: 8417730

Claim:
A computer-implemented method for encoding a data stream of bytes, said method comprising the steps of: (a) receiving said data stream; (b) providing a fixed-length lookahead window for said data stream, the lookahead window having a start position; (c) determining a first digest of said window; (d) determining if the first digest of said window has a corresponding entry in a primary data structure; (e) storing in the primary data structure, a position in the data stream corresponding to the start position of said window if the primary data structure does not include an entry corresponding to the first digest of said window; (f) if the primary data structure includes an entry corresponding to the first digest of said window, modifying the entry to include a secondary data structure of second digests each occurring with the same first digest and associating each second digest included in the secondary data structure with a respective position in the data stream where the combination of the first and second digests was found; (g) if the primary data structure already contains a secondary data structure of second digests, determining if the second digest of the current lookahead window is present in the secondary data structure contained in the primary data structure; (h) if the second digest of the current lookahead window is not present in the secondary data structure contained in the primary data structure, modifying the secondary data structure contained in the primary data structure to associate the second digest of the current lookahead window with the start position of the lookahead window in the data stream; (i) if the second digest of the current lookahead window is present in the secondary data structure contained in the primary data structure, determining a length of a matching portion by reading first data from a first location in the data stream at which the combination of first and second digests was found and comparing the first data from the first location with second data starting at the start position of the current lookahead window, and storing the length of the matching portion in the secondary data structure and assigning a codeword to the sequence of bytes in the matching portion; (j) if the combination of digests for the current lookahead 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 combination of digests of the current lookahead window is shortened in accordance with the length of the matching portion; (k) continuing processing at a location in the data stream of a next non-matching byte until the data stream has been fully processed; (l) after completing steps (a)-(j), further processing blocks of unmatched data by a dictionary coder adapted to find small repetitions of data; wherein the method is performed by a computer programmed to perform steps (a)-(l).