A fast algorithm for optimal length-limited Huffman codes

DOI10.1145/79147.79150zbMATH Open0699.68070OpenAlexW2021302562WikidataQ127769903 ScholiaQ127769903MaRDI QIDQ3477965FDOQ3477965

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

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

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)

Cited In (24)

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

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)