On the average redundancy rate of the Lempel-Ziv code (Q4336280)

The redundancy of a noiseless code measures how far the code is from optimal for a given information source. Since the Lempel-Ziv codes have become virtually standard in practical lossless data compression, making an estimate of the redundancy of Lempel-Ziv codes is important. In this paper, the redundancy of the Lempel-Ziv'78 code for memoryless source is investigated. The authors proved that the average redundancy rate of encoding \(n\) letters of the source output is \[ Er_n= \bigl(A+ \delta(n) \bigr)/ \log n+ O(\log \log n/ \log^2n), \] where \(A\) is an explicitly given constant that depends on source characteristics, and \(\delta(x)\) is a fluctuating function with a small amplitude. To prove the main result, they compute the \(k\)th moment of number of phrases using the second-order properties of the Lempel-Ziv algorithm.