On the pointwise redundancy of the LZ78 algorithm
En‐hui Yang, Lihua Song, Gil I. Shamir, John C. Kieffer · 2005
The redundancy rate of the Lempel-Ziv algorithm has been widely investigated. Much of the data compression community believed that the redundancy rate of the LZ78 algorithm should be O((log n)-1), where n is the data length. However, until the present paper, this conjecture had not been proved for sources beyond Markov sources. In this paper, we investigate the upper bound on the pointwise redundancy rate of the Lempel-Ziv algorithm for mixing sources and finite-state sources. The technique we applied in this paper is simple. By studying the dictionary tree resulting from the LZ78 algorithm, we derive certain relationships between the self-information of a sequence emitted by a source and the number of phrases resulting from the LZ78 parsing of the sequence. From these relationships, upper bounds on the pointwise redundancy rate of the LZ78 algorithm on mixing sources and finite-state sources can be obtained. These results show that for mixing sources and finite-state sources, the pointwise redundancy rate is upper bounded by O((log n)-1) for the LZ78 algorithm. We also compare our results with previous results of Savari and Kieffer-Yang