Data compression using hashing

Details Data compression using hashing Data compression using hashing

1992-10-23

1994-12-06

Young, Brian K.

Coded data generation or conversion

Digital code to digital code converters

Adaptive coding

341 67, 341106, H03M 730

Patent

active

053714997

ABSTRACT:
Compressing a sequence of characters drawn from an alphabet uses string substitution with no a priori information. An input data block is processed into an output data block comprised of variable length incompressible data sections and variable length compressed token sections. Multiple hash tables are used based on different subblock sizes for string matching, and this improves the compression ratio and rate of compression. The plurality of uses of the multiple hash tables allows for selection of an appropriate compression data rate and/or compression factor in relation to the input data. Using multiple hashing tables with a recoverable hashing method further improves compression ratio and compression rate. Each incompressible data section contains means to distinguish it from compressed token sections.

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: 4899147 (1990-02-01), Schiavo
patent: 4906991 (1990-03-01), Fiala et al.
patent: 4929946 (1990-05-01), O'Brien et al.
patent: 4961139 (1990-10-01), Hong 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: 5032987 (1991-07-01), Broder et al.
patent: 5049881 (1991-09-01), Gibson et al.
patent: 5129074 (1992-07-01), Kikuchi et al.
patent: 5132992 (1992-07-01), Yurt et al.
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 (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 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).

Affiliated with

Also associated with

Rating

Data compression using hashing 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 using hashing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data compression using hashing will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-217433