Coded data generation or conversion – Digital code to digital code converters – Adaptive coding
Reexamination Certificate
2001-09-13
2003-11-25
Tokar, Michael (Department: 2819)
Coded data generation or conversion
Digital code to digital code converters
Adaptive coding
C341S050000, C341S085000, C341S106000, C341S057000
Reexamination Certificate
active
06653950
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention relates to LZ dictionary based data compression systems particularly with respect to the LZW compression methodology. More particularly, the invention relates to a parallel architecture for storing and accessing data character strings in the compressor.
2. Description of the Prior Art
Professors Abraham Lempel and Jacob Ziv provided the theoretical basis for LZ data compression and decompression systems that are in present day widespread usage. Two of their seminal papers appear in the IEEE Transactions on Information Theory, IT-23-3, May 1977, pp. 337-343 and in the IEEE Transactions on Information Theory, IT-24-5, September 1978, pp. 530-536. A ubiquitously used data compression and decompression system known as LZW, adopted as the standard for V.42 bis modem compression and decompression, is described in U.S. Pat. No. 4,558,302 by Welch, issued Dec. 10, 1985. LZW has been adopted as the compression and decompression standard used in the GIF image communication protocol and is utilized in the TIFF image communication protocol. GIF is a development of CompuServe Incorporated and the name GIF is a Service Mark thereof. A reference to the GIF specification is found in GRAPHICS INTERCHANGE FORMAT, Version 89a, July 31, 1990. TIFF is a development of Aldus Corporation and the name TIFF is a Trademark thereof. Reference to the TIFF specification is found in TIFF, Revision 6.0, Final—Jun. 3, 1992.
Further examples of LZ dictionary based compression and decompression systems are described in the following U.S. Pat. No.: 4,464,650 by Eastman et al., issued Aug. 7, 1984; U.S. Pat. No. 4,814,746 by Miller et al., issued Mar. 21, 1989; U.S. Pat. No. 4,876,541 by Storer, issued Oct. 24, 1989; U.S. Pat. No. 5,153,591 by Clark, issued Oct. 6, 1992; U.S. Pat. No. 5,373,290 by Lempel et al., issued Dec. 13, 1994; U.S. Pat. No. 5,838,264 by Cooper, issued Nov. 17, 1998; U.S. Pat. No. 5,861,827 by Welch et al., issued Jan. 19, 1999; and U.S. Pat. No. 6,188,333 by Cooper, issued Feb. 13, 2001.
In dictionary based LZ compression and decompression systems, the compressor and decompressor dictionaries may be initialized with all of the single character strings of the character alphabet. In some implementations, the single character strings are considered as recognized although not explicitly stored. In such systems the value of the single character may be utilized as its code and the first available code utilized for multiple character strings would have a value greater than the single character values. In this way the decompressor can distinguish between a single character string and a multiple character string and recover the characters thereof. For example, in the ASCII environment, the alphabet has an 8 bit character size supporting an alphabet of 256 characters. Thus, the characters have values of 0-255. The first available multiple character string code can, for example, be 258 where the codes 256 and 257 are utilized as control codes as is well known.
In the prior art dictionary based LZ compression systems, data character strings are stored and accessed in the compressor dictionary utilizing well known search tree architectures and protocols. Typically, the search for the longest matching string stored in the dictionary is an iterative process where sequentially matched strings in the dictionary are extended by sequentially fetched input characters, respectively, until the longest matching string is determined. At each iteration, the dictionary is accessed to determine if the new string extension is a previously stored dictionary entry. Potentially, at each iteration, access to all of the strings stored in the dictionary may be effected to determine the required information. For example, in systems implemented utilizing an associative memory dictionary, such as in said U.S. Pat. Nos. 5,373,290 and 5,838,264, it may be necessary, at an iteration, to access all dictionary locations to determine that an extended string is not stored therein.
The conventional iterative protocols, therefore, tend to be time consuming. Although the known dictionary architectures and protocols provide efficient data compression systems, it is a continuing objective in the art to improve compressor performance.
SUMMARY OF THE INVENTION
The present invention provides new string storage and access architecture and protocols which, it is believed, will improve the speed of dictionary based LZ type data compressors.
In the present invention, a plurality of subdictionaries are arranged in levels for storing strings of data characters encountered in the input stream. The strings stored in a subdictionary have the same number of characters with respect to each other and the strings stored in the subdictionary of a level have one character more than the strings stored in the subdictionary at the level prior thereto. A plurality of data characters are fetched from the input and applied to the levels, respectively. The fetched characters are searched by comparing the fetched characters to the stored strings to determine the longest match therewith. The longest match 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 so as to provide the output stream of compressed codes corresponding to the input stream of data characters. 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.
In particular, the fetched characters are searched by searching the strings stored at a particular level for a string comprising a string matched at the level prior thereto extended by the fetched character applied to the particular level. The string code of a string matched at the particular level is applied to the next level in cascade fashion.
A best mode 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 2 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.
REFERENCES:
patent: 4814746 (1989-03-01), Miller et al.
patent: 5179378 (1993-01-01), Ranganathan et al.
patent: 5293164 (1994-03-01), Bugajski et al.
patent: 5442350 (1995-08-01), Iyer et al.
patent: 5592667 (1997-01-01), Bugajski
patent: 5642112 (1997-06-01), Cooper
patent: 5838264 (1998-11-01), Cooper
patent: 5861827 (1999-01-01), Welch et al.
patent: 6018303 (2000-01-01), Sadeh
Ming-Bo Lin; Journal of VLSI Signal Processing Systems for Signal, Image and Video Techonologg; “A Hardware Architecuted of the LZW Compression and Decompression Algorithms Based on Parallel Dictionaries”; pp 369-381; (Kluwer Academic Publishers, vol. 26, No. 3, Nov. 2000).*
Ming-Bo Lin;Journal of VLSI Signal Processing Systems for Signal, Image, and Video Technology; “A Hardware Architecture for the LZW Compression and Decompression Algorithms Based on Parallel Dictionaries”; pp 369-381; (Kluwer Academic Publishers, vol. 26, No. 3, Nov. 2000).
K.S. Ng, et al;Proceedings of the 4thInternational Conference on Document Analysis and Recognition(ICDAR; “Dynamic Word Based Text Compression”, pp. 412-416, (Proceedings of the ICDAR, Los Alamitos, IEEE Comp. Soc, US, vol. II, Aug. 18, 1997).
Atlass Michael B.
Cooper Albert B.
Nguyen Linh Van
Starr Mark T.
Tokar Michael
LandOfFree
Data compression method and apparatus utilizing cascaded... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Data compression method and apparatus utilizing cascaded..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data compression method and apparatus utilizing cascaded... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3168403