Dynamic shannon coding
Travis Gagie · 2004
This paper presents a new algorithm, called dynamic Shannon coding, that uses at most (H + 1)m + O(nlogm) bits to encode string S. The key idea is to smooth the relative frequencies of characters when computing their weights. It also shows that dynamic Shannon coding can be easily modified to restrict the maximum length of any codeword in the encoding produced. The analysis of dynamic Shannon coding is much simpler than the analysis of dynamic Huffman coding.