Meta-EAH: an adaptive encoder based on adaptive codes. Moving between adaptive mechanisms

ABSTRACT

Adaptive codes associate variable-length codewords to symbols being encoded depending on the previous symbols in the input data string. This class of codes has been introduced in [6] as a new class of non-standard variable-length codes. New algorithms for data compression, based on adaptive codes of order one and Huffman codes, have been presented in [7], where we have behaviorally shown that for a large class of input data strings, these algorithms substantially outperform the Lempel-Ziv universal data compression algorithm [12]. EAH has been introduced in [8], as an improved generalization of these algorithms. In this paper, we introduce Meta-EAH, an adaptive version of the EAH algorithm. Some comparisons between Meta-EAH and the Lempel-Ziv universal data compression algorithm are reported.

REFERENCES

• 1: Jean Berstel , Dominique Perrin, Theory of Codes, Academic Press, Inc., Orlando, FL, 1985
• 2: Mark Nelson , Jean-Loup Gailly, The data compression book (2nd ed.), MIS:Press, New York, NY, 1995
• 3: W. C. Huffman , Richard A. Brualdi , Vera S. Pless, Handbook of Coding Theory, Elsevier Science Inc., New York, NY, 1998
• 4: Grzegorz Rozenberg , Arto Salomaa, Handbook of Formal Languages, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 5: David Salomon, Data compression: the complete reference, Springer-Verlag New York, Inc., New York, NY, 1997
• 6: D. Trincă. Adaptive Codes: A New Class of Non-standard Variable-length Codes. (submitted to Romanian Journal of Information Science and Technology)
• 7: Dragos Trinca, Towards New Algorithms for Data Compression Using Adaptive Codes, Proceedings of the International Conference on Information Technology: Coding and Computing (ITCC'04) Volume 2, p.767, April 05-07, 2004
• 8: D. Trincă. EAH: An Encoder based on Adaptive Codes and Huffman Codes. (submitted to ISIT 2004, Chicago, Illinois, USA)
• 9: D. Trincă. Towards Combinatorial Translations of the EAH Data Compression Algorithm. (submitted to ICALP 2004, Turku, Finland)
• 10: F. L. Tiplea, E. Mäkinen, C. Enea. SE-Systems, Timing Mechanisms and Time-Varying Codes. International Journal of Computer Mathematics 79(10), 2002, 1083--1091.
• 11: Ferucio L. Tiplea , Erkki Mäkinen , Dragos Trincă , Costel Enea, Characterization results for time-varying codes, Fundamenta Informaticae, v.53 n.2, p.185-198, November 2002
• 12: J. Ziv, A. Lempel. Compression of individual sequences via variable-rate coding. IEEE Transactions on Information Theory, vol. IT-24, 1978, 530--536.

INDEX TERMS

Keywords:
adaptive codes, coding theory, data compression, prefix codes, variable-length codes