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

Path	csiph.com!newsfeed.hal-mli.net!feeder3.hal-mli.net!newsfeed.hal-mli.net!feeder1.hal-mli.net!newsfeed.xs4all.nl!newsfeed1.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
Return-Path	<dreamingforward@gmail.com>
X-Original-To	python-list@python.org
Delivered-To	python-list@mail.python.org
X-Spam-Status	OK 0.021
X-Spam-Evidence	'H': 0.96; 'S': 0.00; 'algorithm': 0.04; 'bits': 0.09; 'cc:addr:python-list': 0.11; 'anyway': 0.14; '"0"': 0.16; "'cause": 0.16; 'compression': 0.16; 'length.': 0.16; 'obviously,': 0.16; 'items.': 0.19; 'cc:addr:python.org': 0.22; 'cc:2**1': 0.23; 'least': 0.26; 'header:In-Reply-To:1': 0.27; "doesn't": 0.30; 'message-id:@mail.gmail.com': 0.30; 'piece': 0.31; 'subject:that': 0.31; 'lists': 0.32; 'but': 0.35; 'received:google.com': 0.35; 'data,': 0.36; 'sequence': 0.36; 'list': 0.37; 'sometimes': 0.38; 'generic': 0.38; 'does': 0.39; 'structure': 0.39; 'how': 0.40; 'length': 0.61; 'information': 0.63; 'containing': 0.69; 'washington': 0.93
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 :cc:content-type; bh=2H/uCVe5T9SwpmbksQ9iubgPGZ3wLuJ4hWjt67iZ58k=; b=x65Fw1hRYMKKwMXTlQ8avWv8+fZSKeA8wnD3K6WDMM4uMo8AqRkvZ8ecs2a8zktCud OO10rEfMKCaMaSoajt1GE4r4OsS6adEoUADNLbiz3iRUaP1ZRc6odzr+iHzI/bHxEyDf M3iHL4PwBnQpFA1evLMqBxJEsbDHe/aMVbOlCgEyJv4txNujTLv+lg6tuglQx8UborC+ EZw+jjZKgodIgGmM6w/lKxDa2ZwKuTMsR51xyVTBBnpR4SsnmQqJWKUNVDJ7RL5W9Ytb yyPoEt8lhkxSO6Bx2pPnG5X7ZLkhXHrYNKtqx58gkk9AGY0ul1rXuhQ91aBfwFwfh5O5 yZyQ==
MIME-Version	1.0
X-Received	by 10.180.182.193 with SMTP id eg1mr10789043wic.49.1383536436076; Sun, 03 Nov 2013 19:40:36 -0800 (PST)
In-Reply-To	<CAN1F8qX_6smuOCWYmuDXvD08NEED301smc22Az6VMePkoy8QQg@mail.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> <5275c065$0$29972$c3e8da3$5496439d@news.astraweb.com> <CAN1F8qX_6smuOCWYmuDXvD08NEED301smc22Az6VMePkoy8QQg@mail.gmail.com>
Date	Sun, 3 Nov 2013 19:40:36 -0800
Subject	Re: Algorithm that makes maximum compression of completly diffused data.
From	Mark Janssen <dreamingforward@gmail.com>
To	Joshua Landau <joshua@landau.ws>
Content-Type	text/plain; charset=ISO-8859-1
Cc	python-list <python-list@python.org>, Steven D'Aprano <steve+comp.lang.python@pearwood.info>
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.2004.1383536444.18130.python-list@python.org> (permalink)
Lines	24
NNTP-Posting-Host	2001:888:2000:d::a6
X-Trace	1383536444 news.xs4all.nl 15963 [2001:888:2000:d::a6]:45893
X-Complaints-To	abuse@xs4all.nl
Xref	csiph.com comp.lang.python:58426

Show key headers only | View raw

> Note that I *can* make a "compression" algorithm that takes any
> length-n sequence and compresses all but one sequence by at least one
> bit, and does not ever expand the data.
>
> "00" -> ""
> "01" -> "0"
> "10" -> "1"
> "11" -> "00"
>
> This, obviously, is just 'cause the length is an extra piece of data,
> but sometimes you have to store that anyway ;).

And how many bits will you use to store the length?

> So if I have a list of
> N length-Y lists containing only 1s or 0s, I can genuinely compress
> the whole structure by N log2 Y items.

But you cheated by using a piece of information from "outside the
system": length.  A generic compression algorithm doesn't have this
information beforehand.
-- 
MarkJ
Tacoma, Washington

Thread

csiph-web