UCLA ACM's First Programming Competition: File Anti-Compression
Write a file encoder whose output, when sent through gzip,
is compressed by as little as possible.
(The full UCLA ACM description of this problem, problem #2, is no longer on the web.)
Date: Tue, 16 Nov 2004 01:02:02 -0800 From: Adam Harmetz <firstname.lastname@example.org> Subject: MPC Results! Thank you all for participating in ACM's Monthly Programming Contest. I have graded the results for the two problems this month. Problem 1 was open only to first and second years. There were two winners who correctly identified the longest palindrome in the text of Shakepeare's Hamlet. The winners were Shant Hovsepian and the two person team of Brian Chang and Grace Shih. All three people have won a prize package. In addition, Brian and Grace's solution was incredibly efficient and effectively used object oriented programming to create easy to read code. They deserve special accolades and won the style points for problem 1. There was great diversity within the answer set for project two. Perl, C++, Java, and shell scripting were all employed to try to beat gzip. Two themes emerged as "most successful" solutions. These solutions actually expanded the file length to be greater than the original file when "compressed." The first solution used a random number generator (or an array of random numbers hardcoded into the source) to XOR the bits of the original file. Since XOR is symmetric and random number generators will produce the same values if given the same seed, this solution had the interesting property that the encoder and decoder were the same program. The second solution was clever in its own way. It employed gzip itself to compress the original file. To ensure that the encoded file was the same length as the original, two different strategies were used. One used random data to pad the end of the file to the correct length. Another solution was to repeat copies of the gzipped data until the correct length was reached. Participants either stored the length somewhere in the file, added a special character at the end of the gzipped data, or took advantage of the fact that gzip will ignore trailing garbage. Either solution yielded the same expansion of the original file when gzipped. Chris Frost, Steve VanDeBogart, Wing-kai Chan, Adam Vartanian, Nathan Plumley, and Sean Soria were all able to implement one of the above optimal strategies. Other participants either employed strategies that resulted in compression (non-random choice of digits to XOR), or didn't fully take advantage of the various random number generators of Java and Python (too small a subset of random numbers yielded suboptimal results). Chris Frost, in addition to providing a wonderful narrative on gzip and an analysis of what an optimal solution looks like, also employed a clever trick to beat the rest of the participants. Since gzip stores the name of the file you are compressing inside the file, the longer the encoded file name the larger the compressed file. Chris chose the maximum filename length for his outputted encoded file. This showed a healthy knowledge of the inner workings of gzip and earns him the most significant prize package (wireless keyboard and mouse, Office XP Professional 2003, Visual Studio .NET, and Halo) as well as special accolades on this contest. Out of the remaining five high achievers on the contest, Nathan and Sean were randomly selected to receive a wireless keyboard from Microsoft. For the rest, I have copies of Halo for you. Thanks to everyone who participated. I'm really happy to see the enthusiastic response to this ACM program and a healthy desire to experiment with programming. Google and Real Networks will both be involved in designing future challenges and the Engineering Alumni Association came through with significant funding for future contests. Expect another contest after Thanksgiving to carry us through the holiday season. Thanks, of course, to Dr. Eggert for helping design problem 2 and to Microsoft for their generous support of the program. Please send me your resume if you would like to be included in the special packet being sent to Microsoft (it includes only those who participated in the contest). To pick up your prize, you are welcome to drop by my apartment if you are itching to get it soon (I live on Kelton). I will set up an "office hour" next week where you can drop by and pick them up from me on campus. As a final note, I'd like to let everyone know about the next major upcoming competition: Imagine Cup. Sponsored by Microsoft, there are a number of cool challenges and puzzles. Anyone who participated in our contest should find competing in Imagine Cup right up their alley. Email me if you want more info, or visit imagecup.com. You can email me if you would like more info on how your submission was graded or other questions. Take care, Adam
And if you're interested, my solution's description/analysis:
ACM Monthly Programming Contest Novermber 3rd Second Problem Chris Frost <email@example.com> ** Building and Requirements GNU's make will build frontend. This program requires: some bits and pieces of posix (eg system()), gzip, gunzip, cp, cat, echo, and touch. ** Usage Running frontend will output a help summary. To encode a file: frontend -e <input_filename> To decode a file: frontend -d <encoded_filename> <output_filename> Note: the encoded filename should not be changed. frontend will attempt to detect any important modifications, but it does not detect all changes. ** Algorithm The goal of this program is to encode a given file so that when this encoded file is given to gzip, it is larger than any other person's entry :). Two primary questions come to mind: - How can I do this? - Is there a maximum size? My two obvious answers to how are to produce what looks like random information (you can't compress randomness well) or to give gzip gzip's output. While producing random noise would make decoding difficult, cryptography has long studied how to make make information have random properties. Were the compressor in this contest unknown, I think I would take the route of encryption, it would probably hold up better in general. However, knowing gzip is the compressor, we can get larger file using gzip, I believe. As to whether there is a maximum, at which point we can stop trying: yes. zlib, used by gzip, detects when "compressed" information would be larger than its original size. In this case, the block (32KB) is stored without any compression along with five bytes of header information. There is an additional fixed overhead for the file header plus the variable-sized filename in the file header. Thus, the maximum we can make gzip expand a file is by 5B / 32KB + ~50B for the fixed header + the encoded filename. This algorithm gets as close to the 5B / 32KB limit as my measuring has allowed me to inspect. (I am sure you could inch more space out, however.) This algorithm also takes advantage of the filename encoding as far as a filesystem will let it, enlargining the gzipped file by another about 2^8 B. (This is os dependent.) My primary reference for gzip has been http://www.gzip.org/zlib/zlib_tech.html, as well as their rfcs. *** Achieving 5B / 32KB Inflation Our goal is 5B / 32KB, this is how we try to get there. After a bit of experimentation, I found that running gzip on gzip output reaches a local maxima fairly quickly, typically in less than four rounds. What we want is for the judge's gzip run to inflate the file by as much as possible. Thus, we should compress the file one less time than this. However, things aren't quite this simple because we have to have the same file length as the input file. Gzip has one sweet property we take advantage of: it detects non-gzip data at the end of the file and ignores it. Our approach is thus this: gzip the original file a few times to get us one step away from the local inflation maxima, write a little non-gzip data, then write hard-to-compress data until the file is long enough. It would be more involved in the decoding stage if we determined the number of gzip runs used on a perfile basis, so we gzip the input file three times. (What a little testing showed to work well for a couple files.) We then write a few byte string as the non-gzip "magic" data. We then concatentate a copy of the compressed input file onto itself until the compressed input + magic + this footer has a size at least that of the input. The footer is then compressed twice (this turns out to do a fair bit), and then all three parts are merged into one file. This single file is then truncated to the length of the original file. Finally, we output the encoded file. However, gzip stores the compressed file's name in the compressed file. We can take advantage of this and give the encoded file a long file name, which will thus increase the size of the judge's gzip run by this much more. How long a filename can be is dependent on the os, with linux and ext2 filenames are limited to 255 characters. (There are C constants giving maximum filename lengths, but they are often much longer than what the os's filesystem actually supports. We thus determine this experimentally at runtime.) A couple snags: - Exactly as we are doing to gzip, we could be given a file that we could inflate. We detect this in all cases and fall back to "encoding" the input by copying it. We transfer this fact to the decoder through the filename. - We assume that the data we will be dealing with is larger than around 32KB. If this assume fails, our copies will be within gzip's blocksize and the judge's gzip run will compress our encoding. I'm assuming/hoping this won't be the case, as I think people will be more likely to take the mindset of thinking large files are difficult, and the problem statement states "a rather long text file" will be used. A side note: One interesting thing I found was that we actually want to *avoid* as much header information stored in the encode phase as possible! Headers are not compressed, so every byte in a header is a byte not helping push the number of 32KB blocks higher. Thus the encode phase tells gzip not to store original filenames and timestamps. On a 165KB file, this makes the judge's gzipped file perhaps 2B larger. :) encode() contains more detailed documentation on the encoding. *** Decoding decode() explains this pretty straightfowardly, we just reverse the operations of encode(). This turns out to be simpler since we gzip throws the footer and magic away for us and we never deal with them. *** Room for Improvement - Be able to analytically calculate how many times to gzip data and allow this number to vary per file. - With the above, we could run gzip on what is now the encoded file. From experiments, running gzip on a concatentated file will push the judge's filesize a little more. - Support file encoding even when the input can be compressed and cated a few times but not for the full process. - Perhaps use zlib rather than gzip, which I believe stores less header data. ** Problem Summary: Write an encoder and decoder such that, given an arbitrary text file, the encoder's output (which must be the same size as the original) is compressed the least by the standard gzip utility. You must be able to use the decoder on the encoded file to get back the exact original. Eligibility: All UCLA students Due date: November 3rd Further description: To explain this in more detail, we will explain how we will be testing your encoder/decoder. First, we will choose a rather long text file, call it filea.txt. Next, we will run your encoder on this text file. The result of this process should be a separate file that is the exact same length as the original, call it fileaencoded.txt. You may produce fileaencoded.txt in any manner that you see fit. However, we must be able to run your decoder on fileaencoded.txt to produce filea.txt again exactly (We will use diff to check). To determine the winner of the contest, we will run gzip on fileaencoded.txt to produce fileaencoded.gz. Whichever competitor?s fileaencoded.gz is the largest will be the winner of the competition. Note that we may run this process on several different files and take the weighted average file size of the trials. What to turn in: You must turn in the source of your encoder and decoder, written in the language of your choice. Both files must be able to compile (if necessary) and run on a SEASnet machine. Please also turn in a README file if appropriate. Email your files to ucla.acm at gmail.com What determines the winner: Whoever has the largest average file size across all our test cases will win. If there are multiple entries that fit this criterion, all winners will be entered in a random drawing for available prizes. In addition, ?style points? will be awarded for clever, efficient, or otherwise unique answers. These contestants will receive additional prizes.