Coded data generation or conversion – Digital code to digital code converters – To or from variable length codes
Patent
1994-05-09
1995-05-09
Logan, Sharon D.
Coded data generation or conversion
Digital code to digital code converters
To or from variable length codes
341106, 341 95, H03M 742
Patent
active
054144256
ABSTRACT:
An apparatus and method are disclosed for converting an input data character stream into a variable length encoded data stream and encoding the variable length encoded date stream according to byte length. A 2 byte length is encoded by 2 bits having the values "00". Encoded lengths of 3 and 4 bytes are represented respectively by 2 bits having the values "01" and "10". Byte lengths of 5 to 7 are represented by 4 bits "1100" to "1110" and so on to thereby enable an efficient procedure for encoding the length of a bit string during compression.
REFERENCES:
patent: 3656178 (1972-04-01), De Maine 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: 3976844 (1976-08-01), Betz
patent: 3995254 (1976-11-01), Rosenbaum
patent: 4021782 (1977-05-01), Hoerning
patent: 4054951 (1977-10-01), Jackson et al.
patent: 4412306 (1983-10-01), Moll
patent: 4464650 (1984-08-01), Eastman et al.
patent: 4491934 (1985-01-01), Heinz
patent: 4494150 (1985-01-01), Brickman et al.
patent: 4558302 (1985-12-01), Welch
patent: 4612532 (1986-09-01), Bacon et al.
patent: 4701745 (1987-10-01), Waterworth
patent: 4730348 (1988-03-01), MacCrisken
patent: 4814746 (1989-03-01), Miller et al.
patent: 4876541 (1989-10-01), Storer
patent: 4906991 (1990-03-01), Fiala et al.
patent: 5003307 (1991-03-01), Whiting et al.
patent: 5016009 (1991-05-01), Whiting et al.
patent: 5058144 (1991-10-01), Fiala et al.
patent: 5126739 (1992-06-01), Whiting et al.
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 Unv., 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, pp. 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, Kyoto, pp. 807-809, 1978.
Kohonen, T. et al., "A Thousand-Word Recognition System Based on the Learning Subspace Method and Redundant Hash Addressing," Proc. 5th Int. Conf. on Pattern Recognition, Miami, pp. 158-165, 1980.
Lindsay, R. et al., "Universal Data Compression," International Telemetering Conference Proceedings, pp. 117-124, 1985.
Lynch, M., "Creation of Bibliographic Search Codes for Hash-addressing Using the Variety-Generator Method," Program, vol. 9, No. 2, pp. 46-55, 1975.
Miller, V. et al., "Variations on a Theme by Lempel and Ziv," IBM, 1982.
Munakata, S., "Ziv-Lempel Data Compression Algorithm," J. Information Processing Society of Japan, vol. 27, No. 1, pp. 2-6, Jan., 1985 (with translation).
Rabin, M., "Discovering Repetitions in Strings," Combinatorial Algorithms on Words, Apostolico and Galil eds. NATO ASI Series, vol. F12, pp. 279-288, 1985 (presented in Italy, Jun. 1984).
Reghbati, H. et al., "An Overview of Data Compression Techniques," Computer, vol. 14, No. 4, pp. 71-75, 1981.
Reuhkala, E., "Recognition of Strings of Discrete Symbols with Special Application to Isolated Word Recognition," ACTA Polytechnica Scandinavica Mathematics and Computer Science Series No. 38, pp. 1-92, 1983.
Reukhala, E., "Pattern Recognition for Strings of Discrete Symbols," Proc. 6th Int. Conf. on Pattern Recognition, Munich, pp. 969-972, 1982.
Rivest, R., "Partial-Match Retrieval Algorithms," Siam J. Computing, vol. 5, No. 1, pp. 19 et seq., 1976.
Rodeh, M., "String Matching Algorithms and Their Application to Data Compression," Thesis, Israel Institute of Technology, pp. i-40, 1976 (and translation).
Rodeh, M. et al., "A Linear Algorithm for Finding Repetitions and its Applications in Data Compression," Technicon--Israel Institute of Technology, Department of Computer Science, Haifa, Technical Report No. 72, pp. 1-32, 1976.
Ryan, D. et al., "Data Compression Experiments Using Sliding Dictionaries," Technical Report CS-84-117, Brandeis University, 1984.
Schuegraf, E., "A Survey of Data Compression Methods for Non-Numeric Records," Canadian Journal of Information Science, vol. 2, No. 1, pp. 93-105, 1977.
Schuegraf, E. et al., "A Comparison of Algorithms for Data Base Compression by Use of Fragments as Language Elements," ISR vol. 10, No. 9/10-B, pp. 309-319, 1974.
Sedgewick, R. "Algorithms" Addison-Wesley, 1984.
Severance, D., "Identifier Search Mechnisms: A Survey and Generalized Model," Computing Surveys, vol. 6, pp. 175-194, 1974.
Storer, J. et al., "The Macro Model for Data Compression," 1977.
Tharp, A. et al., "The Practicality of Text Signatures for Accelerating String Searching," Software--Practice and Experience, vol. 12, pp. 35-44, 1982.
Wagner, R., "Common Phrases and Minimum-Space Text Storage," Communications of the ACM 16(3): 148-152, 1973.
Waterworth Design Memo, "Some Notes on the Subject of File Compression, Issue 2.".
Waterworth source code.
Whiting, D., "Bit-Serial Reed-Solomon Decoders in VLSI," Thesis, California Institute of Technology, 1985.
Willett, P., "Document Retrieval Experiments Using Indexing Vocabularies of Varying Size. 11. Hashing, Truncation, Diagram and Trigram Encoding of Index Terms," Journal of Documentation, vol. 35, No. 4, pp. 296-305, 1979.
Wipke, W. et al., "Hash Functions for Rapid Storage and Retrieval of Chemical Structures," J. Chem. Inf. Comput. Sci. vol. 18, No. 1, pp. 32-37, 1978.
Wirth, "Algorithms+Data Structures=Programs," 1976.
Yamamoto, H. et al., "Improvement of Ziv-Lempel code and evaluation of efficiency by simulation (II)," Papers of Technical Group on Communication Systems, IECE, Japan, CS84-135 (Jan., 1985).
Zamora, A., "Automatic Detection and Correction of Spelling Errors in a Large Data Base.: Journal of the American Society for Information Science, pp. 51-57, 1980.
Bell, Timothy C., "Better OPM/L Text Compression," IEEE Transactions on Communications, vol. Com-34, No. 12, pp. 1176-1182, Dec., 1986.
Bell, Timothy, "A Unifying Theory and Improvements for Existing Approaches to Text Compression," Ph.D. Thesis, pp. 32-45, 81-86, 128-134, Department of Computer Science, University of Canterbury, 1986.
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.
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 Tran
George Glen A.
Ivey Glen E.
Whiting Douglas L.
Logan Sharon D.
Stac
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-1709105