Coded data generation or conversion – Digital code to digital code converters – Adaptive coding
Patent
1993-03-12
1995-10-03
Young, Brian K.
Coded data generation or conversion
Digital code to digital code converters
Adaptive coding
H03M 730
Patent
active
054555779
ABSTRACT:
A method and system for compressing a stream of bytes in a compression system. The compression system has a search data structure containing slots for identifying the position of occurrences of byte sequences in an input stream. A byte sequence is retrieved from the input stream. The method then determines whether the search data structure contains a slot identifying the position of a byte sequence that matches the retrieved byte sequence. If the search data structure contains a slot which identifies a matching byte sequence, then the contents of a search data structure slot containing the match is replaced with the position of the retrieved byte sequence. If the search data structure does not contain a slot identifying a matching byte sequence, then a slot is selected using a least recently updated slot algorithm. The contents of this least recently updated slot are then replaced with the position of the retrieved byte sequence. When a matching byte sequence is determined, an indicator of the position identified in the slot before replacement is output. If no matching byte sequence is determined, then a byte of the retrieved byte sequence is output.
REFERENCES:
patent: 4021782 (1977-05-01), Hoerning
patent: 4464650 (1984-08-01), Eastman et al.
patent: 4701745 (1987-10-01), Waterworth
patent: 4730348 (1988-03-01), MacCrisken
patent: 4814746 (1989-03-01), Miller et al.
patent: 4906991 (1990-03-01), Fiala et al.
patent: 5016009 (1991-05-01), Whiting et al.
patent: 5155484 (1992-10-01), Chambers, IV
James A. Storer et al., "Data Compression via Textual Substitution", Journal of the Asociation for Computing Machinery, vol. 29, No. 4, Oct. 1982, pp. 928-951.
Tescher, P. "A Modified Lempel-Ziv-Welch Data Compression Scheme" (1987), Australian Computer Science Communications, 9(1), 262-272.
Bell, Timothy, et al., Text Compression, Prentice Hall, New Jersey, 1990, pp. 214-243, 303-310.
Bell, Tim, "Longest Match String Searching for Ziv-Lempel Compression," Submitted to Workshop on Algorithms and Data Structures, Carleton University, Canada, 1989.
Bell, Timothy, "A Unifying Theory and Improvements for Existing Approaches to Text Compression," doctoral dissertation, University of Canterbury, Christchurch, New Zealand, 1986.
Bell, Timothy, "Better OPM/L Text Compression," IEEE Transactions on Communications, vol. 34, No. 12, Dec. 1986, pp. 1176-1182.
Bell, Timothy, et al., "Modeling for Text Compression," ACM Computing Surveys, vol. 21, No. 4, Dec. 1989, pp. 557-591.
Brent, R. P., "A Linear Algorithm for Data Compression," The Australian Computer Journal, vol. 19, No. 2 May 1987, pp. 64-68.
Chambers, Lloyd, "Fast Data Compressor With Direct Lookup Table Indexing Into History Buffer," Software Source Code Appendix, Salient Software, Inc., 1991, pp. A1-A10.
Cleary, John G., and Witten, Ian H., "Data Compression Using Adaptive Coding and Partial String Matching," IEEE Transactions on Communications, vol. 32, No. 4, Apr. 1984, pp. 396-402.
Fiala, Edward R., and Greene, Daniel H., "Data Compression With Finite Windows," Communications of the ACM, vol. 32, No. 4, Apr. 1989, pp. 490-505.
Fiala, Edward R., Greene, Daniel H., "CompressImpl.mesa" and CompressImpl4KUF.mesa, Xerox Corp., 1984, pp. 1-18.
Horspool, R. Nigel, and Cormack, Gordon V., "A General-Purpose Data Compression Technique With Practical Computer Applications," CIPS Session 84, 1984, pp. 138-141.
Lempel, Abraham, and Ziv, Jacob, "On the Complexity of Finite Sequences," IEEE Transactions on Information Theory, vol. 22, No. 1, Jan. 1976, p. 75-81.
Storer, James A., and Szymanski, Thomas G., "The Macro Model for Data Compression," Tenth Annual ACM Symposium on Theory of Computer, 1978, pp. 30-39.
Welch, Terry A., "A Technique for High-Performance Data Compression," Computer, Jun. 1984, pp. 8-19.
Ziv, Jacob, "Coding Theorems for Individual Sequences," IEEE Transactions on Information Theory, vol. 24, No. 4, Jul. 1978, pp. 405-412.
Witten, Ian H., et al., "Compress and Compact Discussed Further," Communications of the ACM, Technical Correspondence, vol. 31, No. 9, Sep, 1988, pp. 1139-1140, 1145.
Ziv, Jacob, "On Universal Quantization," IEEE Transactions on Information Theory, vol. 31, No. 3, May 1985, pp. 344-347.
Ziv, Jacob, and Lempel, Abraham, "A Universal Algorithm for Sequential Data Compression," IEEE Transactions on Information Theory, vol. 23, No. 3, May 1977, pp. 337-343.
Rashid Richard F.
Slivka Benjamin W.
Microsoft Corporation
Young Brian K.
LandOfFree
Method and system for data compression 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 system for data compression, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for data compression will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-1080010