Bounding the inefficiency of length-restricted prefix codes

DOI10.1007/S00453-001-0060-4MaRDI QIDQ5953598zbMATH OpenOpenAlexFDO

Authors Ruy L. Milidiú, Eduardo S. Laber

Publication date 10 June 2003

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-001-0060-4

zbMATH Keywords

redundancycompressionprefix codesHuffman treesapproximative algorithm

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 3910298
• Efficient and Compact Representations of Prefix Codes
• Optimal Prefix Codes for Infinite Alphabets With Nonlinear Costs
• Some Tight Lower Bounds on the Redundancy of Optimal Binary Prefix-Free and Fix-Free Codes
• Algorithms and Data Structures
• On the ratio of prefix codes to all uniquely decodable codes with a given length distribution
• scientific article; zbMATH DE number 1512691
• On the Expected Codeword Length Per Symbol of Optimal Prefix Codes for Extended Sources
• More Efficient Algorithms and Analyses for Unequal Letter Cost Prefix-Free Coding
• More Efficient Algorithms and Analyses for Unequal Letter Cost Prefix-Free Coding

Cited in

(22)

• Three space-economical algorithms for calculating minimum-redundancy prefix codes
• On compressing permutations and adaptive sorting
• On the size of transducers for bidirectional decoding of prefix codes
• A note on the construction of error detecting/correcting prefix codes
• Algorithms and Data Structures
• Colored range queries and document retrieval
• Worst-Case Optimal Adaptive Prefix Coding
• A note on r-extensible prefix codes
• Parity codes
• On the ratio of prefix codes to all uniquely decodable codes with a given length distribution
• Exact and approximation algorithms for error-detecting even codes
• On the Expected Codeword Length Per Symbol of Optimal Prefix Codes for Extended Sources
• On the proportion of prefix codes in the set of three-element codes
• Existence of optimal prefix codes for infinite source alphabets
• scientific article; zbMATH DE number 1512691 (Why is no real title available?)
• Complexity aspects of guessing prefix codes
• On the cost of worst case coding length constraints
• On the redundancy of optimal binary prefix-condition codes for finite and infinite sources (Corresp.)
• Trading off worst and expected cost in decision tree problems
• Efficient and compact representations of some non-canonical prefix-free codes
• Efficient prefix coding of uncertainty spaces
• The WARM-UP algorithm: A Lagrangian construction of length restricted Huffman codes

This page was built for publication: Bounding the inefficiency of length-restricted prefix codes

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