←back to thread

The $5000 Compression Challenge (2001)

(www.patrickcraig.co.uk)
181 points ekiauhce | 1 comments | 23 Nov 24 21:10 UTC | HN request time: 0.212s | source
Show context
Panzer04 ◴[25 Nov 24 00:19 UTC] No.42231889[source]▶
I would have expected it to be possible to compress a single arbitrary random file with a small program. I would have thought an RNG could generate a file with some weakness that allows you to compress it, although said compressor would be worse at other inputs.

Likewise this challenge would have been stronger if the requirement was to compress two provided arbitrary files :P

replies(3): >>42232185 #>>42233044 #>>42235780 #
1. brody_hamer ◴[25 Nov 24 01:03 UTC] No.42232185[source]▶
I thought the same thing. Surely a random binary sequence will have some (small) repeating sequences? So as long as we can find them and (efficiently) mark their locations, we can have some small size reduction.

Which is basically what he’s done here. He’s cheating by marking the location of the repeating sequence using unique files, rather than some other actually more efficient location system.

This is a fun discussion! I think it helps to make compression feel more approachable for armchair enthusiasts.