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
> 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".
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.
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.
> 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.
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.
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. :
(
On Feb 9, 12:09 pm, Harry Potter <rose.josep...@yahoo.com> wrote:
> 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.
> 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.
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.
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.
