Compressing the Library of Babel!
summary
Explains why a compressor cannot shrink the Library of Babel: using pigeonhole principle to show some books must expand, and using a tiny program-plus-runforever decompressor to invoke Kolmogorov complexity so compressed size is the decompressor size. Demos and numbers: gzip gives ~3:1 on Wikipedia, gzip2 ~4:1, the best listed PhD a9 beats that a bit. Mentions zip bombs, missing-page bitmap tradeoffs, and the Hutter Prize as a concrete 50k€ incentive.
AI-written summary · about
chapters (11)
- 0:00Start
- 0:14The Library Of Babel by Jorge Luis Borges
- 0:27All possible books
- 2:35If you have 101 pigeons, and 100 holes, two pigeons will share a hole
- 3:19Kolmogorov Complexity or "descriptive complexity"
- 4:31Representing missing data
- 5:19Page bitmap
- 6:02The Real Library of Babel
- 6:13Compressing Wikipedia
- 8:19Borges's Objection
- 9:02Recording and Production Confreaks
related talks
24mHow GZIP compression works
32mBeyond Zstandard: The Future of Data Compression
32mOn compression of everything in Postgres
18mWhy Lossless Data Compression Is Important and Fun
52mI Want to Compress Everything
34mIn core compression-How to shrink your database
01h 04mCompress and Conquer: Compression Algorithms in Databases
01h 09mBtune: Making Compression Better