High speed lossless data compression method and apparatus using side-by-side sliding window dictionary and byte-matching adaptive dictionary
AssigneeCeram Incorporated
InventorsGary L. Harrington, Thomas M. Mnich, William D. Miller
Life of this patent
Estimating the term…
Abstract
A data compression and decompression method and apparatus utilizing a sliding window dictionary in combination with an adaptive dictionary. Incoming data moves through a buffer and is compared against both the sliding window dictionary and the adaptive dictionary, and matched data is replaced with a pointer to the dictionary entry. All incoming data is entered into the sliding window dictionary, but only data which satisfies certain criteria is entered into the adaptive dictionary.
Claims27
A method for compressing a byte stream of input data, comprising:
- establishing a multiple-byte buffer and sequentially transferring bytes from said byte stream into said buffer;
- establishing a multiple-byte first comparison window and sequentially transferring bytes from said byte stream into said first comparison window;
- establishing a multiple-byte second comparison window to receive some but not all of the bytes from said byte stream;
- comparing a byte in the buffer against the bytes in the first comparison window and the second comparison window;
- substituting a pointer for the compared byte in the buffer if the compared byte matches a byte in the first or second comparison window;
- and outputting said substituted pointer into an output stream.
A system for compressing a byte stream of input data, comprising a buffer having at least one byte position;
- a first comparison window having at least one byte position;
- a second comparison window having at least one byte position;
- means for comparing a byte in the buffer against bytes in the comparison windows to determine a matching byte in the first comparison window or the second comparison window;
- means operatively connected to the comparison windows for generating a pointer indicating the location in a comparison window of the matched byte in the comparison window;
- means for substituting the pointer for the matched byte in the buffer;
- and means for updating the comparison windows whereby the first comparison window receives each byte in the byte stream sequentially and the second comparison window receives only those bytes in the byte stream that satisfy pre-established conditions.
Dependencies are inferred from the claim text.