On the average redundancy rate of the Lempel-Ziv code

In this paper, we settle a long-standing open problem concerning the average redundancy r(n) of the Lempel-Ziv'78 (LZ78) code, We prove that for a memoryless source the average redundancy rate attains asymptotically Er-n=(A+delta(n))/log N+ O(log log n/log(2) n), where A is an explicitly given constant that depends on source characteristics, and delta(x) is a fluctuating function with a small amplitude, We also derive the leading term for the kth moment of the number of phrases, We conclude by conjecturing a precise formula on the expected redundancy for a Markovian source, The main result of this paper is a consequence of recently obtained second-order properties of the Lempel-Ziv algorithm by Jacquet and Szpankowski, These findings have been established by analytical techniques of the precise analysis of algorithms, We give a brief survey of these results since they are interesting in their own right, and shed some light on the probabilistic behavior of pattern matching based data compression.