An Efficient Implementation of Adaptive Prefix Coding

The goal of the prefix coding is to assign codewords to elements of the input alphabet A, so that no codeword is a prefix of another one, and the total length of the encoded message S is minimized. In the case of static prefix coding, symbol frequencies are known in advance. In the case of adaptive (or dynamic) prefix coding, every symbol S_i is encoded before the next symbol S_i+1 is read.