r/askscience • • Jun 17 '12

Computing How does file compression work?

(like with WinRAR)

I don't really understand how a 4GB file can be compressed down into less than a gigabyte. If it could be compressed that small, why do we bother with large file sizes in the first place? Why isn't compression pushed more often?

414 Upvotes

146 comments sorted by

View all comments

Show parent comments

3

u/1919 Jun 18 '12

Absolutely fascinating, though I do have a followup question.

Lets say you aren't coding a string, and instead you're coding something like a fixnum?

2

u/[deleted] Jun 18 '12

You mean like encoding a binary file? The machine implementation of this is to read everything in as numbers anyway, byte by byte, which is why it can operate on binary files and text files alike. That is, rather than describe an algorithm that was made for text using binary, computers just operate on binary. To illustrate, we can use a real computer algorithm on the text from above. Here is the sentence in ASCII format:

0000000 49 20 6c 69 6b 65 20 74 6f 20 70 6c 61 79 2e 20
0000020 57 68 65 6e 20 49 20 70 6c 61 79 20 49 20 68 61
0000040 76 65 20 66 75 6e 2e 20 54 68 65 20 72 65 61 73
0000060 6f 6e 20 49 20 70 6c 61 79 20 69 73 20 62 65 63
0000100 61 75 73 65 20 49 20 6c 69 6b 65 20 74 6f 20 68
0000120 61 76 65 20 61 73 20 6d 75 63 68 20 66 75 6e 20
0000140 61 73 20 70 6f 73 73 69 62 6c 65 2e 20 54 68 65
0000160 20 61 6d 6f 75 6e 74 20 6f 66 20 66 75 6e 20 49
0000200 20 68 61 76 65 20 69 73 20 62 61 73 65 64 20 6f
0000220 6e 20 74 68 65 20 61 6d 6f 75 6e 74 20 49 20 70
0000240 6c 61 79 2e 0a

Let's use Palmdoc, chosen mainly because Wikipedia tells me that Palmdoc format uses 11 bits for distance, and 3 bits for length (and 2 bits for padding). Simple math tells us that the dictionary length for palmdoc is 2k. Now, let's compare 'play I' with 'play i' as I had earlier. Do you see it in the block? I don't, but counting the bytes it should be at offset 24, or 0x18.

0000000 49 20 6c 69 6b 65 20 74 6f 20 70 6c 61 79 2e 20
0000020 57 68 65 6e 20 49 20 70 6c 61 79 20 49 20 68 61
                             ^
0000040 76 65 20 66 75 6e 2e 20 54 68 65 20 72 65 61 73
0000060 6f 6e 20 49 20 70 6c 61 79 20 69 73 20 62 65 63
                       ^

What the computer is actually doing is comparing the bytes as represented by hex '70 bc b1 79 20', and then determining that this is in the dictionary 30 characters earlier, using the same process as above. The computer output for this match is 00 00000011110 101 == 0x00F5. It is easily seen that this method will also work with any bytes 0x00-0xFF, not just bytes with an ASCII representation. Interestingly, text is compressed far better with LZ77 because of the tendency of passages to be repetitive. That's why it's ideal for source code, HTML, and pdfs, and not so great for binaries.