Coded data generation or conversion – Digital code to digital code converters – Adaptive coding
Reexamination Certificate
2000-05-04
2001-10-23
JeanPierre, Peguy (Department: 2819)
Coded data generation or conversion
Digital code to digital code converters
Adaptive coding
C341S063000
Reexamination Certificate
active
06307488
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention relates to LZW data compression and decompression systems particularly with respect to reducing compressor and decompressor dictionary accesses by forming portions of the compressor input data character stream into grouped data characters recognizable by the compressor and decompressor.
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, Jul. 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. patents: 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; and U.S. Pat. No. 5,861,827 by Welch et al., issued Jan. 19, 1999.
In the above 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 above dictionary based LZ compression and decompression systems, numerous dictionary accesses are required at the compressor for compressing an input stream of data characters and also at the decompressor to recover the data characters from the compressed code stream. At the compressor at least one dictionary access is required for each input data character and at the decompressor at least one dictionary access is required for each recovered data character. It is desirable in such systems to minimize the number of dictionary accesses so as to enhance system performance.
SUMMARY OF THE INVENTION
A data compressor compresses an input stream of data characters into an output stream of compressed codes by storing strings of data characters encountered in the input, a string being stored as at least one grouping of a predetermined number of the data characters (grouped character) followed by one or more of the data characters. Each stored string has a code associated therewith. In a compression cycle, the input stream is formed into at least one grouped character followed by one or more of the data characters to provide a formed input stream. The formed input stream is compared to the stored strings by matching the grouped character(s) of the formed input stream with the grouped character(s) of the stored strings and sequentially matching the data character(s) of the formed input stream that follow the grouped character(s) thereof with the data character(s) of the stored strings that follow the grouped character(s) thereof until one of the data characters causes a mismatch to occur. In this manner, the longest match between the formed input stream and the stored strings is determined. An extended string is stored comprising the longest match extended by the data character that caused the mismatch and a code is assigned to the stored extended string. The code associated with the longest match is output so as to provide the stream of compressed codes. A grouped character comprising the data character that caused the mismatch concatenated by one less than the predetermined number of the next following data characters is used to begin the next compression cycle.
The predetermined number of data characters of the grouped character is selected so that the grouped character is recognized at the decompressor and the data characters comprising the grouped character can be recovered thereat.
In one embodiment, data character strings comprise an initial grouped character followed by as many data characters as can be matched. In another embodiment, a string is comprised of consecutive grouped characters followed by one or more data characters up to a maximum of one less than the predetermined number. In this embodiment, when extension of a string for storage would result in the predetermined number of data characters following the consecutive grouped characters, the predetermined number of data characters is appended to the consecutive grouped characters as a further grouped character.
The invention further includes a novel data decompressor for recovering the input stream of data characters from the output stream of compressed codes for each compressor embodiment. The decompressor recreates, from the stream of compressed codes, the strings stored at the compressor in lock-step fashion therewith. Furthermore, each decompressor utilizes novel exception case processing based on that of said U.S. Pat. No. 4,558,302.
REFERENCES:
patent: 4558302 (1985-12-01), Welch
patent: 5463390 (1995-10-01), Whitting et al.
patent: 5764167 (1998-06-01), Adams et al.
patent: 5861827 (1999-01-01), Welch et al.
patent: 6169499 (2001-01-01), Cooper
patent: 6188333 (2001-02-01), Cooper
Graphics Interchange Format (sm), Version 89a, Jul. 31, 1990.
TIFF Revision 6.0 Final—Jun. 3, 1992.
Cooper Albert B.
Jean-Pierre Peguy
Starr Mark T.
Unisys Corporation
LandOfFree
LZW data compression and decompression apparatus and method... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with LZW data compression and decompression apparatus and method..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and LZW data compression and decompression apparatus and method... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2591336