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

Path	csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!goblin2!goblin.stu.neva.ru!newsfeed.xs4all.nl!newsfeed3.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
Return-Path	<michael.weylandt@gmail.com>
X-Original-To	python-list@python.org
Delivered-To	python-list@mail.python.org
X-Spam-Status	OK 0.055
X-Spam-Evidence	'H': 0.89; 'S': 0.00; 'algorithm': 0.04; 'bits': 0.09; 'e.g.,': 0.09; 'encode': 0.09; 'scheme.': 0.09; 'cc:addr :python-list': 0.11; 'random': 0.14; '65536': 0.16; 'byte,': 0.16; 'compression': 0.16; 'encoding.': 0.16; 'losing': 0.16; 'noted)': 0.16; 'prevent': 0.16; 'wrote:': 0.18; '>>>': 0.22; 'cc:addr:python.org': 0.22; 'byte': 0.24; 'certainly': 0.24; 'laws': 0.24; 'typical': 0.24; 'cc:2**0': 0.24; 'sort': 0.25; 'solutions.': 0.26; 'least': 0.26; 'certain': 0.27; 'header:In- Reply-To:1': 0.27; 'point': 0.28; 'chris': 0.29; 'sets': 0.30; 'url:mailman': 0.30; 'gives': 0.31; 'easier': 0.31; 'fast.': 0.31; 'subject:that': 0.31; 'values.': 0.31; 'figure': 0.32; 'stuff': 0.32; 'url:python': 0.33; '(e.g.': 0.33; 'fri,': 0.33; 'guess': 0.33; "can't": 0.35; 'but': 0.35; 'received:google.com': 0.35; 'google': 0.35; 'accessible': 0.36; 'data,': 0.36; 'url:listinfo': 0.36; 'charset:us-ascii': 0.36; 'url:org': 0.36; 'two': 0.37; 'message-id:@gmail.com': 0.38; 'generic': 0.38; 'nov': 0.38; 'pm,': 0.38; 'sure': 0.39; 'space': 0.40; 'url:mail': 0.40; 'how': 0.40; 'number,': 0.60; 'problems.': 0.60; 'matter': 0.61; 'making': 0.63; 'header:Message-Id:1': 0.63; 'email addr:gmail.com': 0.63; 'information': 0.63; 'more': 0.64; 'needing': 0.65; 'to:addr:gmail.com': 0.65; 'reply': 0.66; 'between': 0.67; 'lose': 0.68; 'physics': 0.68; 'eight': 0.74; 'fourth': 0.84; 'fuck': 0.84; 'loose': 0.84; '2013,': 0.91; '2013': 0.98
DKIM-Signature	v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=references:mime-version:in-reply-to:content-type :content-transfer-encoding:message-id:cc:from:subject:date:to; bh=oIJbnRaoCQYHvySaQmSkh0KX4Vv7V8tSkN2uQR24VUk=; b=lDEoa3DUFT+sg/MTzMG7pkaoH+2/Std4sdaDCUCdGAIXDb24+KIoftbUI4qdwFdC4N pXnywggyGhlmUSNw2YMgHASkeg5yBXFYW7KF8DS2bZVMrUz8mu5O6bp8anbwq5q36gTZ P7FVjTl2KyIO9HIBHAnynw00vVt3r3dmC5BUBBV/mUU76gxHmQ/G6YectqmOpxMYhZ/2 M8zdw9JCtEMOwFDSPAK5HTf+aXksdJw5aHx6qpRhouyGTOhOz4kVGx15w4trdh6sipCS ZYOINjxRtm4Oej27VZUYpCZNDW0wMABtXzbXpwrWTvu/ECKyt9pZjwwQ8TcWpqWb6qhb 78UQ==
X-Received	by 10.49.110.9 with SMTP id hw9mr18759376qeb.4.1383878594223; Thu, 07 Nov 2013 18:43:14 -0800 (PST)
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>
Mime-Version	1.0 (1.0)
In-Reply-To	<13c04f06-f1f2-4f67-b975-3cff28714641@googlegroups.com>
Content-Type	text/plain; charset=us-ascii
Content-Transfer-Encoding	quoted-printable
X-Mailer	iPhone Mail (10B329)
From	"R. Michael Weylandt <michael.weylandt@gmail.com>" <michael.weylandt@gmail.com>
Subject	Re: Algorithm that makes maximum compression of completly diffused data.
Date	Thu, 7 Nov 2013 21:43:10 -0500
To	"jonas.thornvall@gmail.com" <jonas.thornvall@gmail.com>
Cc	"python-list@python.org" <python-list@python.org>
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.2177.1383878602.18130.python-list@python.org> (permalink)
Lines	55
NNTP-Posting-Host	2001:888:2000:d::a6
X-Trace	1383878602 news.xs4all.nl 15930 [2001:888:2000:d::a6]:40355
X-Complaints-To	abuse@xs4all.nl
Xref	csiph.com comp.lang.python:58740

Show key headers only | View raw

On Nov 7, 2013, at 21:25, jonas.thornvall@gmail.com wrote:

> Den fredagen den 8:e november 2013 kl. 03:17:36 UTC+1 skrev Chris Angelico:
>> On Fri, Nov 8, 2013 at 1:05 PM,  <jonas.thornvall@gmail.com> wrote:
>> 
>>> I guess what matter is how fast an algorithm can encode and decode a big number, at least if you want to use it for very big sets of random data, or losless video compression?
>> 
>> 
>> 
>> I don't care how fast. I care about the laws of physics :) You can't
>> 
>> stuff more data into less space without losing some of it.
>> 
>> 
>> 
>> Also, please lose Google Groups, or check out what other people have
>> 
>> said about making it less obnoxious.
>> 
>> 
>> 
>> ChrisA
> 
> Please, you are he obnoxious, so fuck off or go learn about reformulation of problems. Every number has an infinite number of arithmetical solutions. So every number do has a shortest arithmetical encoding. And that is not the hard part to figure out, the hard part is to find a generic arithmetic encoding.
> 
> I am not sure if it is just stupidness or laziness that prevent you from seeing that 4^8=65536.

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. 

You might reply that you don't need a whole byte for 4 or 8 -- that's true. You could, e.g., just encode the fourth and eight bits of a single byte and send that: certainly gives some compression but at the cost of generality-- what would you do with 65^65? It's sort of like the mean-variance tradeoff in statistics; it's much easier to encode certain data sets (e.g. powers of two as you noted) but only if you concede your algorithm will only work for those values. 

More generally, check out the work of Claud Shannon; a very accessible and worthwhile author. 
> -- 
> https://mail.python.org/mailman/listinfo/python-list

Thread

csiph-web