On the Construction of (Explicit) Khodak's Code and Its Analysis
Yann Bugeaud, Michael Drmota, Wojciech Szpankowski · IEEE Transactions on Information Theory · 2008
Variable-to-variable (VV) codes are very attractive yet not well understood data compression schemes. In 1972, Khodak claimed to provide upper and lower bounds for the achievable redundancy rate, however, he did not offer explicit construction of such codes. In this paper, we first present a constructive and transparent proof of Khodak's result showing that for memoryless sources there exists a code with the average redundancy bounded byD-5/3, whereDis the average delay (e.g., the average length of a dictionary entry). We also describe an algorithm that constructs a VV length code with a small redundancy rate for largeD. Then, we discuss several generalizations. We prove that the worst case redundancy does not exceedD-4/3. Furthermore, we provide similar upper bound for Markov sources (of order 1). Finally, we consider bounds that are valid foralmostallmemoryless and Markov sources for which the set of exceptional source parameters has zero measure. In particular, for all memoryless sources outside this exceptional class, we prove there exists a VV code with the average redundancy rate bounded byD-1-m/3+epsivand the worst case redundancy rate bounded byD-1-m/3+epsiv, wheremis the cardinality of the alphabet. We complete our analysis with a lower bound showing that for all VV codes the average and the worst case redundancy rates are at leastD-2m-1-epsivfor almost all memoryless sources in the sense that the set of exceptional source parameters has zero measure. We prove these results using techniques of Diophantine approximations.