Author : D. W. Jones Authors Info & Claims
Pages 996 - 1007 Published : 01 August 1988 Publication History 66 citation 1,936 Downloads Total Citations 66 Total Downloads 1,936 Last 12 Months 116 Last 6 weeks 11 Get Citation AlertsThis alert has been successfully added and will be sent to: You will be notified whenever a record that you have chosen has been cited.
To manage your alert preferences, click on the button below. Manage my AlertsThe 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.
Bentley, J.L., Sleator, D. D., Tarjan, R. g., and Wei, V. K. A locally adaptive data compression scheme. Commun. ACM 29, 4 (Apr. 1986), 320-330.
Gallager, R.G. Information Theory and Reliable Communication. John Wiley & Sons, New York, 1968.Gallager, R.G. Variations on a theme by Huffman. IEEE Trans. Inform. Theory IT-24, 6 (Nov. 1978), 668-674.
Jones, D.W. An empirical comparison of priority queue and event set implementations. Commun. ACM 29, 4 (Apr. 1986), 300-311.
Knuth, D.E. Dynamic Huffman coding. J. Algorithms 6, 2 (Feb. 1985), 163-180.Rubin, F. Arithmetic stream coding using fixed precision registers. IEEE Trans. Inform. Theory IT-25, 6 (Nov. 1979), 672-675.
Saraswat, V. Merge trees using splaying--or how to splay in parallel and bottom-up. PROLOG Digest 5, 22 (Mar. 27, 1987).
Sleator, D.D., and Tarjan, R.E. Self-adjusting binary trees. In Proceedings of the ACM SIGACT Symposium on Theory of Computing (Boston, Mass., Apr. 25-27). ACM, New York, 1983, pp. 235-245.
Tarjan, R.E., and Sleator, D.D. Self-adjusting binary search trees. J. ACM 32, 3 (July 1985), 652-686.
Vitter, J.S. Two papers on dynamic Huffman codes. Tech. Rep. CS- 85-13. Brown University Computer Science, Providence, R.I. Revised Dec. 1986.
Welch, T.A. A technique for high-performance data compression. IEEE Comput. 17, 6 (June 1984), 8-19.Witten, I.H., Neal, R.M., and Cleary, J.G. Arithmetic coding for data compression. Commun. ACM 30, 6 (June 1987), 520-540.
We give a new lemma (dynamic reweighing) about splay trees and we define a class of dynamically self-adjusted trees (parametrically balanced) wide enough to include BB(α), AVL, rank-balanced and B-trees. Using our lemma we prove that splay trees are .
The suffix tree is a fundamental data structure in the area of string algorithms and it has been used in many applications including data compression. In this paper we propose a data structure called the truncated suffix tree, which is a truncated .
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Association for Computing Machinery
New York, NY, United States
