A locally adaptive data compression scheme

ABSTRACT

A data compression scheme that exploits locality of reference, such as occurs when words are used frequently over short intervals and then fall into long periods of disuse, is described. The scheme is based on a simple heuristic for self-organizing sequential search and on variable-length encodings of integers. We prove that it never performs much worse than Huffman coding and can perform substantially better; experiments on real files show that its performance is usually quite close to that of Huffman coding. Our scheme has many implementation advantages: it is simple, allows fast encoding and decoding, and requires only one pass over the data to be compressed (static Huffman coding takes two passes).

REFERENCES

• 1: Bentlev. 1. L.. and McGeoch. C. A. Worst-case analvsis of self-oreanizing sequential search heuristics. In Proceedings 20th AIlerton Conference on Communication, Control, and Computing. (Monticello, Ill., Oct. 6-8, 1982). Univ. of Illinois, 452461.
• 2: Bentley, J. L., Sleator. D. D.. Tarjan, R. E., and Wei, V. K. A locality adaptive data compression scheme. In Proceedings 22nd AIlerton Conference on Communication, Control, and Computing. (Monticello, Ill., Oct. 3-5, 1984), Univ. of Illinois, 233-242.
• 3: Bentley, J. L., and Yao, A. C. An almost optima1 algorithm for unbounded searching. Inform. Process. Left, 5, 3 (Aug. 1976), 82-87.
• 4: Bitner, J. R. Heuristics that dynamically organize data structures. SZAM J Comput. 8, 1 (Feb. 1979), 82-110.
• 5: Brown, M. R.. and Tarjan. R. E. Design and analysis of a data structure for representing sorted lists. SIAM 1. Comput. 9, 3 (Aug. 1980), 594-614.
• 6: Edsger Wybe Dijkstra, A Discipline of Programming, Prentice Hall PTR, Upper Saddle River, NJ, 1997
• 7: Elias, P. University codeword sets and representation of the integers. IEEE Trans. Inform. Theory IT-21, 2 (Mar. 1975), 194-203.
• 8: Peter Elias, Interval and recency rank source coding: two on-line adaptive variable-length schemes, IEEE Transactions on Information Theory, v.33 n.1, p.3-10, January 2, 1987 [doi>10.1109/TIT.1987.1057251]
• 9: Robert G. Gallager, Information Theory and Reliable Communication, John Wiley & Sons, Inc., New York, NY, 1968
• 10: Gallager, R. G. Variations on a theme by Hoffman. IEEE Trans. Inform. Theory IT-24, 5 (Nov. 1978), 668-674.
• 11: Hardy, G. H., Littlewood, J. E., and Polya, G. Inequalities. Cambridge Univ. Press, Cambridge, England. 1967.
• 12: Huddleston, S. An efficient scheme for fast local updates in linear lists. Univ. of California, Irvine. 1981.
• 13: Huddleston, S., and Meblhorn, K. .4 new data structure for representing sorted lists. Acta Inform. 17. 2 (June 19821, 157-184.
• 14: Hoffman. D. A. A motbod for the c:onstruction of minimum radondancy codes. In Proceedings of fhe IRE 40, (Sept. 1952), 1098-1101.
• 15: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 16: 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]
• 17: S. Rao Kosaraju, Localized search in sorted lists, Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.62-69, May 11-13, 1981, Milwaukee, Wisconsin, United States [doi>10.1145/800076.802458]
• 18: Maier. D., and Salveter, S. C. Hysterical B-trees. Inform. Processing Left. 12, 4 (Aug. 13, 1981), 199-202.
• 19: 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]
• 20: Daniel Dominic Sleator , Robert Endre Tarjan, Amortized efficiency of list update rules, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.488-492, December 1984 [doi>10.1145/800057.808718]
• 21: Daniel D. Sleator , Robert E. Tarjan, Amortized efficiency of list update and paging rules, Communications of the ACM, v.28 n.2, p.202-208, Feb. 1985 [doi>10.1145/2786.2793]
• 22: 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]
• 23: Robert Endre Tarjan, Data structures and network algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983
• 24: Athanasios K. Tsakalidis, AVL-Trees for Localized Search, Proceedings of the 11th Colloquium on Automata, Languages and Programming, p.473-485, July 16-20, 1984
• 25: Vitter. J. S. Design and analysis of dynamic Hoffman coding. In Proceedings of the Twenty-Sixth Annual IEEE Symposium on Foundations of Computer Science. (Portland, Oreg., Oct. 21-23, 1985), IEEE Computer Society, 293-302.
• 26: Ziv, J., and Lempel, A. Compression of individual sequences via variable-rate coding. IEEE Trans. Inform. Theory IT-24, 5 (Sept. 1978), 530-536.

INDEX TERMS

Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Lists, stacks, and queues
  E.4 CODING AND INFORMATION THEORY
      Subjects: Data compaction and compression

General Terms:
Algorithms, Experimentation, Measurement, Performance, Theory