Universal variable-to-fixed length codes achieving optimum large deviations performance for empirical compression ratio

摘要

This paper clarifies two variable-to-fixed length codes whichachieve optimum large deviations performance of empirical compressionratio. One is Lempel-Zir code with fixed number of phrases, and theother is an arithmetic code with fixed codeword length. It is shownthat Lempel-Ziv code is asymtot- ically optimum in the above sense,for the class of finite-alphabet and finite-state source, and that hearithmetic code is asymp- totically optimum for the class offinite-alphabet unifilar sources.