Re: Algorithm that makes maximum compression of completly diffused data.

Path	csiph.com!usenet.pasdenom.info!weretis.net!feeder4.news.weretis.net!feeds.phibee-telecom.net!newsfeed.xs4all.nl!newsfeed2.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
Return-Path	<rosuav@gmail.com>
X-Original-To	python-list@python.org
Delivered-To	python-list@mail.python.org
X-Spam-Status	OK 0.004
X-Spam-Evidence	'H': 0.99; 'S': 0.00; 'repository': 0.05; 'say,': 0.05; 'not': 0.07; 'algorithms,': 0.07; 'clause': 0.09; 'compact': 0.09; 'git': 0.09; 'mercurial': 0.09; 'referenced': 0.09; 'stored': 0.12; 'itself.': 0.14; 'compression': 0.16; 'detects': 0.16; 'expect,': 0.16; 'from:addr:rosuav': 0.16; 'from:name:chris angelico': 0.16; 'somewhere.': 0.16; 'storing': 0.16; 'wrote:': 0.18; '(the': 0.22; 'format,': 0.24; 'instance,': 0.24; 'header:In-Reply-To:1': 0.27; "doesn't": 0.30; 'message- id:@mail.gmail.com': 0.30; 'usually': 0.31; 'apparently': 0.31; "d'aprano": 0.31; 'lot.': 0.31; 'steven': 0.31; 'subject:that': 0.31; 'file': 0.32; 'quite': 0.32; 'tool': 0.35; 'but': 0.35; 'received:google.com': 0.35; 'there': 0.35; 'data,': 0.36; 'described': 0.36; 'library.': 0.36; 'doing': 0.36; 'useful': 0.36; 'application': 0.37; 'nov': 0.38; 'to:addr:python-list': 0.38; 'files': 0.38; 'pm,': 0.38; 'track': 0.38; 'bad': 0.39; 'to:addr:python.org': 0.39; 'even': 0.60; 'skip:u 10': 0.60; 'is.': 0.60; 'then,': 0.60; 'information,': 0.61; 'real': 0.63; 'zip': 0.64; 'more': 0.64; 'limits:': 0.91; '2013': 0.98
DKIM-Signature	v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :content-type; bh=DWx1jfjdY4DkPZvtFvcg3ZABfN3b7etQLVJqcXneNaI=; b=IFDOxPxyoV2m4GIDSztJAX48u8qwsIdhbzxtQMk0JaLDrU7N4Bo5kp9utWMQAlipM1 Neu7m4LY++0Y3ia3oPSEEj7y3ZLW855ElOk83mnc5G9rJ3JOJfOJ08DKdMUrAH5+J02U JqVJplCOBhGyJzLRAvrn7kproT8stnfv+G52OA6ktehbRh9ER0T/SfyK6MT4U6HwI+fF SCfvz+uHC523+jV9ShlPbthWLb0WhUd3UmZfaFkH1UmMOZ5ommDCBYDILJudXcfatA+/ HRSZzUqWSpF6GoISDuwLLSyKjAspXaJn2hBAgJeGrSckpdea63YZ0MJ1Q1eABWEDWOvu Mjwg==
MIME-Version	1.0
X-Received	by 10.68.216.132 with SMTP id oq4mr11023427pbc.50.1383451830914; Sat, 02 Nov 2013 21:10:30 -0700 (PDT)
In-Reply-To	<5275c065$0$29972$c3e8da3$5496439d@news.astraweb.com>
References	<205bfa4f-29de-43de-be5a-72a12d77d0c9@googlegroups.com> <mailman.1835.1383162420.18130.python-list@python.org> <c73c8aa6-cac4-4f02-ae83-31cea167c172@googlegroups.com> <s9ra79dvvnd01rpuqg9hfh6bija8u2q49h@4ax.com> <5275c065$0$29972$c3e8da3$5496439d@news.astraweb.com>
Date	Sun, 3 Nov 2013 15:10:30 +1100
Subject	Re: Algorithm that makes maximum compression of completly diffused data.
From	Chris Angelico <rosuav@gmail.com>
To	python-list@python.org
Content-Type	text/plain; charset=ISO-8859-1
X-BeenThere	python-list@python.org
X-Mailman-Version	2.1.15
Precedence	list
List-Id	General discussion list for the Python programming language <python-list.python.org>
List-Unsubscribe	<https://mail.python.org/mailman/options/python-list>, <mailto:python-list-request@python.org?subject=unsubscribe>
List-Archive	<http://mail.python.org/pipermail/python-list/>
List-Post	<mailto:python-list@python.org>
List-Help	<mailto:python-list-request@python.org?subject=help>
List-Subscribe	<https://mail.python.org/mailman/listinfo/python-list>, <mailto:python-list-request@python.org?subject=subscribe>
Newsgroups	comp.lang.python
Message-ID	<mailman.1965.1383451840.18130.python-list@python.org> (permalink)
Lines	29
NNTP-Posting-Host	2001:888:2000:d::a6
X-Trace	1383451840 news.xs4all.nl 15951 [2001:888:2000:d::a6]:36346
X-Complaints-To	abuse@xs4all.nl
Xref	csiph.com comp.lang.python:58360

Show key headers only | View raw

On Sun, Nov 3, 2013 at 2:17 PM, Steven D'Aprano
<steve+comp.lang.python@pearwood.info> wrote:
> There is a way to apparently get around these limits: store data
> externally, perhaps inside the compression application itself. Then, if
> you just look at the compressed file (the "data.zip" equivalent, although
> I stress that zip compression is *not* like this), you might think it has
> shrunk quite a lot. But when you include the hidden data, the compression
> is not quite so impressive...

Storing externally is, of course, a very useful thing - it's just not
compression. For instance, a git repository (and quite likely a
Mercurial one too) keeps track of files as blobs of data referenced by
their cryptographic hashes. The current state of a directory can be
described by listing file names with their object hashes, which is a
very compact notation; but it doesn't have _all_ the information, and
the "decompression" process involves fetching file contents from the
library. It's a tool in the arsenal, but it's not compression in the
same way that PK-ZIP is.

With real compression algorithms, there's usually an "out" clause that
detects that the algorithm's doing a bad job. The file format for
PK-ZIP and, I expect, every other archiving+compression file format,
has allowances for some of the files to be stored uncompressed. That
way, there's no need for any file to be enlarged by more than some
signature - say, a one-byte "compression type" marker, or even a
one-bit mark somewhere. But enlarged they must be, for the reasons
Steven explained.

ChrisA

Thread

csiph-web