Predicting the size of a Huffman block?

[Harry Potter]

That's pretty much it: Given the number of occuring symbols and the
length of the file or data to be compressed, how do I estimate the
size of the output? I have to do this quickly on 8-bit, 16-bit and 32-
bit computers. I can work on predicting the size of the overhead
myself.
-------------------
Joseph Rose, a.k.a. Harry Potter
Working magic in the computer community

[Thomas Richter]

On 08.02.2012 15:18, Harry Potter wrote:
> That's pretty much it: Given the number of occuring symbols and the
> length of the file or data to be compressed, how do I estimate the
> size of the output? I have to do this quickly on 8-bit, 16-bit and 32-
> bit computers. I can work on predicting the size of the overhead
> myself.

What type of information do you have, and which type of answer would you
need? Do you have the Huffman code available? What do you know on the
statistics of the source? Do you need a worst-case or an average-case
answer? Is an estimate sufficient?

The general answer to your question, lacking any further information, is
just "no".

Greetings,
Thomas

[Earl_Colby_Pottinger]

On Feb 8, 10:55 am, Thomas Richter <t...@math.tu-berlin.de> wrote:

> The general answer to your question, lacking any further information, is
> just "no".

Given the number of occuring symbols AND frequency of those symbols
PLUS length of the file.

I believe it is possible to calculate the size of a STATIC HUFFMAN
table and the expected size of the resulting file.

For non-static you probably do almost as much work estimating the file
size as just doing the compression completely.

[Harry Potter]

On Feb 8, 10:55 am, Thomas Richter <t...@math.tu-berlin.de> wrote:

> What type of information do you have, and which type of answer would you
> need? Do you have the Huffman code available? What do you know on the
> statistics of the source? Do you need a worst-case or an average-case
> answer? Is an estimate sufficient?
>

* General information--I'll do more specific later
* I'm only starting the code--I don't have it yet
* The compressor can scan the source file or parts of it for the
statistics of the source befoe compression
* I need the best possible depending on user settings
* An estimation will do--and is in fact what I want.

[James Dow Allen]

On Feb 8, 9:18 pm, Harry Potter <rose.josep...@yahoo.com> wrote:
> Given the number of occuring symbols and the
> length of the file or data to be compressed, how do I estimate the
> size of the output?

Do you have the histogram [H1, H2, ... Hk] of tokens
to be coded? If so, the output size in bits is
given approximately by
T (0.03 + log T) - sum Hj log Hj
where T = sum Hj, and log is base 2.
0.03 is an estimate of the inefficiency (due to
discreteness) of Huffman coding.

Hope this helps.
James

[Thomas Richter]

On 09.02.2012 16:41, Harry Potter wrote:
> On Feb 8, 10:55 am, Thomas Richter<t...@math.tu-berlin.de> wrote:
>> What type of information do you have, and which type of answer would you
>> need? Do you have the Huffman code available? What do you know on the
>> statistics of the source? Do you need a worst-case or an average-case
>> answer? Is an estimate sufficient?
>>
> * General information--I'll do more specific later
> * I'm only starting the code--I don't have it yet
> * The compressor can scan the source file or parts of it for the
> statistics of the source befoe compression

Is a two-pass approach acceptable, i.e. determine the relative
frequencies first, design the optimal Huffman code, then encode?

> * I need the best possible depending on user settings
> * An estimation will do--and is in fact what I want.

If this is simple zero-order Huffman coder: Set p_i to the relative
frequency of symbol i. ceil(-log_2(p_i)) will give you the number of
bits the Huffman code will assign to the symbol. N \sum_i p_i *
ceil(-log_2(p_i)) will give you the compressed file size in bits, where
N is the number of symbols in the stream. Round up to the next byte,
done. Remember that you somehow also need to signal the Huffman code you
used, i.e. there is an overhead of side-channels not included in the
above computation.

Greetings,
Thomas

[Harry Potter]

On Feb 9, 11:56 am, Thomas Richter <t...@math.tu-berlin.de> wrote:
> Is a two-pass approach acceptable, i.e. determine the relative
> frequencies first, design the optimal Huffman code, then encode?
>

A two-pass approach is my plan.

> If this is simple zero-order Huffman coder: Set p_i to the relative
> frequency of symbol i. ceil(-log_2(p_i)) will give you the number of
> bits the Huffman code will assign to the symbol. N \sum_i p_i *
> ceil(-log_2(p_i)) will give you the compressed file size in bits, where
> N is the number of symbols in the stream. Round up to the next byte,
> done. Remember that you somehow also need to signal the Huffman code you
> used, i.e. there is an overhead of side-channels not included in the
> above computation.
>

I don't understand most of the above computations as I am limited to a
high-school math education. But logarithms are too complex to do on
an 8-bit computer with any semblance of speed.

[Harry Potter]

I should've mentioned: the figures I have are the size of the block to
compress, the values that occur and the number of occurences for each
value. However, I don't want to use the number of occurences in the
calculation as it would take too long. And as for the overhead, I
don't want to reveal how I'm going to do compression, so I'll have to
figure it out myself. Sorry about the rudeness--it wasn't intended. :
(

[Thomas Richter]

On 09.02.2012 18:09, Harry Potter wrote:

> I don't understand most of the above computations as I am limited to a
> high-school math education. But logarithms are too complex to do on
> an 8-bit computer with any semblance of speed.

Point 1) No, taking the log to the base of two is not a complex
operation. It is a matter of shifting and counting the shifts and is
trivial.

Point 2) Sorry, folks, but without mathematics no compression. The
problem can be solved by getting an education, and only by that. If
that's not your intention - deliver Pizza instead. Sorry to sound so
strict, but it is *really* that simple. As always, it is up to you to
fix it.

[Harry Potter]

On Feb 9, 2:45 pm, Thomas Richter <t...@math.tu-berlin.de> wrote:
> Point 1) No, taking the log to the base of two is not a complex
> operation. It is a matter of shifting and counting the shifts and is
> trivial.
>

I can do that.

> Point 2) Sorry, folks, but without mathematics no compression. The
> problem can be solved by getting an education, and only by that. If
> that's not your intention - deliver Pizza instead. Sorry to sound so
> strict, but it is *really* that simple. As always, it is up to you to
> fix it.

You're right. I think I have some ideas, though.

[Jim Leonard]

On Feb 9, 1:45 pm, Thomas Richter <t...@math.tu-berlin.de> wrote:
>
> Point 2) Sorry, folks, but without mathematics no compression. The
> problem can be solved by getting an education, and only by that. If
> that's not your intention - deliver Pizza instead. Sorry to sound so
> strict, but it is *really* that simple. As always, it is up to you to
> fix it.

For order-0/statistical and complex methods, absolutely. But I wrote
my own LZ77 compressor long before I understood what those were. My
math is also limited, but I've tried to make up for it with excessive
research.

I have entertained the idea of going back to college (ie. night school
or community college) to complete calculus and trigonometry. I have
been using many methods and formulas in my hobby work for over a
decade without fully understanding them. The proverbial "light bulb"
has not yet lit up yet.