HDTenEightyP/NetNews huggingface dataset:
Newsgroups: comp.compression.research
From: radford@cs.toronto.edu (Radford Neal)
Subject: Re: C source for Fractal compression, huh !
Organization: Department of Computer Science, University of Toronto
Date: 20 Nov 92 19:53:03 GMT

In article <1992Nov18.024912.24072@maths.tcd.ie> tim@maths.tcd.ie (Timothy Murphy) writes:

>>...information theory does not set an absolute limit on maximum compression 

> As I understand it, Chaitin/Kolmogorov Algorithmic Information Theory
> does set an absolute limit to the degree to which any given data can
> be compressed... subject only to the choice of a particular universal 
> Turing machine. (This last proviso would not have any effect in practice.)

When people talk about an "absolute limit on maximum compression", they
are referring to an ABSOLUTE theoretical limit on maximum compression.

Chaitin/Kolmogorov Algorithmic Information Theory does not give such
a limit, for the very reason you note - it depends on a particular 
choice of universal Turing machine. By chosing the Turing machine 
appropriately, I can make any string have any complexity whatsoever.
Saying that it's not an issue in practice is not germaine - we aren't
talking about PRACTICAL limits, but about ABSOLUTE, THEORETICAL limits.

In any case, none of this has anything to do with the original topic,
which was fractal compresion. The claims made for this technique do
indeed seem rather dubious, given their coyness about releasing hard
information, but they certainly can't be ruled out on theoretical
grounds, even allowing for some additional "practical" constraints.
There's not enough known about the psychology of human vision to tell
how much information can be deleted from images without harm, and
there's not enough known about the universe of images to say how
redundant they are.

    Radford Neal
Newsgroups: comp.compression.research
From: wtyler@adobe.com (William Tyler)
Subject: Re: C source for Fractal compression, huh !
Followup-To: comp.compression.research
Organization: Adobe Systems Inc., Mountain View, CA
Date: Sat, 21 Nov 1992 00:06:15 GMT

In article <1992Nov20.033432.18247@maths.tcd.ie> tim@maths.tcd.ie (Timothy Murphy) writes:

>The informational content H(s) of a string
>is the length of the shortest program
>which will output the string
>when fed into the universal Turing machine U.

I.e. H(s) is only well-defined when you have selected U. For any
string s, it is possible to construct a universal Turing machine U(s)
that will output s given the one-symbol input program '0'. If you'll
let me have a machine that will 'execute' an empty input tape, you
don't even need the one-symbol program. 

-- 
Bill Tyler      wtyler@adobe.com
Newsgroups: comp.compression.research
From: spot@CS.CMU.EDU (Scott Draves)
Subject: Re: C source for Fractal compression, huh !
Originator: spot@COBOL.FOX.CS.CMU.EDU
Organization: School of Computer Science, Carnegie Mellon University
	<1992Nov16.184754.3170@maths.tcd.ie> <Bxu712.LvA@metaflow.com>
	<1992Nov18.024912.24072@maths.tcd.ie>
Date: Fri, 20 Nov 1992 15:00:32 GMT


Timothy> Chaitin/Kolmogorov Algorithmic Information Theory does set an
Timothy> absolute limit to the degree to which any given data can be
Timothy> compressed: the string s cannot be compressed beyond its
Timothy> entropy (or informational content) H(s).

there's no limit to how well any one particular or small group of
possible inputs can be compressed.  consider a code that compresses
input A (say this netnews post) to "0", and any other input B to "1B".
clearly, that one bit is less than H(A), but averaged over all inputs,
satisfies the theory.  the magic of (lossless) compressing is deciding
what inputs you want to compress and "concentrating" the code to make
that portion of the possible input space take very little space, at
the expense of other stuff taking lots of space.

-- 
				orgasm
Scott Draves			nitrous
spot@cs.cmu.edu			death
Newsgroups: comp.compression.research
From: tim@maths.tcd.ie (Timothy Murphy)
Subject: Re: C source for Fractal compression, huh !
Organization: Dept. of Maths, Trinity College, Dublin, Ireland.
Date: Sat, 21 Nov 1992 15:12:12 GMT

radford@cs.toronto.edu (Radford Neal) writes:

>In article <1992Nov18.024912.24072@maths.tcd.ie> tim@maths.tcd.ie (Timothy Murphy) writes:

>>>...information theory does not set an absolute limit on maximum compression 

>> As I understand it, Chaitin/Kolmogorov Algorithmic Information Theory
>> does set an absolute limit to the degree to which any given data can
>> be compressed... subject only to the choice of a particular universal 
>> Turing machine. (This last proviso would not have any effect in practice.)

>When people talk about an "absolute limit on maximum compression", they
>are referring to an ABSOLUTE theoretical limit on maximum compression.

>Chaitin/Kolmogorov Algorithmic Information Theory does not give such
>a limit, for the very reason you note - it depends on a particular 
>choice of universal Turing machine. By chosing the Turing machine 
>appropriately, I can make any string have any complexity whatsoever.
>Saying that it's not an issue in practice is not germaine - we aren't
>talking about PRACTICAL limits, but about ABSOLUTE, THEORETICAL limits.

This is a complete red herring.
All right, let us agree to take the universal machine
defined in

@book{davis73
author = " Davis, M.",
title = "Computability and unsolvability",
publisher = "Dover",
year = 1973,
isbn = 0486614719
}

Now there is no doubt about it.
(The choice is irrelevant,
because if you insisted on the definition
in Marvin Minsky, "Finite and Infinite Machines",
you would reach exactly the same conclusion.)

>In any case, none of this has anything to do with the original topic,
>which was fractal compresion.

It has everything to do with this.
It shows beyond the slightest doubt
that it is not possible to reach the kind of compression
Barnsley speaks (or spoke) of,
without loss of information (ie reversibility).

>how much information can be deleted from images without harm, and
>there's not enough known about the universe of images to say how
>redundant they are.

If this is meant to be in response to my posting,
I said explicitly that this compression was not possible
_without loss of information_.
If you now accept that some information is lost,
but argue that it wasn't very valuable information anyway,
you are into a completely different realm,
where I have no intention of following you.


-- 
Timothy Murphy  
e-mail: tim@maths.tcd.ie
tel: +353-1-2842366
s-mail: School of Mathematics, Trinity College, Dublin 2, Ireland
From: z_youngwd@ccsvax.sfasu.edu
Newsgroups: comp.compression.research
Subject: fractal compression demo location. ip address
Date: 20 Nov 92 11:28:22 CST
Organization: Stephen F. Austin State University


Fractal compression demos are located at lyapunov.ucsd.edu (132.239.86.10)
in pub/uploads (temporarily).  Should be in pub/young-fractal soon.

Wayne

Newsgroups: comp.compression.research
From: tim@maths.tcd.ie (Timothy Murphy)
Subject: Re: C source for Fractal compression, huh !
Organization: Dept. of Maths, Trinity College, Dublin, Ireland.
Date: Fri, 20 Nov 1992 03:34:32 GMT

wtyler@adobe.com (William Tyler) writes:

>In article <1992Nov18.024912.24072@maths.tcd.ie> tim@maths.tcd.ie (Timothy Murphy) writes:

>>Chaitin/Kolmogorov Algorithmic Information Theory
>>does set an absolute limit to the degree to which
>>any given data can be compressed:
>>the string s cannot be compressed 
>>beyond its entropy (or informational content) H(s).
>>H(s) is precisely defined,

>Ah, there's the rub. H(s) is only precisely defined with respect to
>some particular model of the information source s, expressed in the
>form of probabilities. 

I'm afraid this is completely wrong.
Algorithmic Information Theory
has nothing to do with probability.

The informational content H(s) of a string
is the length of the shortest program
which will output the string
when fed into the universal Turing machine U.

-- 
Timothy Murphy  
e-mail: tim@maths.tcd.ie
tel: +353-1-2842366
s-mail: School of Mathematics, Trinity College, Dublin 2, Ireland
Newsgroups: comp.compression.research
From: wtyler@adobe.com (William Tyler)
Subject: Re: C source for Fractal compression, huh !
Followup-To: comp.compression.research
Summary: Back to Basics
Organization: Adobe Systems Inc., Mountain View, CA
Date: Wed, 18 Nov 1992 08:33:35 GMT

In article <1992Nov18.024912.24072@maths.tcd.ie> tim@maths.tcd.ie (Timothy Murphy) writes:

>Chaitin/Kolmogorov Algorithmic Information Theory
>does set an absolute limit to the degree to which
>any given data can be compressed:
>the string s cannot be compressed 
>beyond its entropy (or informational content) H(s).
>H(s) is precisely defined,

Ah, there's the rub. H(s) is only precisely defined with respect to
some particular model of the information source s, expressed in the
form of probabilities. The better your model of the source, the more
you can compress the information. Usually our source models are far
from ideal, due both to lack of complete understanding of the source,
and practical considerations of constructing and using complex models.
As an example, consider a source where the probability of a given
symbol being emitted was a function of the previous 10^10 symbols.
You aren't likely to even try to tabulate the probabilities, let alone
make optimal use of them :-)

Bill


-- 
Bill Tyler      wtyler@adobe.com
From: rohit@sloth.eng.uci.edu (Rohit Agarwal)
Subject: ( Shimmering ) artifacts in wavelet based video compression ?
Newsgroups: comp.compression.research
Organization: University of California, Irvine
Keywords: Wavelet Transform, Video Compression
Date: 17 Nov 92 01:03:10 GMT

	I have been doing some work with the compression of video by taking
a wavelet transform, scalar quantization and entropy coding. I have implemented
a video compression scheme that uses purely spatial techniques. No motion info
is used. I applied my technique to the compression of several of the CCIR601
MPEG test sequences and observed the following:

	In some of the sequences, particularly Tennis and Flower Garden, there
was a noticable shimmering in the background. Viewed individually, each of the
frames looked very good. For Tennis and Flower Garden, PSNR was about 35 dB on
the average. However viewed as video, ther was a noticable shimmering artifact.
Its as if the errors in each frame are highly uncorrelated with errors in other
frames or maybe it has something to do with interlacing. It might also have 
been due to not using temporal information. I have seen some of the MPEG 2
results from Kurihama and I noticed that there were a few techniques based on
wavelets which did not seem to have these artifacts particularly Aware1 and
 Aware2.
Can anyone give me some pointers as to the possible sources of this artifact.
Interestingly enough, my technique did much better on Mobile and Calendar --
individual frames had a lower PSNR than the other test sequences (about 30 dB),
and there were noticable artifacts in the individual images viewed still (the
white background of the calendar looked dirty gray) but viewed as a sequence
it looked "pretty good" even at 1H.

Also, the compression ratio was only 20:1 translating to a bitstream of about
8Mbps. 

rohit agarwal

Newsgroups: comp.compression.research
From: tim@maths.tcd.ie (Timothy Murphy)
Subject: Re: C source for Fractal compression, huh !
Organization: Dept. of Maths, Trinity College, Dublin, Ireland.
Date: Sun, 22 Nov 1992 23:34:25 GMT

radford@cs.toronto.edu (Radford Neal) writes:

>Go right ahead and adopt this Turing machine for all your computing
>needs if it makes you happy, but I suspect you'll find it a bit slow
>and awkward, as well as difficult to get good repair service for.

You misunderstand completely.
Just beacause you define a unit of time in terms of
the spectral frequency of caesium,
that does not mean that every wristwatch
has to include a caesium laser.

>As for myself, I'm happy to use whatever machine seems convenient at
>the time. In particular, if I'm interested in storing images compactly
>for later display, I'm happy to use a "machine" that is carefully
>tailored so that there are short "programs" that produce images that
>crop up a lot, at the expense of long "programs" for images that don't
>occur very often.

You will find that in order to separate your "easy" images
you will need rather a lot of cyles on the universal Turing machine U.

>What is it about data compression that induces so much confusion in
>the layperson? 

Which category do you place yourself in?
Since you base your comments on my posting,
which referred explicitly and exclusively
to Chaitin/Kolmogorov Algorithmic Information Theory,
may I ask if you have read anything on this subject?

>Half of them seem to think it plausible that one
>could compress any data set into practically nothing without any
>knowledge of the source probabilities, while the other half think 
>that knowledge of the source is irrelevant in light of mythical
>"theoretical limits" . . .

They are not mythical.
It is you who confuse theoretical and practical matters.
You dismissed my theoretical definition of informational content
(or entropy)
on the grounds that it was not based on practical computing practice.
This is like dismissing the special theory of relativity
on the grounds that Einstein
did not try to drive faster than the speed of light.

-- 
Timothy Murphy  
e-mail: tim@maths.tcd.ie
tel: +353-1-2842366
s-mail: School of Mathematics, Trinity College, Dublin 2, Ireland
Newsgroups: comp.compression.research
From: z_youngwd@ccsvax.sfasu.edu
Newsgroups: comp.compression.research
Subject: fractal compression source and exe's
Date: 19 Nov 92 20:30:50 CST
Organization: Stephen F. Austin State University

Sorry, I tried to rename the subject... no luck.
EXIT == FRACTAL COMPRESSION SOURCE POSTED
NEW NEW NEW NEW
From: phalke@pepper.rutgers.edu (V. Phalke)
Newsgroups: comp.compression.research
Subject: arithmetic coding
Keywords: when does it work ?
Date: 16 Nov 92 03:54:43 GMT
Organization: Rutgers Univ., New Brunswick, N.J.

Supposing SIGMA = { 0, 1}
If the probability P(0) is very high and P(1) is close to ZERO arithmetic
coding doesn't seem to work !! 
I mean supposing the string is pure ZEROES then arithmetic coding interval
will decrease very slowly. This would result in a very long encoding. On
the other hand the entropy of this data is very low!!
Any help ??

Thanks.

-Vidyadhar Phalke
===============================================================================
VIDYADHAR PHALKE
phalke@paul.rutgers.edu         (908) 878-1602(h)       (908) 932-4635(o)
         __/__|_\_  	--------  ZOOOOOOooooommmMMMM IT GOES
        "-O-----O-"   __________________________________
===============================================================================
Newsgroups: comp.compression.research
From: radford@cs.toronto.edu (Radford Neal)
Subject: Kolmogorof complexity and data compression
Organization: Department of Computer Science, University of Toronto
Date: 23 Nov 92 16:19:48 GMT

Regarding the claims that Kolmogorof complexity theory places 
absolute limits on possible data compression:

I think the problem may be a misapprehension of the problem being
tackled. Kolmogorof complexity would be relevant if we were trying to
send an image (say) to someone with whom we had made no prior
arrangements. We would then need to (essentially) code the image as a
"self-extracting" compressed file, which can be interpreted as
instructions for some common machine which any interested person would
have available.

This isn't what most people mean by "data compression". Suppose we are
considering a compression method for high-definition television, for
example. There is no requirement that these images be decodable by
anyone with an IBM PC, even with no special software. Instead, we are
willing to build special TV's with decoding devices, and accept that
images will be decodable only by people in possession of such decoding
devices. These devices might, in particular, include large amounts of ROM.

Requiring that each image be encoded as a self-extracting file would
eliminate any but fairly simple schemes, since the program length to
do anything interesting would exceed the size of the uncompressed
image.  In constrast, there's no reason why we shouldn't put a few
megabytes of ROM in every TV, and thereby enable the images to be
compressed much further. (Well, maybe there's an _economic_ reason, but
that's not relevant to the discussion.)

    Radford Neal
Newsgroups: comp.compression.research
From: tim@maths.tcd.ie (Timothy Murphy)
Subject: Re: Kolmogorof complexity and data compression
Organization: Dept. of Maths, Trinity College, Dublin, Ireland.
Date: Mon, 23 Nov 1992 18:38:46 GMT

radford@cs.toronto.edu (Radford Neal) writes:

>This isn't what most people mean by "data compression". Suppose we are
>considering a compression method for high-definition television, for
>example. There is no requirement that these images be decodable by
>anyone with an IBM PC, even with no special software. Instead, we are
>willing to build special TV's with decoding devices, and accept that
>images will be decodable only by people in possession of such decoding
>devices. These devices might, in particular, include large amounts of ROM.

Sorry, you're wrong.
I know what you say sounds plausible,
but it's based on a misunderstanding.
We're not talking about the ease or otherwise of decoding.
We're talking about the informational content of the data.
If for example the data is random
then you will not be able to compress it at all,
regardless of how much ROM your recipient has.

(Incidentally, Chaitin/Kolmogorov entropy is only concerned
with compressibility itself --
it is not concerned at all with the length of time
the data takes to uncompress,
or indeed how much space this requires on the computer.)

-- 
Timothy Murphy  
e-mail: tim@maths.tcd.ie
tel: +353-1-2842366
s-mail: School of Mathematics, Trinity College, Dublin 2, Ireland
Xref: sparky comp.compression:3862 comp.binaries.ibm.pc.wanted:7261
From: nevries@accucx.cc.ruu.nl (Nico E de Vries)
Newsgroups: comp.compression,comp.binaries.ibm.pc.wanted
Subject: Re: ARJ password cracker.
Date: 16 Nov 92 16:47:58 GMT
Followup-To: comp.compression
Organization: Academic Computer Centre Utrecht

In <1992Nov14.065336.17744@nwnexus.WA.COM> ralphs@halcyon.com (Ralph Sims) writes:

>Matthew E. Bernold <MEB117@psuvm.psu.edu> writes:

>>only copy he has left is in the archive, and he can't get to them.  I know
>>I've read about password crackers for WordPerfect documents, and .ZIP files.
>>Is there such a beast for .ARJ files?

>Maybe I'm missing something, but what good is a password that anyone can
>crack?

Not very good. Unfortunately most common ones are crackable (WP, PKZIP, ARJ).
I know of WP and PKZIP crack programs but unfortunately not of ARJ crack
programs. ARJ encryption is very weak but nooane seems to have made a tool for it.

Nico E. de Vries  (nevries@cc.ruu.nl) |------------------*   AA   III  PPP
_ This text is supplied AS IS, no warranties of any kind |  A  A   I   P  P
| apply. No rights can be derived from this text. This   |  AAAA   I   PPP
| text is likely to contain spelling and grammar errors. |  A  A   I   P
*---------------------------( Donate to GreenPeace! )----*  A  A  III  P

"The IBM PC is still waiting for a version of the CP/M OS.", G.M. Vose, 1982.
Newsgroups: comp.compression
Subject: Re: Pkzip 2.0 in the 23'rd century?
From: cs272017@eeyore.stcloud.msus.edu (cs272 user 017)
Date: 15 Nov 92 16:20:50 -0600
Organization: St. Cloud State Univ., MN

PKWare has stated (maybe this is *the* time) that PKZip 2.x will be
released at the end of November, and that it is in final beta.
Hopefully this is finally *it*...

Newsgroups: comp.compression
From: mef@goby.cs.washington.edu (Marc Fiuczynski)
Subject: RE: Lossless audio compression. (SHORTEN)
Organization: /homes/gws/mef/.organization
Date: 18 Nov 92 15:09:46

You will want to use Tony Robinson's shorten program.  It is available
on svr-ftp.eng.cam.ac.uk:/misc/shorten*.shar.  There should only be
one file, but I don't know what version he is working on now.  The
information below is from vesion 0.1.  I believe that he is now
working on version 0.4.

Shorten is a lossless compression for audio files using Huffman coding
of prediction residuals.  The amount of compression obtained depends
on the nature of the audio signal.  Those composing of low frequencies
and low amplitudes give the best compression.  Compression is
generally better than that obtained by general purpose compression
utilities for audio files.

Audio format supported are:

     Sun audio format (8 bit ulaw)
     s8  signed 8 bit values
     u8  unsigned 8 bit values
     s16 signed 16 bit values
     u16 unsigned 16 bit values
     s16x signed 16 bit values, byte swapped
     u16x unsigned 16 bit values, byte swapped


Sincerely,

Marc E. Fiuczynski
From: nevries@accucx.cc.ruu.nl (Nico E de Vries)
Newsgroups: comp.compression
Subject: Re: Need a compressor for sparse bit datastream
Keywords: compression technique
Date: 16 Nov 92 16:53:52 GMT
Organization: Academic Computer Centre Utrecht

In <1992Nov13.120505.29654@spectrum.xerox.com> richard@garfield.noname (richard_landells.sbd-e@rx.xerox.com) writes:

>I have an application that generates binary output.  The output is relatively random, but there are approximately twice as many off bits as on bits.  My objective is to compress this as much as possible.  

>I have tried several 'standard' compressors, arj 2.2, lharc, pkzip 1.1, and have only managed to achieve very minimal compression in the order of 4% at best (on a 40K file).  Now I know that a truly random binary datastream cannot be compressed, but I was kind of hoping for better than 4%.  Am I missing something fundamental, or is this really the best that can be achieved?  

>If there is a technique to compress this type of data, I would appreciate some pointers to some source code that implements it.

If the data is random but has two times more 0's than 1's use arithmetic
compression. This achieves better compression than the 4% you mentioned.
If there is some "logic" in the data (repeating patterns etc) you might
considder e.g. higher order arithmetic compression. 

Something which also might work is converting bits to bytes. This makes the
file 8 times larger but allows ARJ and PKZIP to do their job. Both are
byte oriented. The resulting compressed file might become smaller than
the compressed origional one.

>Richard Landells  (landells.sbd-e@rx.xerox.com)
>Rank Xerox System Centre

Nico E. de Vries  (nevries@cc.ruu.nl) |------------------*   AA   III  PPP
_ This text is supplied AS IS, no warranties of any kind |  A  A   I   P  P
| apply. No rights can be derived from this text. This   |  AAAA   I   PPP
| text is likely to contain spelling and grammar errors. |  A  A   I   P
*---------------------------( Donate to GreenPeace! )----*  A  A  III  P

"The IBM PC is still waiting for a version of the CP/M OS.", G.M. Vose, 1982.
Newsgroups: comp.compression