A fast algorithm for adaptive prefix coding

DOI10.1007/S00453-007-9140-4MaRDI QIDQ2391182zbMATH OpenOpenAlexFDO

Authors Marek Karpinski, Yakov Nekrich

Publication date 24 July 2009

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-007-9140-4

zbMATH Keywords

adaptive codingdata compressionprefix-free codes

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Nonnumerical algorithms (68W05) Prefix, length-variable, comma-free codes (94A45)

Recommendations

• Fast adaptive coding algorithm
• Fast and Compact Prefix Codes
• Worst-Case Optimal Adaptive Prefix Coding
• A fast and efficient nearly-optimal adaptive Fano coding scheme
• Publication:4945375
• Efficient and Compact Representations of Prefix Codes
• scientific article; zbMATH DE number 3930882
• Efficient method of adaptive arithmetic coding for sources with large alphabets
• Faster algorithm for designing optimal prefix-free codes with unequal letter costs
• A fast and space-economical algorithm for length-limited coding

Cites work

• A fast and efficient nearly-optimal adaptive Fano coding scheme
• A Mathematical Theory of Communication
• A Method for the Construction of Minimum-Redundancy Codes
• Algorithms – ESA 2004
• Bounding the Compression Loss of the FGK Algorithm
• Combinatorial Merging
• Data compression
• Design and analysis of dynamic Huffman codes
• Dynamic huffman coding
• Fusion trees can be implemented with AC^0 instructions only
• Generating a canonical prefix encoding
• New bounds on the redundancy of Huffman codes
• On-line adaptive canonical prefix coding with bounded compression loss
• Surpassing the information theoretic bound with fusion trees
• Variations on a theme by Huffman

Cited in

(8)

• Minimax trees in linear time with applications
• Space-efficient Huffman codes revisited
• Fast adaptive coding algorithm
• Worst-Case Optimal Adaptive Prefix Coding
• Fast and Compact Prefix Codes
• On-line adaptive canonical prefix coding with bounded compression loss
• Simple worst-case optimal adaptive prefix-free coding
• Dynamic Shannon coding

This page was built for publication: A fast algorithm for adaptive prefix coding

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