From: Alex Vinokur
Subject: Re: huffman code length
Date: Thu, 10 Jun 1999 08:31:01 GMT
Newsgroups: comp.compression,alt.comp.compression,sci.crypt,sci.math
Keywords: worst-case code set for a Huffman code generator
In article ,
Tom Lane wrote:
> mclarke@nospam.pizza.demon.co.uk (M Clarke) writes:
> > Namely what is the maximum possible code size for any given data
set..
> > (in this case the number of unique symbols is 256 and the data set
> > will typically be many thousands of bytes)
>
> It's theoretically possible for a Huffman code generator to
> produce the worst-case code set wherein the k'th symbol has
> code length k,
> 0
> 10
> 110
> 1110
> ...
> 111111111111111111...10
> This happens when the k'th symbol has probability 2^-k.
>
[snip]
For more details about worst-case code see
the message titled "Huffman codes and Fibonacci numbers"
in comp.compression
http://www.deja.com/getdoc.xp?AN=471802979&fmt=text
Alex
>
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.