Data compression apparatus and method using matching string searching and Huffman encoding
AssigneeStac Electronics, Inc.
InventorsClay Mayers, Douglas L. Whiting
Life of this patent
Estimating the term…
Abstract
An apparatus and method for converting an input data character stream into a variable length encoded data stream in a data compression system. A sliding window data compression algorithm is combined with Huffman encoding on the strings and raw bytes. The Huffman table, in a compressed form, is prepended to the encoded output data. The Huffman codes representing the shortest strings encode both the string length and part of the string offset. Assigning Huffman codes to represent the combined length and offset allows the use of a smaller sliding window size without sacrificing compression ratio. The smaller window size allows implementations in software and hardware to minimize memory usage, thus reducing cost.
Claims26
A data compression method comprising:
- performing a search for matching strings in a window of input bytes, said search producing a stream of tokens, said tokens representing either a raw byte or a matching string of a certain length and a certain offset back into said window;
- assigning said tokens to predefined bins, some of said bins containing matching strings of a predetermined length and within a certain offset range;
- assigning variable length codes to each bin based on the frequency of occurrence of tokens assigned to each bin;
- outputting for each token generated said variable length codes for said bin to which each token is assigned to the output data stream;
- and
- after each said variable length code is output, outputting extra bits, if required, to specify exactly said token within said bin.
A data decompression method which decompresses a compressed input data stream, comprising:
- maintaining a history array of all bytes output;
- and
- repeating the following steps until the input data stream is exhausted or until a code indicating the end of said compressed input data stream is encountered:
- extracting a bin code from said compressed input data stream;
- extracting any extra bits required to determine exactly the token associated with said bin code;
- operative when said token corresponds to a raw byte, outputting said raw byte;
- and
- operative when said token corresponds to a matching string, outputting all bytes of said string by indexing back into said history array using the offset of said string.
A data compression apparatus comprising:
- means for performing a search for matching strings in a window of input bytes, said search producing a stream of tokens, said tokens representing either a raw byte or a matching string of a certain length and a certain offset back into said window;
- means for assigning said tokens to predefined bins, some of said bins containing matching strings of a predetermined length and within a certain offset range;
- means for assigning variable length codes to each bin based on the frequency of occurrence of tokens assigned to each bin;
- means for outputting for each token generated said variable length codes for said bin to which each token is assigned to the output data stream;
- and
- means for outputting extra bits, if required, to specify exactly said token within said bin.
A data decompression method which decompresses a compressed input data stream, comprising:
- means for maintaining a history array of all bytes output;
- and
- means for extracting a bin code from said compressed input data stream;
- means for extracting any extra bits required to determine exactly the token associated with said bin code;
- means for outputting a raw byte;
- and
- means for outputting all bytes of a matching string by indexing back into said history array using the offset of said string.
Dependencies are inferred from the claim text.