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

2

u/UncleMeat Security | Programming languages Jun 18 '12

Sipser's book is considered by many to be the best introductory text on theory of computation. It covers a lot of things that are needed to understand PL theory, but not PL itself.

There is no "best" text on PL that I am aware of. It depends on if you want more practical ideas like parsers and compilers or more mathematical ideas like algebraic type theory. The "dragon" book is a well known book that covers the first set of materials. Fundamentals of Programming Languages by Mitchell is a pretty good guide to the second set of materials, but it is a little dry.