Stem for dynamically compressing and decompressing electronic da

Details Stem for dynamically compressing and decompressing electronic da Stem for dynamically compressing and decompressing electronic da

1987-10-15

1989-10-24

Shoop, Jr., William M.

Coded data generation or conversion

Digital code to digital code converters

Adaptive coding

341 67, 341106, H03M 742

Patent

active

048765414

ABSTRACT:
A data compression system for encoding and decoding textual data, including an encoder for encoding the data and for a decoder for decoding the encoded data. Both encoder and decoder have dictionaries for storing frequently-appearing strings of characters. Each string is identified by a unique pointer. The input data stream is parsed and matched with strings in the encoder dictionary using a novel matching algorithm. The pointer associated with the matched string is then transmitted to a remote location for storage or decoding. Thereafter, using a novel update algorithm the encoder dictionary is updated to include new strings of data based on the matched string of data. If required, a novel deletion algorithm is employed to remove infrequently used strings of data to provide room for the newly generated strings of data. The strings of data may be arranged using a modified least recently used queue.
The decoder matches each unique pointer in the stream of compressed input data with a corresponding pointer in the decoder dictionary. The decoder then transmits the string of character data associated with the matched pointer, thereby providing textual data in original, uncompressed form. Thereafter, using the novel update and deletion algorithms, new strings of data are added to, and old strings of data are deleted from, the decoder dictionary, so as to ensure both encoder and decoder dictionaries contain identical strings of data.

REFERENCES:
patent: 4464650 (1984-08-01), Eastman et al.
patent: 4558302 (1985-12-01), Welch
patent: 4612532 (1986-09-01), Bacon et al.
D. A. Huffman; "A Method for the Construction of Minimum-Redundancy Codes"; Proceedings of the Ire; vol. 40, pp. 1098-1101; 1952.
A Lempel et al; "On the Complexity of Finite Sequences"; IEEE Transactions of Information Theory; 22:1, pp. 75-81; 1976.
V. S. Miller et al; "Variations on a Theme by Lempel and Ziv", Combinatorial Algorithms on Words, pp. 131-140; 1985.
J. B. Seery et al; "A Universal Data Compression Algorithm Description and Preliminary Results"; Technical Memorandum; 1977.
J. B. Seery et al; "Further Results on Universal Data Compression"; Technical Memorandm; 1978.
J. A. Storer et al; "Data Compression Via Textual Substitution"; Journal of the Association for Computing Machinery; vol. 29:4; 1982.
J. A. Storer; "Textual Substitution Techniques for Data Compression"; Combinatorial Algorithms on Words; pp. 120-121; 1985.
T. A. Welch; "A Technique for High-Performance Data Compression"; IEEE Computer, vol. 17:6; 1984.

Affiliated with

Also associated with

Rating

Stem for dynamically compressing and decompressing electronic da does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Stem for dynamically compressing and decompressing electronic da, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Stem for dynamically compressing and decompressing electronic da will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-1591447