Up: My home page
Next: Introduction

The Redundancy of the Ziv-Lempel Algorithm for Memoryless Sources

Yuri M. Shtarkov\ - Tjalling J. Tjalkens

Symposium on Information Theory in the Benelux
Oct 25--26, 1990

Abstract:

We discuss the redundancy of the Ziv-Lempel universal source coding algorithm. We consider this algorithm as a variable-to-fixed coding scheme and analyze its redundancy for memoryless sources as a function of the codeword length L. We show that, at least for some sources, the redundancy decreases not faster than , whereas the optimal rate of decrease is of .

This gives a partial, and negative, answer to the question for what classes of sources the Ziv-Lempel algorithm achieves an asymptotically optimal rate of decrease or the redundancy.

• Introduction
• The Ma version of the Ziv-Lempel algorithm
• The redundancy of VB coding schemes
• Computing the average message length
• The behavior of the redundancy
• Conclusion
• References