Coded data generation or conversion – Digital code to digital code converters – To or from variable length codes
Patent
1995-07-07
1996-07-02
Young, Brian K.
Coded data generation or conversion
Digital code to digital code converters
To or from variable length codes
H03M 740
Patent
active
055326943
ABSTRACT:
An apparatus and method for converting an input data character stream into a variable length encoded data stream in a data compression system. A sliding window data compression algorithm is combined with Huffman encoding on the strings and raw bytes. The Huffman table, in a compressed form, is prepended to the encoded output data. The Huffman codes representing the shortest strings encode both the string length and part of the string offset. Assigning Huffman codes to represent the combined length and offset allows the use of a smaller sliding window size without sacrificing compression ratio. The smaller window size allows implementations in software and hardware to minimize memory usage, thus reducing cost.
REFERENCES:
patent: 3054987 (1962-09-01), Lawrence et al.
patent: 3344406 (1967-09-01), Vinal
patent: 3390380 (1968-06-01), Cooke-Yarborough et al.
patent: 3394352 (1968-07-01), Wernikoff et al.
patent: 3396352 (1968-08-01), Wilson
patent: 3612660 (1971-10-01), Miller
patent: 3675211 (1972-07-01), Raviv
patent: 3675212 (1972-07-01), Raviv et al.
patent: 3726993 (1973-04-01), Lavallee
patent: 3767901 (1973-10-01), Black et al.
patent: 3873977 (1975-03-01), McIntosh
patent: 3970183 (1976-07-01), Robinson et al.
patent: 3976844 (1976-08-01), Betz
patent: 3995254 (1976-11-01), Rosenbaum
patent: 4021782 (1977-05-01), Hoerning
patent: 4031515 (1977-06-01), Kashio
patent: 4034350 (1977-07-01), Kashio
patent: 4054951 (1977-10-01), Jackson et al.
patent: 4064489 (1977-12-01), Babb
patent: 4121259 (1978-10-01), Preuss et al.
patent: 4135214 (1979-01-01), Weber
patent: 4145686 (1979-03-01), McMurray et al.
patent: 4207599 (1980-06-01), Murayama et al.
patent: 4232375 (1980-11-01), Paugstat et al.
patent: 4290105 (1981-09-01), Cichelli et al.
patent: 4295124 (1981-10-01), Roybal
patent: 4319225 (1982-03-01), Klose
patent: 4376933 (1983-03-01), Saran et al.
patent: 4382286 (1983-05-01), Mitchell et al.
patent: 4386416 (1983-05-01), Giltner et al.
patent: 4412306 (1983-10-01), Moll
patent: 4464650 (1984-08-01), Eastman et al.
patent: 4486853 (1984-12-01), Parsons
patent: 4491934 (1985-01-01), Heinz
patent: 4494150 (1985-01-01), Brickman et al.
patent: 4494151 (1985-01-01), Liao
patent: 4506325 (1985-03-01), Bennett et al.
patent: 4507752 (1985-03-01), McKenna et al.
patent: 4516246 (1985-05-01), Kenemuth
patent: 4543612 (1985-09-01), Matsunaga et al.
patent: 4545032 (1985-10-01), Mak
patent: 4546342 (1985-10-01), Weaver et al.
patent: 4558302 (1985-12-01), Welch
patent: 4597057 (1986-06-01), Snow
patent: 4610027 (1986-09-01), Anderson et al.
patent: 4612532 (1986-09-01), Bacon et al.
patent: 4626824 (1986-12-01), Larson
patent: 4626829 (1986-12-01), Hauck
patent: 4684923 (1987-08-01), Koga
patent: 4701108 (1987-10-01), Scampini
patent: 4701745 (1987-10-01), Waterworth
patent: 4706264 (1987-11-01), Cung
patent: 4749983 (1988-06-01), Langdon, Jr.
patent: 4774500 (1988-09-01), Lichty
patent: 4783841 (1988-11-01), Crayson
patent: 4796003 (1989-01-01), Bentley et al.
patent: 4814746 (1989-03-01), Miller et al.
patent: 4839649 (1989-06-01), Imai et al.
patent: 4847619 (1989-07-01), Kato et al.
patent: 4857993 (1989-08-01), Music et al.
patent: 4862167 (1989-08-01), Copeland, III
patent: 4866440 (1989-09-01), Tsukiyama et al.
patent: 4870415 (1989-09-01), Van Maren et al.
patent: 4870479 (1989-09-01), Dubner
patent: 4872009 (1989-10-01), Tsukiyama et al.
patent: 4876541 (1989-10-01), Storer
patent: 4881075 (1989-11-01), Weng
patent: 4882754 (1989-11-01), Weaver et al.
patent: 4891643 (1990-01-01), Mitchell et al.
patent: 4899147 (1990-02-01), Schiavo et al.
patent: 4899148 (1990-02-01), Sato et al.
patent: 4910751 (1990-03-01), Einarsson
patent: 5003307 (1991-03-01), Whiting et al.
patent: 5049881 (1991-09-01), Gibson et al.
patent: 5051745 (1991-09-01), Katz
patent: 5058144 (1991-10-01), Fiala et al.
patent: 5155484 (1992-10-01), Chambers, IV
patent: 5339076 (1994-08-01), Jiang
Bar-Ness et al. "String Dictionary Structure for Markov Arithmetic Encoding," IEEE International Conference on Communications, vol. 1, Jun. 1988, New York, pp. 395-399.
English translation of German Patent No. 26 25 527, 1978.
Berkovich, S. et al., "Matching String Patterns in Large Textual Files," Department of Electrical Engineering and Computer Science, George Washington Univ., pp. 122-127, 1985.
Boyer, R., "A Fast String Searching Algorithm", Communications of the ACM 20(10), 762-772, 1977.
Cleary, J., "Compact Hash Tables Using Bidirectional Linear Probing"; IEEE Transactions on Computers c-33(9): 828-834, 1984.
Collmeyer, A. et al., "Analysis of Retrieval Performance for Selected File Organization Techniques," Proc. Fall Joint Comp. Conf., pp. 201-210, 1970.
Comer, D., "English Dictionary Searching with Little Extra Space," National Computer Conference, pp. 209-216, 1979.
Comer, D. et al. "Hash-Bucket Search: A Fast Technique for Searching an English Spelling Dictionary," Software--Practice and Experience, vol. 12, pp. 669-682, 1982.
Cowan, R. et al. "Hashing--The Key to Rapid Pattern Matching," Proceedings, Eurosam, lecture Notes in Computer Science 72, Springer-Verlag, Marsaille, pp. 266-278, 1979.
Davison, G., "Rapidly Searching for Character String Matches Using Hash Coding," IBM Technical Disclosure Bulletin, vol. 16, No. 1, p. 64, 1973.
Davisson, L. et al., "Efficient Universal Noiseless Source Codes," IEEE Transactions on Information Theory, vol. IT-27, No. 3, pp. 269-279, 1981.
Dewan, H. et al., "Data Compression by Textual Substitution Some Implementation Schemes and Results," Technical Report CS-83-113, Brandeis University, 1983.
Dimsdale, J. et al., "File Structure for an On-Line Catalog of One Million Titles," Journal of library Automation, vol. 6, No. 1, pp. 37-55, 1973.
Ellzey, R., "Data Structures for Computer Information Systems,"Science Research Associates, 1982.
Fiala, E. et al. "Data Compression with Finite Windows," Communications of the ACM 32(4): 490-505, Apr., 1989.
Floyd, R., "Application of Data Compression Techniques on Computer-Based Text and Program Source Libraries," Thesis, College of Engineering, Florida Atlantic University, 1977.
Floyd, R., "Data Base Compression through Combined Software Techniques," IBM Technical Disclosure Bulletin, vol. 21, No. 2, pp. 458-462, 1978.
Gallant, J., "Optimal String Compression" EECS Department, Princeton Univ., pp. 1-10. (No Date Given by Applicant).
Goble, C., "A Free-text Retrieval System using Hash Codes," The Computer Journal, vol. 18, pp. 18-20, 1975.
Goto, E., et al., "Studies on Hashing Part-2: Algorithms and Programming with CAMs," Journal of Information Processing, vol. 3, No. 1, pp. 13-22, 1980.
Harrison, M., "Implementation of the Substring Test by Hashing," Communications of the ACM 14(12): 777-779, 1971
Heaps, H., "Data Compression of Large Document Data Bases," Journal of Chemical Information and Computer Sciences, vol. 15, No. 1, pp. 32-39, 1975.
Heaps, H., "Information Retrieval: Computational and Theoretical Aspects," Academic Press, Introduction, Chapter 5 and Chapter 9, 1978.
Hegazy, "Searching Large Textual Files for Near Matching Patterns," The George Washington Univ., 1985.
Hopgood, "Compiling Techniques," American Elsevier Publishing Company, Inc., pp. 1-28, 1969.
Horowitz and Sahni, "Fundamentals of Data Structures in Pascal," (2d ed.) 1987.
Horowitz and Sahni, "Fundamentals of Data Structures in Pascal," (4th ed.) W. H. Freeman and Company, pp. 425-457, 1990.
Kara, T., "Recent Advances in Data Compression Theory," J. of Japan Electronic Communications Society, vol. 67, No. 3, pp. 288-292 (1984).
Karp, R., et al., "Efficient Randomized Pattern-Matching Algorithms," Harvard Univ. Center for Research in Computing Technology, pp. 1-39, 1981.
Knuth, D., "Algorithms," Scientific American, Apr., 1977, p. 63 et. seq.
Kohonen, T. "Content Addressable Memories," Spring Series in Information Sciences, vol. 1, pp. 1-124 and 253-263, 1980.
Kohonen, T., et al., "A Very Fast Associative Method for the Recognition and Correction of Misspelt Words, Based on Redundant Hash Addressing," Proc. 4th Int. Joint Conf. on Pattern Recognition, Kyo
Mayers Clay
Whiting Douglas L.
Stac Electronics, Inc.
Young Brian K.
LandOfFree
Data compression apparatus and method using matching string sear 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 using matching string sear, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data compression apparatus and method using matching string sear will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-1510044