Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Patent
1996-08-06
1999-09-14
Moise, Emmanuel L.
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
341 51, 341 87, 341 95, 341106, 358426, G06F 700, G06F 1500, H03M 700
Patent
active
059516232
ABSTRACT:
An adaptive compression technique which is an improvement to Lempel-Ziv (LZ) compression techniques, both as applied for purposes of reducing required storage space and for reducing the transmission time associated with transferring data from point to point. Pre-filled compression dictionaries are utilized to address the problem with prior Lempel-Ziv techniques in which the compression software starts with an empty compression dictionary, whereby little compression is achieved until the dictionary has been filled with sequences common in the data being compressed. In accordance with the invention, the compression dictionary is pre-filled, prior to the beginning of the data compression, with letter sequences, words and/or phrases frequent in the domain from which the data being compressed is drawn. The letter sequences, words, and/or phrases used in the pre-filled compression dictionary may be determined by statistically sampling text data from the same genre of text. Multiple pre-filled dictionaries may be utilized by the compression software at the beginning of the compression process, where the most appropriate dictionary for maximum compression is identified and used to compress the current data. These modifications are made to any of the known Lempel-Ziv compression techniques based on the variants detailed in 1977 and 1978 articles by Ziv and Lempel.
REFERENCES:
patent: 4386416 (1983-05-01), Giltner et al.
patent: 4464650 (1984-08-01), Eaastman et al.
patent: 4558302 (1985-12-01), Welch
patent: 4672679 (1987-06-01), Freeman
patent: 4701745 (1987-10-01), Waterworth
patent: 4814746 (1989-03-01), Miller et al.
patent: 4847619 (1989-07-01), Kato et al.
patent: 4876541 (1989-10-01), Storer
patent: 4881075 (1989-11-01), Weng
patent: 4906991 (1990-03-01), Fiala et al.
patent: 4988998 (1991-01-01), O'Brien
patent: 5001478 (1991-03-01), Nagy
patent: 5003307 (1991-03-01), Whiting et al.
patent: 5016009 (1991-05-01), Whiting et al.
patent: 5023610 (1991-06-01), Rubow et al.
patent: 5049881 (1991-09-01), Gibson et al.
patent: 5058137 (1991-10-01), Shah
patent: 5087913 (1992-02-01), Eastman
patent: 5126739 (1992-06-01), Whiting et al.
patent: 5140321 (1992-08-01), Jung
patent: 5153591 (1992-10-01), Clark
patent: 5155484 (1992-10-01), Chambers, IV
patent: 5179378 (1993-01-01), Ranganathan et al.
patent: 5243341 (1993-09-01), Seroussi et al.
patent: 5262776 (1993-11-01), Kutka
patent: 5373290 (1994-12-01), Lempel et al.
patent: 5455576 (1995-10-01), Clark, II et al.
patent: 5485526 (1996-01-01), Tobin
patent: 5561421 (1996-10-01), Smith et al.
Rodeh et al., "Linear Algorithm for Data Compression via String Matching", J. of the Assoc. For Computing Machinery, 1981, 28(1), 16-24.
Storer, J.A. et al., "Data Compression via Textual Substitution",J. of the Assoc. for Computing Machinery, 1982, 29, 928-951.
Welch, T.A., "A Technique for High-Performance Data Compression", IEEE, 1984, 8-19.
Zipf, G., Human Behavior and the Principle of Least Effort, 1949.
Ziv J. et al., "A Universal Algorithm for Sequential Data Compression", IEEE Trans. On Information Theory, 1977, IT-23(3), 337-343.
Ziv, J. et al., "Compression of Individual Sequences via Variable-Rate Coding", IEEE Trans. On Information Theory, 1978, IT-24(5), 530-536.
Bell et al., "Text Compression", 1990, Englewood Cliffs, New Jersey, Prentice Hall.
Bell, T.C., "Better OPM/L Text Compression", IEEE Trans. on Comm., 1986, COM-34(12), 1176-1182.
Bell et al., "Adaptive Dictionary Encoders: Ziv-Lempel Coding", Dictionary Techniques, Chap. 8, 214-234.
Bentley, J. L. et al., "A Locally Adaptive Data Compression Scheme", Comm. of ACM, 1986, 29(4), 320-330.
Huffman, D.A., "A Method for the Construction of Minimum-Redundancy Codes", Proceedings of the I.R.E., 1952, 40, 1098-1101.
Langdon Jr., G.G., "A Note on the Ziv-Lempel Model for Compressing Individual Sequences", IEEE Trans. On Information Theory, 1983, 29(2), 284-287.
Marcus et al., "Building a Large Annota Corpus of English: The Penn Treebank ", Computational Linguistics, 1993, 19(2), 313-330.
Miller, V.S. et al., "Variations on a Theme by Ziv and Lempel" in Combinatorial Algorithms on Words, NATO ASI Series, Apostolico, A. and Galil, Z., eds., 1985, vol. F12, 131-140.
Eisner Jason
Herz Fred
Reynar Jeffrey C.
Ungar Lyle
LandOfFree
Lempel- Ziv data compression technique utilizing a dictionary pr does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Lempel- Ziv data compression technique utilizing a dictionary pr, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Lempel- Ziv data compression technique utilizing a dictionary pr will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-1505490