Coded data generation or conversion – Digital code to digital code converters – Adaptive coding
Patent
1992-05-01
1994-10-04
Young, Brian K.
Coded data generation or conversion
Digital code to digital code converters
Adaptive coding
341 87, H03M 730
Patent
active
053530241
ABSTRACT:
The present invention is a data compression method having an improved encoding algorithm which utilizes a token stacking technique. The essential step of the present invention encoding method is constructing a group of stacked tokens. Each stacked token has multiple fields including a substring length counter field and a backward displacement pointer field, where the former is identical among all stacked tokens for serving as the basis in constructing the group of stacked tokens, and the latter is assigned with a respective range of integers. The ranges assigned to the stacked tokens are stacked sequentially without overlapping. The encoding method further comprises the steps of determining a backward displacement pointer for a compressible substring and encoding the backward displacement pointer into a respective stacked token according to the range assigned, such that the backward displacement pointer falls within the range assigned to the respective stacked token. The present invention encoding method is particularly effective in saving the number of bytes required for encoding compressible substrings which are remotely located from their respective previously processed identical substrings because the larger backward displacement pointer can be encoded in a stacked token assigned with a stacked and shifted range of backward displacement pointers.
REFERENCES:
patent: 3914586 (1975-10-01), McIntosh
patent: 3976844 (1976-08-01), Betz
patent: 4021782 (1977-05-01), Hoerning
patent: 4054951 (1977-10-01), Jackson et al.
patent: 4087788 (1978-05-01), Johannesson
patent: 4295124 (1981-10-01), Roybal
patent: 4412306 (1983-10-01), Moll
patent: 4464650 (1984-08-01), Eastman et al.
patent: 4491934 (1985-01-01), Heinz
patent: 4538240 (1985-08-01), Carter et al.
patent: 4558302 (1985-12-01), Welch
patent: 4560976 (1985-12-01), Finn
patent: 4586027 (1986-04-01), Tsukiyama et al.
patent: 4588985 (1986-05-01), Carter et al.
patent: 4612532 (1986-09-01), Bacon et al.
patent: 4677649 (1987-06-01), Kunishi et al.
patent: 4682150 (1987-07-01), Mathes et al.
patent: 4701745 (1987-10-01), Waterworth
patent: 4730348 (1988-03-01), MacCrisken
patent: 4758899 (1988-07-01), Tsukiyama
patent: 4809350 (1989-02-01), Shimoni et al.
patent: 4814746 (1989-03-01), Miller et al.
patent: 4853696 (1989-08-01), Mukherjee
patent: 4872009 (1989-10-01), Tsukiyama et al.
patent: 4876541 (1989-10-01), Storer
patent: 4906991 (1990-03-01), Fiala et al.
patent: 4929946 (1990-05-01), O'Brien et al.
patent: 4949302 (1990-08-01), Arnold et al.
patent: 4979039 (1990-12-01), Kisor et al.
patent: 4988998 (1991-01-01), O'Brien
patent: 5003307 (1991-03-01), Whiting et al.
patent: 5010553 (1991-04-01), Scheller 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: 5132992 (1992-07-01), Yurt et al.
J. Cleary et al., "Date Compression Using Adaptive Coding and Partial String Matching", IEEE Transactions on Communications, 32:396-403 (1984).
M. Wells, "File Compression Using Variable Length Encodings", The Computer Journal, 15:308-313 (1972).
R. P. Brent, "A Linear Algorithm for Data Compression", The Australian Computer Journal, 19(2):64-67 (1987).
J. Ziv and A. Lempel, "A Universal Algorithm for Sequential Data Compression", IEEE Transactions on Information Theory, IT-23(3):337-343 (1977).
T. C. Bell, "Better OPM/L Text Compression", IEEE Transactions on Communicatons, CCOM-34(12):1176-1182 (1986).
D. W. Jones, "Application of Splay Trees to Data Compression", Communications of the ACM, 31(8):996-1007 (1988).
E. R. Fiala and D. H. Greene, "Data Compression with Finite Windows", Communications of the ACM, 32(4):490-505 (1989).
E. Goto et al., "Parallel Hashing Algorithms", Information Processing Letters, 6(1):8-13 (1977).
E. M. McCreight, "A Space-Economical Suffix Tree Construction Algorithm", Journal of the ACM, 23(2):262-272 (1976).
T. A. Welch, "A Technique for High Performance Data Compression", IEEE Computer, 8-19 (Jun. 1984).
M. Rodeh et al., "Linear Algorithm for Data Compression via String Matching", Journal of the ACM, 28(1):16-24 (1981).
V. S. Miller and M. N. Wegman, "Variations on a Theme by Ziv and Lempel" Conference Record-International Conference on Communications, (IEEE Service Center, Cat. No. 88CH2538-7) 390-394 (1984).
M. E. Gonzalez-Smith and J. A. Storer, "Parallel Algorithms for Data Compression", Journal of the Assoc. for Computing Machinery, 32(2):344-373 (1985).
Storer, J. A., Data Compression: Methods and Theory, Computer Sciente Press (1988).
Nelson, M., The Data Compression Book, M & T Books (1992).
Storer, J. A. and Reif, J. H. (ed.), Data Compression Conference 1991, IEEE Computer Society Press (1991).
Knuth, D. E., Sorting and Searching, The Art of Computer Programming, Chapter 6.4, vol. 3, pp. 506-542, Addison Wesley Publishing Co. (1973).
Holloman, D. R., "Technique for Relocatable Chains" IBM Technical Disclosure Bulletin, 14(2):449-451, Jul. 1971.
Intersecting Concepts, Inc.
Young Brian K.
LandOfFree
Method for data compression having an improved encoding algorith 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 for data compression having an improved encoding algorith, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for data compression having an improved encoding algorith will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-584316