Universal Variable-to-Fixed Length Codes Achieving Optimum Large Deviations Performance for Empirical Compression Ratio
Tomohiko Uyematsu · 1999
This paper clarifies two variable-to-fixed length codes which achieve optimum large deviations performance of empirical compression ratio. One is Lempel-Ziv code with fixed number of phrases, and the other is an arithmetic code with fixed codeword length. It is shown that Lempel-Ziv code is asymptotically optimum in the above sense, for the class of finite-alphabet and finite-state sources, and that the arithmetic code is asymptotically optimum for the class of finite-alphabet unifilar sources. key words: source coding, variable-to-fixed length code, empirical compression rate, finite state source 1. Introduction Comparisons between lossless variable-to-fixed (V-F) length codes and fixed-to-variable (F-V) length codes have been done by many researchers. Especially, Ziv [1] has shown that for Markovian sources with long memory there exists a V-F length code that provides a better compression ratio than any F-V length code with the same number of codewords. Tjal