Coded data generation or conversion – Digital code to digital code converters – Adaptive coding
Patent
1994-12-06
1996-04-09
Hoff, Marc S.
Coded data generation or conversion
Digital code to digital code converters
Adaptive coding
341 67, 341106, H03M 730
Patent
active
055065805
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: 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: 3656178 (1972-04-01), De Maine et al.
patent: 3675211 (1972-07-01), Raviv
patent: 3675212 (1972-07-01), Raviv et al.
patent: 3694813 (1972-09-01), Loh et al.
patent: 3701108 (1972-10-01), Loh et al.
patent: 3717851 (1973-02-01), Cocke 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: 4730348 (1988-03-01), MacCrisken
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: 4906991 (1990-03-01), Fiala et al.
patent: 4910751 (1990-03-01), Einarsson
patent: 5058144 (1991-10-01), Fiala et al.
English translation of German Patent No. 26 25 527.
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.
Davidson, 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., "Dat Compression by Textual Substitution Some Implementation Schemes and Results," Technical Report CS-83-113, Brandeis Unviersity, 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).
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.
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 Address
George Glen A.
Ivey Glen E.
Whiting Douglas L.
Hoff Marc S.
Stac Electronics, 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-141814