On the average redundancy rate of the Lempel-Ziv code with k-error protocol

In this paper we examine the average redundancy rate of a Lempel-Ziv 78 code with the k-error protocol. Storer and Reif (1997) have studied this modification of the Lempel-Ziv scheme and shown that it provides an efficient protection against error propagation while preserving the asymptotic optimality of the code. We refine this result by providing an asymptotic expression for the average redundancy rate of this code for memoryless sources. We have established our result by exploiting a relationship between a parsing scheme of the Lempel-Ziv encoder with the k-error protocol and a generalization of the digital search tree structure, and by using analytical techniques of the analysis of algorithms. We accompany our analysis with a number of experiments that test the validity of our theoretical result and demonstrate the effects of various additional modifications of the Lempel-Ziv algorithm