From: Alex Vinokur <alexander.vinokur@telrad.co.il>
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 <uo9vhcw3g0u.fsf@netcom2.netcom.com>,
  Tom Lane <tgl@netcom.com> 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.