摘要 |
The data compressor utilizes a plurality of subdictionaries arranged in levels for storing strings of data characters. The subdictionary at the first level stores two character strings and a subdictionary at a subsequent level stores strings that are one character longer than the strings stored in the subdictionary at the level prior thereto. A plurality of data characters are fetched from the input into an input buffer and applied to the respective levels. The subdictionary at a level is searched for the string comprising the string matched at the prior level extended by the fetched character applied to the level. The string code of a string matched at a level is cascaded to the next level. The longest match with the fetched characters is determined by one of the fetched characters resulting in a mismatch at one of the levels. The string code associated with the longest match is output. An extended string comprising the longest match extended by the fetched character that resulted in the mismatch is inserted into the subdictionary at the mismatching level. One embodiment of the invention includes an auxiliary table at each of the levels except for the first level. While the subdictionary at the first level is being searched for a two character string match, each of the subdictionaries at the remaining levels is screened for stored strings ending in the fetched input character applied to the level. The screened strings are transferred to the corresponding auxiliary table. At a level, the cascaded string code from the previous level is searched in the auxiliary table.
|