An empirical evaluation of coding methods for multi-symbol alphabets

摘要

Many contemporary data compression schemes distinguish two distinct components: modelling and coding. Modelling involves estimating probabilities for the input symbols, while coding involves generating a sequence of bits in the output based on those probabilities. Several different methods for coding have been proposed. The best known are Huffman's code and the more recent technique of arithmetic coding, but other viable methods include various fixed codes, fast approximations to arithmetic coding, and splay coding. Each offers a different trade-off between compression speed, memory requirements, and the amount of compression obtained. This paper evaluates the performance of these methods in several situations and determines which is the most suitable for particular classes of application.