Literal handling in LZ compression employing MRU/LRU encoding

Details Literal handling in LZ compression employing MRU/LRU encoding Literal handling in LZ compression employing MRU/LRU encoding

1998-09-11

2001-04-17

JeanPierrre, Peguy (Department: 2819)

Coded data generation or conversion

Digital code to digital code converters

Coding by table look-up techniques

C341S051000, C341S063000

Reexamination Certificate

active

06218970

ABSTRACT:

TECHNICAL FIELD
This invention relates to Lempel-Ziv data compression, and, more particularly, to the handling of literals which are not output as part of a string match during the data compression process.
BACKGROUND OF THE INVENTION
With the continued growth in demand for data transmission and data storage capacities, improved lossless data compression techniques are continually sought. As described in coassigned U.S. Pat. No. 5,652,878, of the many classes of lossless data compression, one of the most useful is the class of dictionary based compression techniques. Among these, the most useful today are the so-called Ziv-Lempel variable-length encoding procedures ascribed to J. Ziv and A. Lempel who suggested the “LZ1” length offset encoding scheme. The LZ1 process uses a fixed size sliding “history” window into the past source data string as the dictionary. Matches are encoded as a “match length” and an “offset” from an agreed position.
Because LZ1 scrolls the source string over a fixed sized sliding history window to create an adaptive dictionary, identification of duplicate “matching” strings in the source data is at first difficult, but becomes very efficient. Once a matching string is encoded as a “length” and “offset”, the necessary decoding process is rapid and efficient, requiring no dictionary preload. The '878 patent illustrates an LZ1 compression technique which has been denominated the “adaptive lossless data compression” technique, or “ALDC”.
All sliding window data compression processes suffer from what may be called “start-up losses” and “non-redundancy losses” in compression efficiency and corresponding increases in entropy. Because each source string or block begins with an empty “dictionary”, the first source symbol must be passed through as a raw word without compression, and begins building the dictionary. Similarly, a string of input data which has already been encrypted or compressed and lacks substantial redundancy, will likely lack the matches required to achieve compression, and these source symbols must also be passed through as raw words without compression. The raw words must be identified as such, however, thereby leading to an expansion of the data.
Only after accumulating a substantial dictionary, by having the sliding window fill up with input data having substantial redundancy, are matches found for increasing numbers of substrings which allow encoding efficiency to build up.
In the original LZ1 arrangement, called “LZ77”, all source input is output in the form of a three part token having the length and offset together with a flag, which is the first character of the compressed substring. Techniques such as ALDC overcome the problem when a non-redundant character is encountered by not sending the three part token, but instead providing the character unchanged, called a “literal”, and providing it with a designation to indicate that it is not compressed. A typical designation is an added “zero” bit for each word of the source string. Thus, when encountering a string of non-redundant input data, the compression is expanded by a much smaller length than is likely with the original LZ1 technique. However, LZ1 techniques such as ALDC still must actually expand the data by one bit for every word, typically a {fraction (9/8)} expansion to output them as literals.
Because of this problem, alternative compression techniques have been designed to offer special advantages in particular circumstances. An example is LZ2 compression (also known as LZ78 or the related version known as LZW) which captures redundancies and maintains them in a dictionary for, e.g., an entire record, as described in “The Data Compression Book”, M. Nelson, M & T Publishing, 1991, pp. 277-311. Thus, the opportunity for having redundancies is expanded, albeit at the cost of an expanded dictionary buffer.
SUMMARY OF THE INVENTION
It is an object of the present invention to handle literals so as to reduce the likely expansion of the resultant output.
Disclosed are a method and system for handling literals in a Lempel-Ziv data compression system. The literals are arranged in a storage array in an MRU/LRU format in a defined sequential MRU/LRU order, with shorter MRU/LRU reference codes assigned to the MRU literals and longer MRU/LRU reference codes to the LRU literals. Upon receiving an input literal, a selector selects the literal and a reference encoder provides the assigned MRU/LRU reference code for the literal as the output. If the literal is not already at the top of the MRU/LRU format stack, the literals are then rearranged. An incrementor is responsive to the literal selection, for incrementing downward one location in the sequential order, all of the literals in the storage array from the top of the MRU order to the literal immediately preceding the selected literal, and the selector moves the selected literal to the top of the MRU order.
For a fuller understanding of the present invention, reference should be made to the following detailed description taken in conjunction with the accompanying drawings.


REFERENCES:
patent: 4906991 (1990-03-01), Fiala et al.
patent: 5247638 (1993-09-01), O.Brien et al.
patent: 5412384 (1995-05-01), Chang et al.
patent: 5450562 (1995-09-01), Rosenberg et al.
patent: 5534861 (1996-07-01), Chang et al.
patent: 5652878 (1997-07-01), Craft
patent: 5689255 (1997-11-01), Frazier et al.

Affiliated with

Also associated with

Rating

Literal handling in LZ compression employing MRU/LRU encoding does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Literal handling in LZ compression employing MRU/LRU encoding, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Literal handling in LZ compression employing MRU/LRU encoding will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2524423