mirror of
https://github.com/google/brotli.git
synced 2026-07-08 17:56:58 +00:00
Compression efficiency: found "bad" case #91
Reference in New Issue
Block a user
Delete Branch "%!s()"
Deleting a branch is permanent. Although the deleted branch may continue to exist for a short time before it actually gets removed, it CANNOT be undone in most cases. Continue?
Originally created by @jneb on GitHub (Feb 4, 2016).
This is not a complaint, but more of a "teaser".
In case someone in here tries to squeeze the last drop out of the compressor, I found (after trying about everything, where brotli consistently beats both gzip and bzip) an easy way to generate strings where both bzip2 and gzip do produce shorter strings than brotli. Different from earlier reports, these are pretty short!
I am convinced that there must be a way to get these compressed more efficiently, so there must be some strange reason the compressor doesn't this.
Edited: version 0.3.0 does a better job than claimed here. These numbers are for 0.1.0. Still, there is room for improvement; see below.
In English: make a list of random 10-bit patterns, written out in ASCII.
In Python3:
2373
2107
2385
I hope this will inspire someone.
@jneb commented on GitHub (Feb 4, 2016):
Sorry, but I was using 0.1.0. Version 0.3.0 fares better, but still doesn't beat bz2:
2390
2113
2190
@eustas commented on GitHub (Feb 29, 2016):
Thank you for your report. We'll investigate what happens under the hood, and, perhaps, fix the problem.
@eustas commented on GitHub (Feb 29, 2016):
This seems to be limitation of encoding. bzip uses BWT and thus wins from the input format (\n, and ' ' get grouped). Thus it gets close to conventional compressors limit - about 17 bits per integer; using range coding would have improved the compression ratio.
And of course, this is much bigger than true entropy (10 bits per integer).
BTW, if we remove spaces and new lines
> ts=''.join('{:1b}'.format(random.getrandbits(1)) for i in range(10000))then
> print(len(codecs.encode(ts,'zip')))1661> print(len(codecs.encode(ts,'bz2')))1692> print(len(brotli.compress(ts)))1262@jneb commented on GitHub (Mar 1, 2016):
You are absolutely right, of course.
I was writing this because i was playing with this disassembler, and I was
trying to see which things compressed well and which didn't.
You can do a lot with clever block types and well chosen zero out one bit
distance and insert & copy encoding, and sometimes with contexts.
What I found missing is a way to repeat the literal length without having
to reencode the extra bits (with distance you can use last to handle that).
I wrote a small program that produces the shortest compression i could
think of in that case (see my github fork).
From all my playing and struggling, I found two ways to squeeze the
compression to the limit:
Allow for more (flexible??) contexts; make a way to say "same literal
length".
A context based on the character type 8 characters ago, for example, would
solve all problems (apart from creating lots of problems, of course...).
Thanks for inspiring me with this great compressor!
-Jurjen
Op 29 feb. 2016 17:45 schreef "eustas" notifications@github.com:
@eustas commented on GitHub (Mar 1, 2016):
Yup, it is not the first time we found that we could push the limit if the format wouldn't be frozen to the moment... But there is a trade-off: freeze format early and help customers adopting it or never freeze it, have a full freedom, but no customers.
Thank you again for your experiments and analysis, this would help us make the next compressor even better ;-)