Coded data generation or conversion – Digital code to digital code converters – Adaptive coding
Patent
1992-02-28
1995-04-11
Young, Brian K.
Coded data generation or conversion
Digital code to digital code converters
Adaptive coding
341106, H03M 730
Patent
active
054062780
ABSTRACT:
A method and apparatus for digital data compression having an improved matching algorithm which utilizes a parallel hashing technique. The matching algorithm of the present invention data compression method can (a) perform a first hash computation on data string subblocks of N bytes and save the hash table value; (b) perform a second hash computation on a data string subblock of N+1 bytes by using the hash result from (a) which is hashed on the data string subblocks of N bytes; (c) perform a first hash matching on data string subblocks of N+1 bytes; and (d) when the first hash matching on the data string subblock of N+1 bytes found no match, perform a second subsequent parallel hash matching on data string subblocks of N bytes.
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 (1985-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: 4899147 (1990-02-01), Schiavo et al.
patent: 4906991 (1990-03-01), Fiala et al.
patent: 4929946 (1990-05-01), O'Brien 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: 5049881 (1991-09-01), Gibson et al.
patent: 5132992 (1992-07-01), Yurt et al.
Storer, J. A., Data Compression: Methods and Theory, Computer Science 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).
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).
J. Cleary et al., "Data 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 Communications, CCOM-34(12):1176-1182 (1986).
D. W. Jones, "Application of Splay Trees to Data Compression", Communications of the ACM, 31(8):996-1007.
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).
Gibson Dean K.
Graybill Mark D.
Intersecting Concepts, Inc.
Young Brian K.
LandOfFree
Method and apparatus for data compression having an improved mat 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 apparatus for data compression having an improved mat, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for data compression having an improved mat will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-1541681