Optimal prefix codes with fewer distinct codeword lengths are faster to construct

DOI10.1016/J.IC.2019.104436zbMATH Open1430.68096arXivcs/0509015OpenAlexW2963622137WikidataQ127441902 ScholiaQ127441902MaRDI QIDQ2272991FDOQ2272991

Authors: Ahmed A. Belal, Amr Elmasry 

Publication date: 17 September 2019

Published in: Information and Computation (Search for Journal in Brave)

Abstract: A new method for constructing minimum-redundancy binary prefix codes is described. Our method does not explicitly build a Huffman tree; instead it uses a property of optimal prefix codes to compute the codeword lengths corresponding to the input weights. Let $n$ be the number of weights and $k$ be the number of distinct codeword lengths as produced by the algorithm for the optimum codes. The running time of our algorithm is $O(kcdotn)$. Following our previous work in cite{be}, no algorithm can possibly construct optimal prefix codes in $o(kcdotn)$ time. When the given weights are presorted our algorithm performs $O(9^{k}cdotlo{g}^{2k}n)$ comparisons.

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

Recommendations

• Distribution-Sensitive Construction of Minimum-Redundancy Prefix Codes
• Efficient construction of minimum-redundancy codes for large alphabets
• Optimal prefix free codes with partial sorting
• In-place calculation of minimum-redundancy codes
• A fast algorithm for optimal length-limited Huffman codes

zbMATH Keywords

data structuresoutput-sensitiveHuffman treesmedian findingoptimal prefix codes

Mathematics Subject Classification ID

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

Cites Work

• A Method for the Construction of Minimum-Redundancy Codes
• An almost optimal algorithm for unbounded searching
• Design and analysis of dynamic Huffman codes
• Title not available (Why is that?)
• Variations on a theme by Huffman
• On the maximum length of Huffman codes
• Efficient construction of minimum-redundancy codes for large alphabets
• Verification of minimum-redundancy prefix codes
• Three space-economical algorithms for calculating minimum-redundancy prefix codes
• In-place calculation of minimum-redundancy codes
• Distribution-Sensitive Construction of Minimum-Redundancy Prefix Codes

Cited In (5)

• A fast algorithm for optimal length-limited Huffman codes
• Distribution-Sensitive Construction of Minimum-Redundancy Prefix Codes
• Fixed-prefix encoding of the integers can be Huffman-optimal
• Optimal prefix free codes with partial sorting
• Fast and Compact Prefix Codes

This page was built for publication: Optimal prefix codes with fewer distinct codeword lengths are faster to construct

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