Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!usc!rpi!sigma From: sigma@sun.ipl.rpi.edu (Kevin Martin) Newsgroups: comp.compression Subject: Re: DDJ compression competition FLAME Message-ID: Date: 10 Apr 91 19:08:19 GMT References: <1991Apr8.160133.22070@kcbbs.gen.nz> <14294@helios.TAMU.EDU> Lines: 31 Nntp-Posting-Host: ipl.rpi.edu byron@archone.tamu.edu (Byron Rakitzis) writes: >Just a comment here: last year, the Princeton CS department sponsored just >such a competition, i.e., the assignment was to compress and uncompress >a given dictionary. The competition was graded according to the sum of >(1) the compressed dictionary file, and (2) the size of the decompressing >executable. It was quite possible, and some even found it desirable to set >(1) to zero and to simply submit a huge program which produced a given output. I don't see how this follows. If the huge program submitted simply does a massive copy of the dictionary to output, what has been achieved? Nothing, because your executable would be at least as big as the original. Anyone who had written a program which did ANY degree of compression would beat your entry. Just simple RLE could make the dictionary smaller (maybe), or if there aren't any 8-bit characters, just change all the 8-bit codes to seven bits and assume a high zero. That's 12.5% compression right there, and if the dictionary is any decent size, the program will be much smaller than 1/8 the dictionary. >Not to say that this is a valid way of producing general-purpose compression >algorithms (I think this is the point of the competition in DDJ? I can't really >infer this from your article, and I have not read the journal myself) but it >does have its place. DDJ is trying to get general-purpose compression algorithms, although they don't make that clear. I don't really think something which requires 8Mb memory, even under Unix, is general-purpose. Something which fits in a 512K dataspace (640K MSDOS minus overhead) would be interesting indeed, unless it takes days to run. -- Kevin Martin sigma@ipl.rpi.edu