Coded data generation or conversion – Digital code to digital code converters – To or from variable length codes
Patent
1990-11-27
1992-09-08
Logan, Sharon D.
Coded data generation or conversion
Digital code to digital code converters
To or from variable length codes
341106, 364DIG1, H03M 742, G06F 1200
Patent
active
051462214
ABSTRACT:
An apparatus and method are disclosed for converting an input data character stream into a variable length encoded data stream in a data compression system. The data compression system includes a history array. The history array has a plurality of entries and each entry of the history array is for storing a portion of the input data stream. The method for converting the input data character stream includes the following steps. Performing a search in a history array for the longest data string which matches the input data string. If the matching data string is found within the history buffer, the next step includes encoding the longest matching data string found by appending to the encoded data stream a tag indicating the longest matching data string was found and a string substitution code. If the matching data string is not found within the history array, the next step includes encoding the first character of the input data string by appending to the encoded data stream a raw data tag indicating that no matching data string was found and the first character of the input data string.
REFERENCES:
patent: 3914747 (1975-10-01), Barnes et al.
patent: 3976844 (1976-08-01), Betz
patent: 4021782 (1977-05-01), Hoerning
patent: 4054951 (1977-10-01), Jackson et al.
patent: 4412306 (1983-10-01), Moll
patent: 4464650 (1984-08-01), Eastman et al.
patent: 4491934 (1985-01-01), Heinz
patent: 4558302 (1985-12-01), Welch
patent: 4612532 (1986-09-01), Bacon et al.
patent: 4701745 (1987-10-01), Waterworth
patent: 4814746 (1989-03-01), Miller et al.
patent: 4835733 (1989-05-01), Powell
patent: 4876541 (1989-10-01), Storer
patent: 4906995 (1990-03-01), Swanson
patent: 5010513 (1991-04-01), Ueda
M. Cohn, "Performance of Lempel-Ziv Compressors with Deferred Innovation," Brandeis University, Technical Report TR-88-132, Apr. 1988.
S. Even and M. Rodeh, "Economical Encoding of Commas Between Strings," Communications of the ACM, vol. 21, No. 4, Apr., 1978, pp. 315-317.
J. K. Gallant, "String Compression Algorithms," Ph.D. Dissertation, Department of Electrical Engineering and Computer Science, Princeton University, 1982.
A. Hartman and M. Rodeh, "Optimal Parsing of Strings," Combinatorial Algorithms on Words, pp. 155-167 (1985).
G. Held, Data Compression: Techniques and Applications, Hardware and Software Considerations, (second edition 1987).
D. A. Huffman, "A Method for the Construction of Minimum-Redundancy Codes," Proceedings of the I.R.E., Sep., 1952, pp. 1098-1101.
D. W. Jones, "Application of Splay Trees To Data Compression," Communications of the ACM, vol. 31, No. 8, Aug., 1988, pp. 996-1007.
Knuth, Sorting and Searching: The Art of Computer Programming, pp. 506-549 (vol. 3, 1973).
G. G. Langdon, Jr., "A Note on the Ziv-Lempel Model for Compressing Individual Sequences," IEEE Transactions on Information Theory, vol. IT-29, No. 2, Mar. 1983, pp. 284-287.
A. Lempel, G. Seroussi and J. Ziv, "On the Power of Straight-Line Computations in Finite Fields," IEEE Transactions on Information Theory, vol. IT-28, No. 6, Nov., 1982, pp. 875-880.
A. Lempel and J. Ziv. "On the Complexity of Finite Sequences," IEEE Transactions on Information Theory, vol. IT-22, No. 1, Jan. 1976, pp.75-81.
A. Lempel and J. Ziv, "Compression of Two-Dimensional Data," IEEE Transactions on Information Theory, vol. IT-32, No. 1, Jan., 1986, pp. 2-8.
A. Lempel and J. Ziv, "Compression of Two-Dimensional Images," Combinatorial Algorithms on Words, pp. 141-154 (1985).
V. S. Miller and M. N. Wegman, "Variations on a Theme by Lempel and Ziv," Combinatorial Algorithms on Words, pp. 131-140 (1985).
M. Rodeh, V. R. Pratt, and S. Even, "Linear Algorithms for Data Compression via String Matching," Journal of the Association for Computing Machinery, vol. 28, No. 1, Jan., 1981, pp. 16-24.
J. A. Storer, Data Compression: Methods and Theory (1988).
J. A. Storer, "Data Compression: Method and Complexity Issues," Ph.D. Dissertation, Department of Electrical Engineering and Computer Science, Princeton University, 1979.
J. A. Storer, "Parallel Algorithms For On-Line Dynamic Data Compression," IEEE International Conference On Communications 1988, pp. 385-389.
J. A. Storer, "Textual Substitution Techniques for Data Compression," Combinatorial Algorithms on Words, pp. 111-129 (1985).
J. A. Storer and T. G. Szymanski, "Data Compression via Textual Substitution," Journal of the Association for Computing Machinery, vol. 29, No. 4, Oct., 1982, pp. 928-951.
J. A. Storer and T. G. Szymanski, "The Macro Model for Data Compression," (extended abstract), Tenth Annual ACM Symposium on Theory of Computing, pp. 30-39 (1978).
T. A. Welch, "A Technique for High-Performance Data Compression," IEEE Computer, Jun., 1984, pp. 8-19.
J. Ziv, "Coding Theorems for Individual Sequences," IEEE Transactions on Information Theory, vol. IT-24, No. 4, Jul., 1978, pp. 405-412.
J. Ziv, "On Universal Quantization," IEEE Transactions on Information Theory, vol. IT-31, No. 3, May, 1985, pp. 344-347.
J. Ziv and A. Lempel, "A Universal Algorithm for Sequential Data Compression," IEEE Transactions on Information Theory, vol. IT-23, No. 3, May, 1977, pp. 337-343.
J. Ziv and A. Lempel, "Compression of Individual Sequences Via Variable-Rate Coding," IEEE Transactions on Information Theory, vol. IT-24, No. 5, Sep., 1978, pp. 530-536.
J. G. Cleary and I. H. Witten, "Data Compression Using Adaptive Coding and Partial String Matching," IEEE Transactions on Communications, vol. 33, No. 4, Apr., 1984, pp. 396-403.
M. E. Gonzalez Smith and J. A. Storer, "Parallel Algorithms for Data Compression," Journal of the Association for Computing Machinery, vol. 32, No. 2, Apr., 1985, pp. 344-373.
M. Wells, "File Compression Using Variable Length Encodings," The Computer Journal, vol. 15, No. 4, Nov., 1972, pp. 308-313.
Mark Bianchi, Jeffrey J. Kato and David J. Van Maren, "Data Compression in a Half-Inch Reel-to-Reel Tape Drive" Hewlett-Packard Journal Jun. 1969.
Preliminary Product Specification, InfoChips Systems, Inc. IC-105 Compression Decompression Processor Hewlett-Packard Product Specification, "Magic Data Compression IC".
George Glen A.
Ivey Glen E.
Whiting Douglas L.
Logan Sharon D.
Stac, Inc.
LandOfFree
Data compression apparatus and method does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Data compression apparatus and method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data compression apparatus and method will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-136916