Re: Best existing binary compressor method?

biject schrieb:

Actually you over looked one thing. If you have an I.I.d. you would
tend to compress
close to the entopy. But its a statistical thing. Some strings of ABC
will compress
right on some will be smaller some longer?

It's a statistical statement I'm making, not an absolute one. Given the
statistics described as above, then the *expected* number of bits per
sample will approach the entropy in the limit of infinite input streams
on average.

if you use arithmetic
cmpression you
get closer than huffman to the entropy on average.

That is correct, but only due to the limitation of huffman not
being able assign symbols a fractional number of bits. IOW, as long as
the probabilities of the source alphabet are inverse powers of two, there
is no difference between huffman and arithmetic in the limit.

But in either case
some will
compress smaller than the entropy and some longer. That is assuming
you do a
proper bijective style of entropy compression.

"Bijective" is completely irrelevant for this topic. There is absolutely
nothing in the proof that requires this.

So long,
Thomas
.

Relevant Pages

  • Re: Best existing binary compressor method?
    ... biject schrieb: ... get closer than huffman to the entropy on average. ... but only due to the limitation of huffman not ... compress to the entropy limit if your not compressing bijectively ...
    (comp.compression)
  • Data vs: Information (was: A unique number for every "person" - can it be done?)
    ... >> entropy have less information than systems with low entropy (though ... >> amount of data (10 coins), but one is much more ordered. ... > compress the random text significantly. ... > engine, and if you burned them carefully enough, the engine powered by ...
    (sci.crypt)
  • Re: Choose a default prefix code for a generic stream
    ... biject wrote: ... I need a way to generate a prefix code in a very light way. ... compress smaller ... input blocks Xblockc Xblockc Xblockc ...
    (comp.compression)
  • Re: Best existing binary compressor method?
    ... get closer than huffman to the entropy on average. ... but only due to the limitation of huffman not ... the probabilities of the source alphabet are inverse powers of two, ... compress smaller than the entropy and some longer. ...
    (comp.compression)
  • Re: Entropy and Equivalent Key Lengths?
    ... This increases to 4 bits of entropy if we allow case, ... > and special characters. ... best language models can compress text to 1.2-1.3 bpc. ...
    (sci.crypt)