Application of splay trees to data compression

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Application of splay trees to data compression

Full text

Pdf (1.22 MB)

Source

Communications of the ACM archive
Volume 31 , Issue 8 (August 1988) table of contents

Pages: 996 - 1007

Year of Publication: 1988

ISSN:0001-0782

Author

D. W. Jones

Dept. of Computer Science, University of Iowa, Iowa City, IA

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 18, Downloads (12 Months): 81, Citation Count: 8

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/63030.63036 What is a DOI?

ABSTRACT

The splay-prefix algorithm is one of the simplest and fastest adaptive data compression algorithms based on the use of a prefix code. The data structures used in the splay-prefix algorithm can also be applied to arithmetic data compression. Applications of these algorithms to encryption and image processing are suggested.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Jon Louis Bentley , Daniel D. Sleator , Robert E. Tarjan , Victor K. Wei, A locally adaptive data compression scheme, Communications of the ACM, v.29 n.4, p.320-330, April 1986 [doi>10.1145/5684.5688]
	2	Robert G. Gallager, Information Theory and Reliable Communication, John Wiley & Sons, Inc., New York, NY, 1968
	3	Gallager, R.G. Variations on a theme by Huffman. IEEE Trans. Inform. Theory IT-24, 6 (Nov. 1978), 668-674.
	4	Douglas W. Jones, An empirical comparison of priority-queue and event-set implementations, Communications of the ACM, v.29 n.4, p.300-311, April 1986 [doi>10.1145/5684.5686]
	5	Donald E. Knuth, Dynamic Huffman coding, Journal of Algorithms, v.6 n.2, p.163-180, June 1985 [doi>10.1016/0196-6774(85)90036-7]
	6	Rubin, F. Arithmetic stream coding using fixed precision registers. IEEE Trans. Inform. Theory IT-25, 6 (Nov. 1979), 672-675.
	7	Saraswat, V. Merge trees using splaying--or how to splay in parallel and bottom-up. PROLOG Digest 5, 22 (Mar. 27, 1987).
	8	Daniel Dominic Sleator , Robert Endre Tarjan, Self-adjusting binary trees, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.235-245, December 1983 [doi>10.1145/800061.808752]
	9	Daniel Dominic Sleator , Robert Endre Tarjan, Self-adjusting binary search trees, Journal of the ACM (JACM), v.32 n.3, p.652-686, July 1985 [doi>10.1145/3828.3835]
	10	Vitter, J.S. Two papers on dynamic Huffman codes. Tech. Rep. CS- 85-13. Brown University Computer Science, Providence, R.I. Revised Dec. 1986.
	11	Welch, T.A. A technique for high-performance data compression. IEEE Comput. 17, 6 (June 1984), 8-19.
	12	Ian H. Witten , Radford M. Neal , John G. Cleary, Arithmetic coding for data compression, Communications of the ACM, v.30 n.6, p.520-540, June 1987 [doi>10.1145/214762.214771]

CITED BY 8

	Timothy Bell , Ian H. Witten , John G. Cleary, Modeling for text compression, ACM Computing Surveys (CSUR), v.21 n.4, p.557-591, Dec. 1989
	Dennis Grinberg , Sivaramakrishnan Rajagopalan , Ramarathnam Venkatesan , Victor K. Wei, Splay trees for data compression, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.522-530, January 22-24, 1995, San Francisco, California, United States
	James J. Hunt , Kiem-Phong Vo , Walter F. Tichy, Delta algorithms: an empirical analysis, ACM Transactions on Software Engineering and Methodology (TOSEM), v.7 n.2, p.192-214, April 1998
	Alistair Moffat , Radford M. Neal , Ian H. Witten, Arithmetic coding revisited, ACM Transactions on Information Systems (TOIS), v.16 n.3, p.256-294, July 1998
	Clark D. Thomborson , Belle W.-Y. Wei, Systolic implementations of a move-to-front text compressor, ACM SIGARCH Computer Architecture News, v.19 n.1, p.53-60, March 1991
	Mark A. Roth , Scott J. Van Horn, Database compression, ACM SIGMOD Record, v.22 n.3, p.31-39, Sept. 1993
	C. D. Thomborson , B. W.-Y. Wei, Systolic implementations of a move-to-front text compressor, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.283-290, June 18-21, 1989, Santa Fe, New Mexico, United States
	Christos Strydis , Georgi N. Gaydadjiev, Profiling of lossless-compression algorithms for a novel biomedical-implant architecture, Proceedings of the 6th IEEE/ACM/IFIP international conference on Hardware/Software codesign and system synthesis, October 19-24, 2008, Atlanta, GA, USA