Bounding the compression loss of the FGK algorithm

[Summary form only given]. For data communication purposes, the initial parsing required by the static Huffman algorithm represents a big disadvantage. This is because the data must be transmitted on-line. As soon as the symbol arrives at the transmitter, it must be encoded and transmitted to the receiver. In these situations, adaptive Huffman codes have been largely used. This method determines the mapping from symbol alphabet to codewords based upon a running estimate of the alphabet symbol weights. The code is adaptive, just changing to remain optimal for the current estimates. Two methods have been presented in the literature for implementing dynamic Huffman coding. The first one was the FGK algorithm (Knuth, 1985) and the second was the Λ algorithm (Vitter, 1987). Vitter proved that the total number of bits D _t transmitted by the FGK algorithm for a message with t symbols is bounded below by S_t-n+1, where S_t is the number of bits required by the static Huffman method and bounded above by 2S_t+t-4n+2. Furthermore, he conjectured that D_t is bounded above by S_t+O(t). We present an amortized analysis to prove this conjecture by showing that D_t⩽S _t+2t-2k-[log min(k+1,n)], where k is the number of distinct symbols in the message. We also present an example where D_t=S _t+2t-2k-3[(t-k)/k]-[log(k+1)], showing that the proposed bound is asymptotically tight. These results explain the good performance of FGK observed by some authors through practical experiments