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

Path	csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!goblin1!goblin2!goblin.stu.neva.ru!newsfeed.xs4all.nl!newsfeed1.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.018
X-Spam-Evidence	'H': 0.96; 'S': 0.00; 'binary': 0.07; 'bytes,': 0.09; 'bytes.': 0.09; 'encode': 0.09; 'exp': 0.09; 'grid': 0.09; 'handful': 0.09; 'mind,': 0.09; 'scheme.': 0.09; '(high': 0.16; '255': 0.16; '65536': 0.16; 'byte,': 0.16; 'exponent': 0.16; 'from:addr:rosuav': 0.16; 'from:name:chris angelico': 0.16; 'wrote:': 0.18; 'bit': 0.19; 'value.': 0.19; 'fit': 0.20; '>>>': 0.22; 'saying': 0.22; 'byte': 0.24; 'bytes': 0.24; 'instance,': 0.24; 'integer': 0.24; 'mathematical': 0.24; 'space.': 0.24; 'typical': 0.24; 'sort': 0.25; 'somewhere': 0.26; 'header:In- Reply-To:1': 0.27; 'point': 0.28; 'michael': 0.29; 'message- id:@mail.gmail.com': 0.30; 'work.': 0.31; 'subject:that': 0.31; 'allows': 0.31; 'fri,': 0.33; 'trouble': 0.34; 'skip:d 20': 0.34; 'could': 0.34; 'common': 0.35; 'something': 0.35; 'case,': 0.35; 'but': 0.35; 'received:google.com': 0.35; 'add': 0.35; 'there': 0.35; 'described': 0.36; 'shorter': 0.36; 'useful': 0.36; 'possible': 0.36; 'example,': 0.37; 'application': 0.37; 'too': 0.37; 'two': 0.37; 'represent': 0.38; 'nov': 0.38; 'to:addr :python-list': 0.38; 'pm,': 0.38; 'to:addr:python.org': 0.39; 'system.': 0.39; 'even': 0.60; 'blank': 0.60; 'gone': 0.61; 'numbers': 0.61; 'entire': 0.61; 'range': 0.61; "you're": 0.61; 'information': 0.63; 'more': 0.64; 'needing': 0.65; 'between': 0.67; 'theoretical': 0.74; 'guaranteed': 0.75; 'density': 0.84; 'hardly': 0.84; 'loose': 0.84; 'numbers:': 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:content-transfer-encoding; bh=6rkaFpFSZLO4QGRfTmkRC2LiJ36xLvXjF1H1pBtY5LE=; b=eW14tSSeppoNelUMeZ0iNPlwW/e7N4zzuEfHhm8pwOj9jTFekazBkhh3CMwWkB6YVa dVdUY0YkFpWEqyPdAXA13ewyb+ZLv2o3wen1RugPwYUBe/QLOgXf9rLHjVZxHSqtH/uh 6xp1s6Gf4oAdXPBfEvXJ5jlQf2mSQhOljdoyUNuBdZI5NDoMjvATagFtFuKSQAlc4PRf vXSU1YySN7NhNkKoIkmmcQaMia0za1f5IHtjm+YRdxig7oCfP1Y9jhcIGZN/4Y9usmTO +gC7vG6qlkAKQixQiSq5FoEbDxfjDB8uzEJnAyRNDhQG+jVcKSNDH7sFPk7uUUmUDgnL mvIQ==
MIME-Version	1.0
X-Received	by 10.68.234.165 with SMTP id uf5mr12592614pbc.41.1383881067473; Thu, 07 Nov 2013 19:24:27 -0800 (PST)
In-Reply-To	<B07C8854-073B-4568-86E2-64374D33163A@gmail.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> <9d998707-a6e9-4911-a585-c2310e4a2b31@googlegroups.com> <q7im799jqj9ap3jb94lnqka1m0hnn9bnpv@4ax.com> <CAMjeLr8jao50FSqM9pT=77in0nPNCOA8SQwHC_Jm50eiQYTs+g@mail.gmail.com> <mailman.2161.1383863216.18130.python-list@python.org> <9b62770c-7ca1-4a4d-81a5-bf7251bac957@googlegroups.com> <mailman.2171.1383877064.18130.python-list@python.org> <13c04f06-f1f2-4f67-b975-3cff28714641@googlegroups.com> <B07C8854-073B-4568-86E2-64374D33163A@gmail.com>
Date	Fri, 8 Nov 2013 14:24:27 +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
Content-Transfer-Encoding	quoted-printable
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.2181.1383881070.18130.python-list@python.org> (permalink)
Lines	62
NNTP-Posting-Host	2001:888:2000:d::a6
X-Trace	1383881070 news.xs4all.nl 15919 [2001:888:2000:d::a6]:54783
X-Complaints-To	abuse@xs4all.nl
Xref	csiph.com comp.lang.python:58744

Show key headers only | View raw

On Fri, Nov 8, 2013 at 1:43 PM, R. Michael Weylandt
<michael.weylandt@gmail.com> <michael.weylandt@gmail.com> wrote:
> Chris's point is more subtle: the typical computer will store the number 65536 in a single byte, but it will also store 4 and 8 in one byte. So if your choice is between sending "65536" and "(4,8)", you actually loose efficiency in your scheme. Don't think in decimal, but in terms of information needing transfer.

Well, 65536 won't fit in a single byte, nor even in two (only just). A
typical binary representation of 65536 would take 3 bytes, or 4 for a
common integer type: 0x00 0x01 0x00 0x00 (big-endian). So it would be
possible to represent that more compactly, if you deem one byte each
for the base and the exponent: 0x04 0x08. However, that system allows
you to represent just 62,041 possible numbers:

>>> decomp={}
>>> for base in range(256):
    for exp in range(256):
        decomp[base**exp]=base,exp

>>> len(decomp)
62041

The trouble is, these numbers range all the way up from 0**0 == 0 to
255**255 == uhh...
>>> 255**255
46531388344983681457769984555620005635274427815488751368772861643065273360461098097690597702647394229975161523887729348709679192202790820272357752329882392140552515610822058736740145045150003072264722464746837070302159356661765043244993104360887623976285955058200326531849137668562738184397385361179287309286327712528995820702180594566008294593820621769951491324907014215176509758404760451335847252744697820515292329680698271481385779516652518207263143889034764775414387732372812840456880885163361037485452406176311868267428358492408075197688911053603714883403374930891951109790394269793978310190141201019287109375

which would decompress to (obviously) 255 bytes. So you can represent
just over sixty thousand possible 255-byte strings in two bytes with
this system.

To generalize it, you'd need to devote a bit somewhere to saying
"There are more to add in". Let's say you do this on the exponent byte
(high bit for convenience), so you have 0x04 0x08 means 65536, and
0x04 0x88 0x01 0x01 means 65536+1 = 65537. Now we have something that
generalizes; but the efficiency is gone - and there are too many ways
to encode the same value. (Bear in mind, for instance, that 0x01 0xNN
for any NN will still just represent 1, and 0x00 0xNN will represent
0. That's wasting a lot of bits.)

The application I can see for this sort of thing is not data
compression, but puzzles. There are lots of puzzles that humans find
enjoyable that represent an entire grid with less data than it
contains - for one popular example, look at Sudoku. You have a 9x9
grid where each cell could contain any of nine digits, which means a
theoretical information density of 9**81; but the entire grid can be
described by a handful of digits and heaps of blank space. This could
be a similarly-fun mathematical puzzle: 3359232 can be represented as
B1**E1 + B2**E2, where all numbers are single-digit. Find B1, B2, E1,
and E2. In this case, you're guaranteed that the end result is shorter
(four digits), but it's hardly useful for general work.

ChrisA

Thread

csiph-web