Coded data generation or conversion – Digital code to digital code converters – Adaptive coding
Patent
1990-12-27
1992-10-06
Hoff, Marc
Coded data generation or conversion
Digital code to digital code converters
Adaptive coding
341 67, 341 79, H03M 738
Patent
active
051535912
DESCRIPTION:
BRIEF SUMMARY
FIELD OF THE INVENTION
The present invention relates to methods and apparatus for compressing data, methods and apparatus for decoding the compressed data, a method of transmitting data and data processing apparatus utilising compressed data. The above methods and apparatus all utilise an adaptive string encoding technique which involves a dictionary having a search tree and means for maintaining this search tree. The invention is applicable particularly but not exclusively to adaptive string encoding utilising the Ziv-Lempel algorithm. The basic form of this algorithm is described in IEEE Transactions IT-23, May 3rd 1977 pp337-343 "A Universal Algorithm for Sequential Data Compression"--J. Ziv and A. Lempel.
BACKGROUND OF THE INVENTION
The basic Ziv-Lempel encoder has a dictionary, in which each entry has an associated index number. Initially the dictionary contains only the basic alphabet of the source. During the encoding process, new dictionary entries are formed by appending single symbols to existing entries. The dictionary may be considered to be in the form of a search tree of connected symbols of the source alphabet. Nodes in the tree correspond to specific sequences of symbols which begin at the root of the tree and the data is compressed by recognising strings of symbols in the uncompressed input data which correspond to nodes in the tree, and transmitting the index of the memory location corresponding to the matched node. A corresponding search tree is provided in the decoder which receives the index representing the compressed data and the reverse process is performed by the decoder to recover the compressed data in its original form. The search tree of the encoder gradually grows during the encoding process as further strings of symbols are identified in the input data and in order to enable the decoder to decode the compressed data, its search tree must be updated to correspond with the search tree of the encoder.
The Ziv-Lempel algorithm has been found difficult to implement in practice, since it requires an indefinitely large memory to store the search tree in its basic form. The use of data structures such as the "trie" structure disclosed by Sussenguth (ACM Sort Symposium 1962) can however greatly improve the storage efficiency and search time associated with text strings. EPA127,815 (Miller and Wegman) and EPA129439 (Welch) disclose similar implementations of the Ziv Lempel algorithm based on the use of a trie structure.
In EPA127,815 (Miller and Wegman) improvements are described to the Ziv-Lempel algorithm which enhance the memory efficiency and speed up the encoding process. The dictionary is held in the form of a tree, with each node containing a single character and a pointer to the parent node which represents the prefix string. A hash table is used to determine, given a matched sub-string and the next input character, whether the extended sub-string is in the dictionary. However, the hash table requires a significant amount of memory and processing time in addition to that needed for the storage of the basic tree structure used to encode the dictionary.
EPA129,439 (Welch) discloses a high speed data compression and decompression apparatus and method in which strings of symbols in the input message are recognised and stored. Strings are entered into a string table and are searched for in the string table by means of a hashing function which utilises a hash key comprising a prior code signal and an extension character to provide a set of N hash table addresses where N is typically 1 to 4. The N RAM locations are sequentially searched and if the item is not in the N locations, it is considered not to be in the table. This procedure is stated to reduce compression efficiency but to simplify substantially the implementation.
U.S. Pat. No. 4,612,532 (Bacon et al) discloses a system, not based on the Ziv-Lempel algorithm, for the dynamic encoding of a stream of characters in which each character is associated with a "follow set" table of characters which usually follow it, in order
REFERENCES:
patent: 4464650 (1984-08-01), Eastman et al.
patent: 4906991 (1990-03-01), Fiala et al.
patent: 4990910 (1991-02-01), Takishima et al.
patent: 5003307 (1991-03-01), Whiting et al.
IBM Technical Disclosure Bulletin, vol. 14, No. 11, Apr. 1972, Koch, "Representation of Tree Data Structures for Manipulation and Search Operation Data", pp. 3521-3522.
IBM Technical Disclosure Bulletin, vol. 20, No. 8, Jan. 1978, Winterbottom, "General Purpose Database Structure", pp. 3320-3323.
IBM Technical Disclosure Bulletin, vol. 25, No. 11B, Apr. 1983, Crus et al, "Method for Deleting Records from a Hierarchical Data Base", pp. 5886-5888.
British Telecommunications public limited company
Hoff Marc
LandOfFree
Method and apparatus for encoding, decoding and transmitting dat 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 encoding, decoding and transmitting dat, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for encoding, decoding and transmitting dat will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-1192686