Dynamic Shannon coding

DOI10.1016/J.IPL.2006.09.015MaRDI QIDQ845979zbMATHOpenAlexFDO

Authors Travis Gagie

Publication date 29 January 2010

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cs/0503085

zbMATH Keywords

data compressionon-line algorithms

Mathematics Subject Classification ID

Source coding (94A29)

Abstract: 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.

Recommendations

• Algorithms – ESA 2004
• Design and analysis of dynamic Huffman codes
• A fast algorithm for adaptive prefix coding
• Algorithm 673
• Dynamic huffman coding

Cites work

• scientific article; zbMATH DE number 2086237 (Why is no real title available?)
• scientific article; zbMATH DE number 3162350 (Why is no real title available?)
• scientific article; zbMATH DE number 3476581 (Why is no real title available?)
• A Mathematical Theory of Communication
• A Method for the Construction of Minimum-Redundancy Codes
• A dynamic programming algorithm for constructing optimal prefix-free codes with unequal letter costs
• A fast and efficient nearly-optimal adaptive Fano coding scheme
• Algorithms – ESA 2004
• An analysis of the Burrows-Wheeler transform
• An optimum encoding with minimum longest code and total number of digits
• Bounding the Compression Loss of the FGK Algorithm
• Channels which transmit letters of unequal duration
• Design and analysis of dynamic Huffman codes
• Dynamic Asymmetric Communication
• Dynamic huffman coding
• Generalized Kraft Inequality and Arithmetic Coding
• Huffman codes and self-information
• Huffman coding with unequal letter costs
• Optimal Prefix-Free Codes for Unequal Letter Costs: Dynamic Programming with the Monge Property
• Sorting and Searching in Multisets
• The sound of silence: Guessing games for saving energy in a mobile environment
• Variations on a theme by Huffman

Cited in

(4)

• Minimax trees in linear time with applications
• Algorithms – ESA 2004
• Dynamic Re-Encoding During MDD Minimization
• Worst-Case Optimal Adaptive Prefix Coding

This page was built for publication: Dynamic Shannon coding

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q845979)