Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #111432 > unrolled thread

Compression

Back to article view | Back to comp.lang.python

Contents

  Compression Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2016-07-14 18:16 +1000
    Re: Compression wxjmfauth@gmail.com - 2016-07-14 01:52 -0700
    Re: Compression Peter Otten <__peter__@web.de> - 2016-07-14 10:59 +0200
    Re: Compression Chris Angelico <rosuav@gmail.com> - 2016-07-14 21:07 +1000

#111432 — Compression

I thought I'd experiment with some of Python's compression utilities. First I 
thought I'd try compressing some extremely non-random data:


py> import codecs
py> data = "something non-random."*1000
py> len(data)
21000
py> len(codecs.encode(data, 'bz2'))
93
py> len(codecs.encode(data, 'zip'))
99


That's really good results. Both the bz2 and Gzip compressors have been able to 
compress nearly all of the redundancy in the data.

What if we shuffle the data so it is more random?

py> import random
py> data = list(data)
py> random.shuffle(data)
py> data = ''.join(data)
py> len(data); len(codecs.encode(data, 'bz2'))
21000
10494


How about some really random data?

py> import string
py> data = ''.join(random.choice(string.ascii_letters) for i in range(21000))
py> len(codecs.encode(data, 'bz2'))
15220

That's actually better than I expected: it's found some redundancy and saved 
about a quarter of the space. What if we try compressing data which has already 
been compressed?

py> cdata = codecs.encode(data, 'bz2')
py> len(cdata); len(codecs.encode(cdata, 'bz2'))
15220
15688

There's no shrinkage at all; compression has actually increased the size.


What if we use some data which is random, but heavily biased?

py> values = string.ascii_letters + ("AAAAAABB")*100
py> data = ''.join(random.choice(values) for i in range(21000))
py> len(data); len(codecs.encode(data, 'bz2'))
21000
5034



So we can see that the bz2 compressor is capable of making use of deviations 
from uniformity, but the more random the initial data is, the less effective is 
will be.


-- 
Steve

[toc] | [next] | [standalone]

#111433

Le jeudi 14 juillet 2016 10:17:14 UTC+2, Steven D'Aprano a écrit :
> I thought I'd experiment with some of Python's compression utilities. First I 
> thought I'd try compressing some extremely non-random data:
> 
> 
> py> import codecs
> py> data = "something non-random."*1000
> py> len(data)
> 21000
> py> len(codecs.encode(data, 'bz2'))
> 93
> py> len(codecs.encode(data, 'zip'))
> 99
> 
> 
> That's really good results. Both the bz2 and Gzip compressors have been able to 
> compress nearly all of the redundancy in the data.
> 
> What if we shuffle the data so it is more random?
> 
> py> import random
> py> data = list(data)
> py> random.shuffle(data)
> py> data = ''.join(data)
> py> len(data); len(codecs.encode(data, 'bz2'))
> 21000
> 10494
> 
> 
> How about some really random data?
> 
> py> import string
> py> data = ''.join(random.choice(string.ascii_letters) for i in range(21000))
> py> len(codecs.encode(data, 'bz2'))
> 15220
> 
> That's actually better than I expected: it's found some redundancy and saved 
> about a quarter of the space. What if we try compressing data which has already 
> been compressed?
> 
> py> cdata = codecs.encode(data, 'bz2')
> py> len(cdata); len(codecs.encode(cdata, 'bz2'))
> 15220
> 15688
> 
> There's no shrinkage at all; compression has actually increased the size.
> 
> 
> What if we use some data which is random, but heavily biased?
> 
> py> values = string.ascii_letters + ("AAAAAABB")*100
> py> data = ''.join(random.choice(values) for i in range(21000))
> py> len(data); len(codecs.encode(data, 'bz2'))
> 21000
> 5034
> 
> 
> 
> So we can see that the bz2 compressor is capable of making use of deviations 
> from uniformity, but the more random the initial data is, the less effective is 
> will be.
> 
> 
> -- 
> Steve


é Ü œ € ξ Ž Ӂ ሴ 㑖 …

[toc] | [prev] | [next] | [standalone]

#111435

Steven D'Aprano wrote:

> How about some really random data?
> 
> py> import string
> py> data = ''.join(random.choice(string.ascii_letters) for i in
> range(21000)) py> len(codecs.encode(data, 'bz2'))
> 15220
> 
> That's actually better than I expected: it's found some redundancy and
> saved about a quarter of the space. 

It didn't find any redundancy, it found the two unused bits:

>>> math.log(len(string.ascii_letters), 2)
5.700439718141093
>>> 21000./8*_
14963.654260120367

[toc] | [prev] | [next] | [standalone]

#111436

On Thu, Jul 14, 2016 at 6:16 PM, Steven D'Aprano
<steve+comp.lang.python@pearwood.info> wrote:
> How about some really random data?
>
> py> import string
> py> data = ''.join(random.choice(string.ascii_letters) for i in range(21000))
> py> len(codecs.encode(data, 'bz2'))
> 15220
>
> That's actually better than I expected: it's found some redundancy and saved
> about a quarter of the space.

What it found was an imbalance in the frequencies of byte values - you
used 52 values lots of times, and the other 204 never. Huffman coding
means those 52 values will get fairly short codes, and if you happened
to have just one or two other byte values, they'd be represented by
longer codes. It's like the Morse code - by encoding some letters with
very short sequences (dot followed by end-of-letter for E, dash
followed by end-of-letter for T) and others with much longer sequences
(dash-dot-dot-dash-EOL for X), it manages a fairly compact
representation of typical English text. The average Morse sequence
length for a letter is 3.19, but on real-world data... well, I used
the body of your email as sample text (yes, I'm aware it's not all
English), and calculated a weighted average of 2.60. (Non-alphabetics
are ignored, and the text is case-folded.) Using the entire text of
Gilbert & Sullivan's famous operettas, or the text of "The Beauty
Stone", or the wikitext source of the Wikipedia article on Morse code,
gave similar results (ranging from 2.56 to 2.60); interestingly, a
large slab of Lorem Ipsum skewed the numbers slightly lower (2.52),
not higher as I was afraid it would, being more 'random'.

Further example: os.urandom() returns arbitrary byte values, and (in
theory, at least) has equal probability of returning every possible
value. Base 64 encoding that data makes three bytes come out as four.
Check this out:

>>> data = os.urandom(21000)
>>> len(base64.b64encode(data)) # just to make sure
28000
>>> len(codecs.encode(data, 'bz2'))
21458
>>> len(codecs.encode(base64.b64encode(data), 'bz2'))
21290

When you remove the redundancy in b64-encoded data, you basically...
get back what you started with. (Curiously, several repeated
os.urandommings showed consistent results to the above - 214xx for
direct 'compression' vs 212xx for b64-then-compress. But in both
cases, it's larger than the 21000 bytes of input.)

ChrisA

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.python

csiph-web