Dynamic Shannon coding

DOI10.1016/J.IPL.2006.09.015zbMATH Open1189.94040arXivcs/0503085OpenAlexW2046831124MaRDI QIDQ845979FDOQ845979

Authors: Travis Gagie 

Publication date: 29 January 2010

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

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.

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

Recommendations

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

zbMATH Keywords

data compressionon-line algorithms

Mathematics Subject Classification ID

Source coding (94A29)

Cites Work

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

Cited In (4)

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

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)