2005/03/30 by Travis Gagie, Gagie, Travis
Computer Science · Mathematics · #E.4 #FOS: Computer and information sciences #Information Theory (cs.IT) #cs.IT #math.IT
paper · pdf · doi:10.48550/arxiv.cs/0503085
6 pages; conference version presented at ESA 2004; journal version submitted to IEEE Transactions on Information Theory
arxiv created 2005/03/30 · arxiv updated 2009/12/01
We present a new algorithm for dynamic prefix-free coding, based on Shannon coding. We give a simple analysis and prove a better upper bound on the length of the encoding produced than the corresponding bound for dynamic Huffman coding. We show how our algorithm can be modified for efficient length-restricted coding, alphabetic coding and coding with unequal letter costs.