I wouldn’t aim for “perfectly”, not because it is impossible, but because it introduces an unnecessary constraint. Your typical movie is compressed with a loss

I wouldn’t aim for “perfectly”, not because it is impossible, but because it introduces an unnecessary constraint. Your typical movie is compressed with a lossy compression algorithm, so it will not perfectly replicate the original. You should aim for creating a compressor that creates something that has a smaller error, using some metric that takes into account what viewers can see. You also should define “size” as “size of the compressed movies plus the decompressor” because otherwise, you’ll find that the winning decompressor will contain copies of the movies. For a similar problem for text see https://en.wikipedia.org/wiki/Hutter_Prize https://en.wikipedia.org/wiki/Hutter_Prize