Image analysis – Image compression or coding – Lossless compression
Reexamination Certificate
1998-12-15
2001-05-29
Mancuso, Joseph (Department: 2621)
Image analysis
Image compression or coding
Lossless compression
Reexamination Certificate
active
06240213
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to a data compression system; and, more particularly, to a data compression system with a string matching module employing a recursive updating algorithm.
DESCRIPTION OF THE PRIOR ART
In general, the available frequency bandwidth of a conventional transmission channel is limited in digitally televised systems. Accordingly, in order to transmit the large amount of digital data therethrough, it is necessary to compress or reduce the volume of data through the use of various data compression techniques.
Although many different data compression techniques are known in the art, one of the most useful is the so-called dictionary-based universal compression techniques. Among these, the most widely used one is a standard coding algorithm, e.g., CCITT (International Telegragh and Telephone Consultative Committee V.42bis), established by CCITT, wherein the standard coding algorithm is developed as a practical technique for compressing data based on the Ziv-Lempel coding algorithm.
In the CCITT V.42bis, an encoding and a decoding apparatus are provided, each having a fixed, finite amount of memory. This memory, also referred to as a “dictionary”, contains a finite number of entries of characters. Each entry has a unique codeword associated therewith. The dictionaries at the encoding and the decoding apparatus may be initialized at the beginning to contain identical information.
Referring to
FIG. 1
, there is illustrated a block diagram of an encoding apparatus
10
used in the conventional data compression system. The encoding apparatus
10
comprises a string matching block
12
, a dictionary
14
, an entry updating block
16
and an encoder
18
.
The string matching block
12
receives an input stream of characters on a character-by-character basis and finds a longest matching string of characters that matches one of a plurality of entries within the dictionary
14
. Specifically, a string, i.e., a sequence of characters, is formed from a first character and, if the string matches with an entry of the dictionary, a next character is read and appended to the string so as to repeat this step. If the string matches with no entry within the dictionary, the last character appended to the string is removed to generate the longest matching string of characters, wherein the string shortened represents the longest matching string and the last character represents an unmatched character that does not match.
The encoder
18
detects a codeword of the matched entry within the dictionary
14
identified by the longest matching string and transfers the codeword as an output.
In the meantime, the entry updating block
16
updates a new entry into the dictionary
14
based on the longest matching string in order to maintain an efficient compression, wherein the new entry is formed by appending the longest matching string to the unmatched character resulting from the string matching operation. A new codeword is assigned to the new entry to be stored in the dictionary.
As a result, the dictionary
14
performs the string matching procedure, the string update procedure and the string encoding procedure as described above. If the new entry itself has already been in the dictionary, it will not be added.
Referring to
FIG. 2
, there is illustrated the manner by which the longest matching string is encoded and the new entry is updated in the conventional data compression system. It is assumed that the dictionary contains characters ‘A’ to ‘Z’ with their respective corresponding codewords ‘0’ to ‘25’ as a plurality of entries and an input stream of characters, e.g., ‘ABABCBCABCBCAD’, is provided. At a 1st level, the first character ‘A’ of the input stream is matched with the longest matching string ‘A’ to be encoded as the codeword ‘0’ since the string ‘AB’ has not been enrolled in the dictionary. Thereafter, the string ‘AB’, which is generated by linking the longest matching string ‘A’ to the unmatched character ‘B’, is enrolled as the new entry with the new codeword ‘26’ in the dictionary. At a 2nd level, the longest matching string ‘B’ is encoded with the codeword ‘1’ and the new entry ‘BA’ is enrolled with the new codeword ‘27’ in the dictionary in a similar manner. At next levels, the longest matching strings ‘AB’, ‘C’, ‘B’, ‘C’, ‘ABC’, ‘BC’ and ‘A’ are sequentially encoded while the new entries ‘ABC’, ‘CB’, ‘BC’, ‘CA’, ‘ABCB’, ‘BCA’ and ‘AD’ are sequentially enrolled in the dictionary.
Since, however, the compression efficiency in the CCITT V.42bis depends on how the dictionary is updated based on the input stream of characters, it is required that the number of new entries which can be enrolled for each longest matching string increases.
SUMMARY OF THE INVENTION
It is, therefore, a primary object of the present invention to provide a data compression system capable of updating a dictionary therein with one or more entries for each longest matching string associated with a codeword.
In accordance with the present invention, there is provided a data compression system for compressing an input stream of characters into a compressed stream of codewords, comprising:
dictionary means for storing a plurality of entries of characters, each entry being identified by a unique codeword;
matching means for parsing said input stream of characters into a number of parsed strings of characters;
encoder for transmitting the unique codeword identifying each parsed string; and
update means for adding N new entries of characters to said dictionary means, wherein all of said N new entries include an unmatched character which is appended to said each parsed string, N being an integer larger than or equal to 0, and assigning a new codeword to each of said N new entries.
REFERENCES:
patent: 4876541 (1989-10-01), Storer
patent: 5151697 (1992-09-01), Bunton
patent: 5455576 (1995-10-01), Clark, II et al.
patent: 5534861 (1996-07-01), Chang et al.
patent: 5703581 (1997-12-01), Matias et al.
patent: 5951623 (1999-09-01), Reynar et al.
patent: 5955976 (1999-09-01), Heath
patent: 0687995 (1995-12-01), None
Bayat Ali
Daewoo Electronics Co. Ltd.
Mancuso Joseph
Pennie & Edmonds LLP
LandOfFree
Data compression system having a string matching module 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 system having a string matching module, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data compression system having a string matching module will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2478020