Coded data generation or conversion – Digital code to digital code converters – Coding by table look-up techniques
Reexamination Certificate
1999-07-30
2001-11-20
JeanPierre, Peguy (Department: 2819)
Coded data generation or conversion
Digital code to digital code converters
Coding by table look-up techniques
C341S051000
Reexamination Certificate
active
06320523
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of Invention
The present invention relates to data compression systems. More particularly, the present invention relates to loss-less data compression and a method and means for increasing the speed of compressing a stream of data in systems that employ a dictionary to store string codes.
2. Description of the Prior Art
Heretofore, loss-less data compression algorithms were known. Some of the best known data compressions systems and methods are referred to as Lempel Ziv One (LZ-1) Lempel Ziv Two (LZ-2) and Lempel Ziv Welch (LZW). All of these adaptive loss-less data compression systems employ a dictionary for storing string codes that are indicative of strings of data and symbols or characters encountered in an input data stream. Once a string is identified it is stored as a code having fewer bits than the identified string of data so that subsequent occurrences of the same string in the data stream are replaced with the previously stored string code. All three above-mentioned data compression systems involve searching plural locations in the dictionary to determine if a string code has been previously stored for the string under examination. The process involves matching a sequence of input data characters with the same sequence already encoded in a dictionary location.
To minimize the time required for searching plural locations in the dictionary, it has been suggested that a hashing algorithm be used to perform the matching function. Hash searches compute an index in a table based on the data being sought. The efficiency of the hash table search is determined by the organization of the table and whether multiple items can hash to the same area of the table without conflict. Hashing systems suffer from high costs of implementations and complex computations which result in performance reducing overhead. One LZW hashing method is described in U.S. Pat. No. 4,558,302 which is incorporated by reference herein.
It has also been suggested that binary searches could be employed in which the memory and portions of the memory are divided and searched sequentially until a match or no match is found. Binary searches by definition require multiple searches in the dictionary and also require table reordering, but have the advantage that they reduce the overhead incurred in the complex calculations associated with hashing.
It has been suggested that a content addressable memory (CAM) or associative memory be employed to reduce the number of comparisons of the contents of plural strings located in the dictionary. This system is efficient, yet complex and it can be very costly. An example of this method is described in U.S. Pat. No. 5,838,264 which is incorporated by reference herein.
It would be desirable to provide a method and apparatus that completely avoids plural searches in data compression systems that employ string dictionaries. It is further desirable that the output from the new data compression system be formatable to be compatible with existing data compression systems such as LZW so that the existing decompressor/decoders would be able to receive and decode compressed data without any modification.
SUMMARY OF THE INVENTION
It is a principle object of the present invention to optimize the speed of data compression implemented with the use of a string dictionary.
It is another principle object of the present invention to eliminate the need for searching plural address locations in a string dictionary of a data compressor.
It is another principle object of the present invention to provide an LZW string dictionary arranged as a look up table having only one unique address for every possible novel string code so that a search in the dictionary is eliminated.
It is another principle object of the present invention to provide a novel data compression system that can be efficiently formatted to compress Chinese, Japanese and other complex character codes without the penalty of extensive searches in a string dictionary.
It is another principle object of the present invention to provide a data compression system that may be implemented using low cost random access memory (RAM) without placing a burden on the computing system.
It is another principle object of the present invention to provide a novel method of performing LZW data compression at speeds higher than was possible heretofore, thus, increasing real time throughput for high speed networks that have standardized on or employ string data compression such as LZW.
It is another object of the present invention to provide a new and improved method of performing LZW data compression that speeds up the process of compressing the data stream and provides a means for higher transmission rates over existing lines and links.
It is a principle object of the present invention to provide a novel expanded pointer address code for strings of data encountered in a data stream to be compressed.
It is a principle object of the present invention to provide a novel string dictionary having a greater number of accessible addresses than the maximum number of string codes being used in a full dictionary.
It is a principle object of the present invention to store a unique single string code value of fewer bits in a dictionary that is representative of the string of characters contained in the unique pointer address code of greater bits.
It is a principle object of the present invention to generate a compressed stream of data in LZW format without the need to search plural address locations in a string dictionary.
It is a principle object of the present invention to eliminate the need to store extension characters with string codes in an LZW dictionary.
It is the general object of the present invention to use the same LZW string dictionary a plurality of times without having to stop and clear the contents when the dictionary is full.
It is the general object of the present invention to purge or clear all or select portions of a string dictionary without reading over the contents of all memory locations.
It is the general object of the present invention to store the address locations of string codes in an auxiliary look up table to enable clearing by overwriting only those address locations where code data has been stored.
According to these and other objects of the present invention there is provided a method and apparatus for optimum high speed performance of data compression using a string dictionary which includes generating unique pointer addresses which comprise a string code portion and an extension code portion. The novel pointer address comprises a string code portion representative of the last string match found in the dictionary, and an extension character code portion representative of the next unknown character in the data stream appended to the string code portion. When the string code portion is defined by no more than 12 bits and the extension character code portion by 8 bits, then there are only 2
20
possible pointer addresses. There are provided 2
20
corresponding dictionary addresses so that only one address in the dictionary need be accessed in order to determine if the string representative of the pointer address has been previously observed and replaced by a string code stored in the dictionary at the pointer address.
REFERENCES:
patent: 4558302 (1985-12-01), Welch
patent: 4929946 (1990-05-01), O'Brien et al.
patent: 5016009 (1991-05-01), Whiting et al.
patent: 5049881 (1991-09-01), Gibson et al.
patent: 5151697 (1992-09-01), Bunton
patent: 5229768 (1993-07-01), Thomas
patent: 5373290 (1994-12-01), Lempel et al.
patent: 5389922 (1995-02-01), Seoussi et al.
patent: 5455576 (1995-10-01), Clark, II et al.
patent: 5525982 (1996-06-01), Cheng et al.
patent: 5642112 (1997-06-01), Cooper
patent: 5646617 (1997-07-01), Ohmoto et al.
patent: 5798718 (1998-08-01), Hadady
Solomon, D., “Data Compression: The Complete Reference”, 1998, Springer-Verlag, Chapter 3, Appendix H, New York, NY.
P. 1 of International Search Report, dated Oct. 17, 2000.
York Kenneth Lindsay
York Thayer Lindsay
Jean-Pierre Peguy
Jeanglaude Jean Bruner
Sowell John B.
Starr Mark T.
Unisys Corporation
LandOfFree
Method and apparatus for reducing the time required for... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for reducing the time required for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for reducing the time required for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2595322