The length of a typical Huffman codeword

DOI10.1109/18.335944MaRDI QIDQ4324194zbMATH OpenOpenAlexFDO

Authors R. Schack

Publication date 1 March 1995

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/adap-org/9303001

zbMATH Keywords

Huffman codelength of a typical codeword

Mathematics Subject Classification ID

Prefix, length-variable, comma-free codes (94A45)

Abstract: If p is the probability of a letter of a memoryless source, the length l of the corresponding binary Huffman codeword can be very different from the value -log p. We show that, nevertheless, for a typical letter, l is approximately equal to -log p. More precisely, the probability that l differs from -log p by more than m decreases exponentially with m.

Recommendations

• Maximal codeword lengths in Huffman codes
• The minimum codeword length and redundancy in the binary Huffman code for uncertain sources
• On the redundancy of binary Huffman codes (Corresp.)
• On the maximum length of Huffman codes
• On the competitive optimality of Huffman codes

Cited in

(4)

• An efficient decoding technique for Huffman codes
• Bernstein polynomials and learning theory
• Maximal codeword lengths in Huffman codes
• Algorithmic information and simplicity in statistical physics

This page was built for publication: The length of a typical Huffman codeword

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