A fast algorithm for optimal length-limited Huffman codes

DOI10.1145/79147.79150MaRDI QIDQ3477965zbMATH OpenOpenAlexWikidataFDO

Authors Lawrence L. Larmore, Daniel S. Hirschberg

Publication date 1990

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/79147.79150

zbMATH Keywords

databinary treeHuffman codingcoding and information theorycompaction and compression

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Prefix, length-variable, comma-free codes (94A45) Data structures (68P05)

Recommendations

• A fast and space-economical algorithm for length-limited coding
• A Fast Algorithm For Optimum Height-Limited Alphabetic Binary Trees
• In-place calculation of minimum-redundancy codes
• Bounding the depth of search trees
• Optimal prefix codes with fewer distinct codeword lengths are faster to construct

Cited in

(24)

• Generation of fast interpreters for Huffman compressed bytecode
• Optimal binary search trees
• Fixed-prefix encoding of the integers can be Huffman-optimal
• The WARM-UP algorithm: A Lagrangian construction of length restricted Huffman codes
• Generating Huffman sequences
• Exact and approximation algorithms for error-detecting even codes
• A Fast Algorithm For Optimum Height-Limited Alphabetic Binary Trees
• Optimal prefix codes with fewer distinct codeword lengths are faster to construct
• Exact and Experimental Algorithms for a Huffman-Based Error Detecting Code
• Is Huffmann coding dead?
• Solving sequential knapsack problems
• Decision trees for function evaluation: simultaneous optimization of worst and expected cost
• Trading off worst and expected cost in decision tree problems
• Space-efficient Huffman codes revisited
• scientific article; zbMATH DE number 3949708 (Why is no real title available?)
• An algorithm for generating Huffman sequences in lexicographic order
• Bounding the depth of search trees
• Distribution-Sensitive Construction of Minimum-Redundancy Prefix Codes
• Parity codes
• Correctness of constructing optimal alphabetic trees revisited
• A fast and space-economical algorithm for length-limited coding
• Shortest synchronizing strings for Huffman codes
• An application of the Hopfield model to Huffman codes
• Trees with exponentially growing costs

This page was built for publication: A fast algorithm for optimal length-limited Huffman codes

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