Data Compression

PREV section

REFERENCES

Abramson, N. 1963. Information Theory and Coding. McGraw-Hill, New York.

Apostolico, A. and Fraenkel, A. S. 1985. Robust Transmission of Unbounded Strings Using Fibonacci Representations. Tech. Rep. CS85-14, Dept. of Appl. Math., The Weizmann Institute of Science, Rehovot, Sept.

ARC File Archive Utility. 1986. Version 5.1. System Enhancement Associates. Wayne, N. J.

Ash, R. B. 1965. Information Theory. Interscience Publishers, New York.

Bentley, J. L., Sleator, D. D., Tarjan, R. E., and Wei, V. K. 1986. A Locally Adaptive Data Compression Scheme. Commun. ACM 29, 4 (Apr.), 320-330.

Bobrow, L. S., and Hakimi, S. L. 1969. Graph Theoretic Prefix Codes and Their Synchronizing Properties. Inform. Contr. 15, 1 (July), 70-94.

Brent, R., and Kung, H. T. 1978. Fast Algorithms for Manipulating Formal Power Series. J. ACM 25, 4 (Oct.), 581-595.

Capocelli, R. M., Giancarlo, R., and Taneja, I. J. 1986. Bounds on the Redundancy of Huffman Codes. IEEE Trans. Infor. Theory 32, 6 (Nov.), 854-857.

Cappellini, V., Ed. 1985. Data Compression and Error Control Techniques with Applications. Academic Press, London.

Connell, J. B. 1973. A Huffman-Shannon-Fano Code. Proc. IEEE 61, 7 (July), 1046-1047.

Cormack, G. V. 1985. Data Compression on a Database System. Commun. ACM 28, 12 (Dec.), 1336-1342.

Cormack, G. V., and Horspool, R. N. 1984. Algorithms for Adaptive Huffman Codes. Inform. Process. Lett. 18, 3 (Mar.), 159-165.

Cortesi, D. 1982. An Effective Text-Compression Algorithm. BYTE 7, 1 (Jan.), 397-403.

Cot, N. 1977. Characterization and Design of Optimal Prefix Codes. Ph. D. dissertation, Computer Science Dept., Stanford Univ., Stanford, Calif.

Elias, P. 1975. Universal Codeword Sets and Representations of the Integers. IEEE Trans. Inform. Theory 21, 2 (Mar.), 194-203.

Elias, P. 1987. Interval and Recency Rank Source Coding: Two On-Line Adaptive Variable-Length Schemes. IEEE Trans. Inform. Theory 33, 1 (Jan.), 3-10.

Faller, N. 1973. An Adaptive System for Data Compression. Record of the 7th Asilomar Conf. on Circuits, Systems and Computers (Pacific Grove, Ca., Nov.), 593-597.

Fano, R. M. 1949. Transmission of Information. M.~I.~T. Press, Cambridge, Mass.

Fraenkel, A. S. and Klein, S. T. 1985. Robust Universal Complete Codes As Alternatives to Huffman Codes. Tech. Report CS85-16, Dept. of Appl. Math., The Weizmann Institute of Science, Rehovot, Oct.

Fraenkel, A. S., Mor, M., and Perl, Y. 1983. Is Text Compression by Prefixes and Suffixes Practical? Acta Inf. 20, 4 (Dec.), 371-375.

Gallager, R. G. 1968. Information Theory and Reliable Communication, Wiley, New York.

Gallager, R. G. 1978. Variations on a Theme by Huffman. IEEE Trans. Inform. Theory 24, 6 (Nov.), 668-674.

Garey, M. R. 1974. Optimal Binary Search Trees with Restricted Maximal Depth. SIAM J. Comput. 3, 2 (June), 101-110.

Gilbert, E. N. 1971. Codes Based on Inaccurate Source Probabilities. IEEE Trans. Inform. Theory 17, 3, (May), 304-314.

Gilbert, E. N., and Moore, E. F. 1959. Variable-Length Binary Encodings. Bell System Tech. J. 38, 4 (July), 933-967.

Glassey, C. R., and Karp, R. M. 1976. On the Optimality of Huffman Trees. SIAM J. Appl. Math 31, 2 (Sept.), 368-378.

Gonzalez, R. C., and Wintz, P. 1977. Digital Image Processing. Addison-Wesley, Reading, Mass.

Hahn, B. 1974. A New Technique for Compression and Storage of Data. Commun. ACM 17, 8 (Aug.), 434-436.

Hester, J. H., and Hirschberg, D. S. 1985. Self-Organizing Linear Search. ACM Comput. Surv. 17, 3 (Sept.), 295-311.

Horspool, R. N. and Cormack, G. V. 1987. A Locally Adaptive Data Compression Scheme. Commun. ACM 16, 2 (Sept.), 792-794.

Hu, T. C., and Tan, K. C. 1972. Path Length of Binary Search Trees. SIAM J. Appl. Math 22, 2 (Mar.), 225-234.

Hu, T. C., and Tucker, A. C. 1971. Optimal Computer Search Trees and Variable-Length Alphabetic Codes. SIAM J. Appl. Math 21, 4 (Dec.), 514-532.

Huffman, D. A. 1952. A Method for the Construction of Minimum-Redundancy Codes. Proc. IRE 40, 9 (Sept.), 1098-1101.

Ingels, F. M. 1971. Information and Coding Theory. Intext, Scranton, Penn.

Itai, A. 1976. Optimal Alphabetic Trees. SIAM J. Comput. 5, 1 (Mar.), 9-18.

Karp, R. M. 1961. Minimum Redundancy Coding for the Discrete Noiseless Channel. IRE Trans. Inform. Theory 7, 1 (Jan.), 27-38.

Knuth, D. E. 1971. Optimum Binary Search Trees. Acta Inf. 1, 1 (Jan.), 14-25.

Knuth, D. E. 1985. Dynamic Huffman Coding. J. Algorithms 6, 2 (June), 163-180.

Krause, R. M. 1962. Channels Which Transmit Letters of Unequal Duration. Inform. Contr. 5, 1 (Mar.), 13-24.

Laeser, R. P., McLaughlin, W. I., and Wolff, D. M. 1986. Engineering Voyager 2's Encounter with Uranus Scientific American 255, 5 (Nov.), 36-45.

Langdon, G. G., and Rissanen, J. J. 1983. A Double-Adaptive File Compression Algorithm. IEEE Trans. Comm. 31, 11 (Nov.), 1253-1255.

Llewellyn, J. A. 1987. Data Compression for a Source with Markov Characteristics. Computer J. 30, 2, 149-156.

McIntyre, D. R., and Pechura, M. A. 1985. Data Compression Using Static Huffman Code-Decode Tables. Commun. ACM 28, 6 (June), 612-616.

Mehlhorn, K. 1980. An Efficient Algorithm for Constructing Nearly Optimal Prefix Codes. IEEE Trans. Inform. Theory 26, 5 (Sept.), 513-517.

Neumann, P. G. 1962. Efficient Error-Limiting Variable-Length Codes. IRE Trans. Inform. Theory 8, 4 (July), 292-304.

Parker, D. S. 1980. Conditions for the Optimality of the Huffman Algorithm. SIAM J. Comput. 9, 3 (Aug.), 470-489.

Pasco, R. 1976. Source Coding Algorithms for Fast Data Compression. Ph. D. dissertation, Dept. of Electrical Engineering, Stanford Univ., Stanford, Calif.

Pechura, M. 1982. File Archival Techniques Using Data Compression. Commun. ACM 25, 9 (Sept.), 605-609.

Perl, Y., Garey, M. R., and Even, S. 1975. Efficient Generation of Optimal Prefix Code: Equiprobable Words Using Unequal Cost Letters. J. ACM 22, 2 (Apr.), 202-214.

PKARC FAST! File Archival Utility. 1987. Version 3.5. PKWARE, Inc. Glendale, WI.

Reghbati, H. K. 1981. An Overview of Data Compression Techniques. Computer 14, 4 (Apr.), 71-75.

Rissanen, J. J. 1976. Generalized Kraft Inequality and Arithmetic Coding. IBM J. Res. Dev. 20 (May), 198-203.

Rissanen, J. J. 1983. A Universal Data Compression System. IEEE Trans. Inform. Theory 29, 5 (Sept.), 656-664.

Rodeh, M., Pratt, V. R., and Even, S. 1981. A Linear Algorithm for Data Compression via String Matching. J. ACM 28, 1 (Jan.), 16-24.

Rubin, F. 1976. Experiments in Text File Compression. Commun. ACM 19, 11 (Nov.), 617-623.

Rubin, F. 1979. Arithmetic Stream Coding Using Fixed Precision Registers. IEEE Trans. Inform. Theory 25, 6 (Nov.), 672-675.

Rudner, B. 1971. Construction of Minimum-Redundancy Codes with Optimal Synchronizing Property. IEEE Trans. Inform. Theory 17, 4 (July), 478-487.

Ruth, S. S., and Kreutzer, P. J. 1972. Data Compression for Large Business Files. Datamation 18, 9 (Sept.), 62-66.

Ryabko, B. Y. 1987. A Locally Adaptive Data Compression Scheme. Commun. ACM 16, 2 (Sept.), 792.

Samet, H. 1984. The Quadtree and Related Hierarchical Data Structures. ACM Comput. Surv. 16, 2 (June), 187-260.

Schwartz, E. S. 1964. An Optimum Encoding with Minimum Longest Code and Total Number of Digits. Inform. Contr. 7, 1 (Mar.), 37-44.

Schwartz, E. S., and Kallick, B. 1964. Generating a Canonical Prefix Encoding. Commun. ACM 7, 3 (Mar.), 166-169.

Severance, D. G. 1983. A Practitioner's Guide to Data Base Compression. Inform. Systems 8, 1, 51-62.

Shannon, C. E., and Weaver, W. 1949. The Mathematical Theory of Communication. University of Illinois Press, Urbana, Ill.

Snyderman, M., and Hunt, B. 1970. The Myriad Virtues of Text Compaction. Datamation 16, 12 (Dec.), 36-40.

Standish, T. A. 1980. Data Structure Techniques. Addison-Wesley, Reading, Mass.

Stiffler, J. J. 1971. Theory of Synchronous Communications. Prentice-Hall, Englewood Cliffs, N. J.

Storer, J. A., and Szymanski, T. G. 1982. Data Compression via Textual Substitution. J. ACM 29, 4 (Oct.), 928-951.

Tanaka, H. 1987. Data Structure of Huffman Codes and Its Application to Efficient Encoding and Decoding. IEEE Trans. Inform. Theory 33, 1 (Jan.), 154-156.

Tropper, R. 1982. Binary-Coded Text, A Text-Compression Method. BYTE 7, 4 (Apr.), 398-413.

UNIX User's Manual. 1984. 4.2. Berkeley Software Distribution, Virtual VAX-11 Version, University of California, Berkeley.

Varn, B. 1971. Optimal Variable Length Codes (Arbitrary Symbol Cost and Equal Code Word Probability). Inform. Contr. 19, 4 (Nov.), 289-301.

Vitter, J. S. 1987. Design and Analysis of Dynamic Huffman Codes. J. ACM 34, 4 (Oct.), 825-845.

Wagner, R. A. 1973. Common Phrases and Minimum-Space Text Storage. Commun. ACM 16, 3 (Mar.), 148-152.

Welch, T. A. 1984. A Technique for High-Performance Data Compression. Computer 17, 6 (June), 8-19.

Wilkins, L. C., and Wintz, P. A. 1971. Bibliography on Data Compression, Picture Properties and Picture Coding. IEEE Trans. Inform. Theory 17, 2, 180-197.

Witten, I. H., Neal, R. M., and Cleary, J. G. 1987. Arithmetic Coding for Data Compression. Commun. ACM 30, 6 (June), 520-540.

Zimmerman, S. 1959. An Optimal Search Procedure. Amer. Math. Monthly 66, (Oct.), 690-693.

Ziv, J., and Lempel, A. 1977. A Universal Algorithm for Sequential Data Compression. IEEE Trans. Inform. Theory 23, 3 (May), 337-343.

Ziv, J., and Lempel, A. 1978. Compression of Individual Sequences via Variable-Rate Coding. IEEE Trans. Inform. Theory 24, 5 (Sept.), 530-536.

PREV section