NetNews Usenet Archive 1992 #27/NN_1992_27.iso/spool/comp/compress/research/298

Internet Message Format | 1992-11-23 | 1.8 KB

Path: sparky!uunet!utcsri!relay.cs.toronto.edu!neuron.ai.toronto.edu!ai.toronto.edu!radford
Newsgroups: comp.compression.research
From: [e-mail] (Radford Neal)
Subject: Kolmogorof complexity and data compression
Message-ID: <[e-mail]>
Organization: Department of Computer Science, University of Toronto
Date: 23 Nov 92 16:19:48 GMT
Lines: 28

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