Worst-Case Optimal Adaptive Prefix Coding

DOI10.1007/978-3-642-03367-4_28MaRDI QIDQ3183465zbMATH OpenOpenAlexFDO

Authors Travis Gagie, Yakov Nekrich

Publication date 20 October 2009

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Coding theorems (Shannon theory) (94A24) Prefix, length-variable, comma-free codes (94A45)

Abstract: A common complaint about adaptive prefix coding is that it is much slower than static prefix coding. Karpinski and Nekrich recently took an important step towards resolving this: they gave an adaptive Shannon coding algorithm that encodes each character in (O (1)) amortized time and decodes it in (O (log H)) amortized time, where $H$ is the empirical entropy of the input string $s$. For comparison, Gagie's adaptive Shannon coder and both Knuth's and Vitter's adaptive Huffman coders all use (Theta (H)) amortized time for each character. In this paper we give an adaptive Shannon coder that both encodes and decodes each character in (O (1)) worst-case time. As with both previous adaptive Shannon coders, we store $s$ in at most ((H + 1) |s| + o (|s|)) bits. We also show that this encoding length is worst-case optimal up to the lower order term.

Recommendations

• A fast algorithm for adaptive prefix coding
• Optimal Prefix Codes And Huffman Codes
• scientific article; zbMATH DE number 1543071
• On-line adaptive canonical prefix coding with bounded compression loss
• Bounding the inefficiency of length-restricted prefix codes
• Optimal Prefix Codes for Infinite Alphabets With Nonlinear Costs
• A fast and efficient nearly-optimal adaptive Fano coding scheme
• scientific article; zbMATH DE number 2036351
• On forward error correction with adaptive decoding (Corresp.)
• Efficient Adaptive Algorithms and Minimax Bounds for Zero-Delay Lossy Source Coding

Cites work

• A Mathematical Theory of Communication
• A Method for the Construction of Minimum-Redundancy Codes
• A fast algorithm for adaptive prefix coding
• Algorithms – ESA 2004
• Bounding the Compression Loss of the FGK Algorithm
• Channels which transmit letters of unequal duration
• Design and analysis of dynamic Huffman codes
• Dynamic Shannon coding
• Dynamic huffman coding
• Dynamic ordered sets with exponential search trees
• Fusion trees can be implemented with AC^0 instructions only
• Generating a canonical prefix encoding
• On-line adaptive canonical prefix coding with bounded compression loss
• Surpassing the information theoretic bound with fusion trees
• Tight bounds for online stable sorting
• Variations on a theme by Huffman

Cited in

(8)

• On-line adaptive canonical prefix coding with bounded compression loss
• Simple worst-case optimal adaptive prefix-free coding
• Algorithms – ESA 2004
• Efficient fully-compressed sequence representations
• Efficient and compact representations of some non-canonical prefix-free codes
• Tight bounds for online stable sorting
• A fast algorithm for adaptive prefix coding
• Minimax trees in linear time with applications

This page was built for publication: Worst-Case Optimal Adaptive Prefix Coding

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