Subject: Re: max. huffman code length?

From: [email-masked]
Date: Sun, 25 DEC 94 21:40:18 -0500

Ulrich Graef <[email-masked]> writes:
 
>>   is there any way to calculate the maximal codelength one will get with
>>   dynamic huffman? (2^16 characters of 8 bit)
>
>Which data and which dynamic Huffman method (See my last post!)?
>
>If you use the first bit to decide whether to code  or to copy the data,
>you can limit the size of the code to 
>
>		2^16 * 8 + 1
 
The Huffman method is somewhat related to the minimum description length
(MDL) and minimum message length (MML) methods which is why I am joining in.
I have been searching for specific detailed examples of how to code
these methods in a spreadsheet.  Thanks in advance for any advice you
may have.  Harry Edwards   [email-masked]

---

From: [email-masked] (Ulrich Graef)
Date: 27 Dec 1994 17:28:42 GMT

> may have.  Harry Edwards   [email-masked]

I think, the methods to generate Huffmann code with dynamic adaption to the
message source are not easy to program in a spreadsheet.
This is because you have to build a Huffman tree to be able to generate
your binary Huffman prefix-code _and_ you must update the tree in periodic
intervals to adapt (dynamically) to the probabilies in your message source.
This is hard to program with good performance,
even if you have a programming language like C or Pascal.

I think the most spreadsheets do not contain features which you need including:

	- tree representation and manipulation.
	- iterative processing of data
		(to perform the coding process and the dynamic model update)

Does your spreadsheet allow this (without heavy add-ins)?
If yes, which one do you use?

If you want to use the spreadsheet anyway, you should consider arithmetic
coding. Especially when you only want to compute the minimal representation
length it would be very helpful. But the need to use iterative processing
of data does not disappear.

Greetings,

	Uli

--
Ulrich Graef       |  home:   06155 62493      int: +49 6155 62493      
Lichtenbergweg 11  |  office: 06103 752 364    int: +49 6103 752 359
D-64347 Griesheim  +-------------------------------------------------
Germany            |  e-mail: [email-masked]