Part 6 · 1 chapters · ~8 min
Compression
Entropy and why some data compresses, LZ77 and dictionary matching, Huffman coding, the deflate format (gzip, zlib), modern codecs (zstd, LZ4, Snappy, Brotli) and their speed and ratio trade-offs, dictionary compression for small messages, columnar compression, and where compression pays in backends.
7
Matching repeats, coding symbols
code
LZ77: replace repeated substrings with (distance, length) back-references
"transfer.completed transfer.failed" → "transfer.completed (19,9)failed"
Huffman: give frequent symbols shorter bit codes (a prefix code built with a heap, DSA P4)
deflate (gzip, zlib, PNG) = LZ77 + Huffman
node -e "const z=require('zlib');const s=Buffer.from(JSON.stringify(Array.from({length:1000},(_,i)=>({id:i,status:'completed',currency:'NGN'}))));console.log(s.length, z.gzipSync(s).length, z.brotliCompressSync(s).length, z.zstdCompressSync?.(s)?.length)"| codec | character | typical use |
|---|---|---|
| gzip / deflate | universal, moderate speed and ratio | HTTP responses, files |
| Brotli | better ratio for text, slower to compress | static web assets (pre-compressed) |
| zstd | excellent ratio/speed range, dictionaries | Kafka batches, databases, backups |
| LZ4 / Snappy | very fast, lower ratio | storage engines, RPC, in-memory |
Repetitive JSON compresses extremely well; already-compressed data (images, encrypted data) does not compress at all. Dictionary compression (zstd with a trained dictionary) helps when each message is small but they share structure (events, logs). Columnar formats (Parquet, ClickHouse) compress far better than rows because similar values sit together.