Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reissue Patent
2001-09-14
2010-02-23
Homayoumehr, Farid (Department: 2439)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C708S212000, C341S050000, C341S051000, C341S087000, C341S095000, C341S106000, C358S426010, C380S217000
Reissue Patent
active
RE041152
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), Eastman 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.
patent: 5590317 (1996-12-01), Iguchi et al.
patent: 5872530 (1999-02-01), Domyo et al.
patent: 0 286 719 (1988-10-01), None
patent: 5-241775 (1993-09-01), None
patent: 5-241777 (1993-09-01), None
patent: 6-28149 (1994-02-01), None
patent: 6-161705 (1994-06-01), None
patent: 7-64765 (1995-03-01), None
patent: 7-152533 (1995-06-01), None
patent: 8-69370 (1996-03-01), None
patent: 8-505008 (1996-05-01), None
patent: 8-162874 (1996-06-01), None
“Adaptive Dictionary Encoders: Ziv-Lempel Coding”, Section 8.3.1 LZ 77, Jan. 2, 1990, 218-227, XP-002132837.
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 annoted 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”,Combinatorial Algorithms on Words, NATO ASI Series, Apostolico, A and Galil, Z., eds., 1985, vol. F12, 131-140.
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 universial 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.
Eisner Jason
Herz Fred
Reynar Jeffrey C.
Ungar Lyle
Homayoumehr Farid
Pinpoint Incorporated
Woodcock & Washburn LLP
LandOfFree
Lempel-Ziv data compression technique utilizing a dictionary... 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..., 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... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-4154238