How can a file shrink but still open exactly as before?

Why compress?

• Compression makes a file smaller, so it uses fewer bits.
• Smaller files need less storage space.
• They take less time to send or download and use less bandwidth.
• Common cases: streaming video and music, web pages, email attachments, photos on a phone.

Squeezing out repetition

• Data often repeats: a row of 6 white pixels, then 3 black, then 4 white.
• Instead of storing all 13 pixels, store each run as a count and a value: 6 W, 3 B, 4 W.
• The original can be rebuilt exactly, bit for bit. Compression that loses nothing is lossless.
• The more repetition there is, the more the file shrinks.

Run length encoding

• Run length encoding (RLE) replaces each run of repeated data with a pair: how many times it repeats, then the value.
• Each pair is a count and a data value.
• Example: 0000011100000011 becomes 5 0 3 1 6 0 2 1.
• RLE is lossless. With little repetition it can make the data bigger, as every single value gains a count.

Lossy and lossless

• Lossy compression permanently removes data, usually detail people are unlikely to notice.
• JPEG (photos) and MP3 (music) are lossy.
• Lossy: much smaller files, but lower quality and the original cannot be got back.
• Lossless: the original is rebuilt exactly, but the file is not as small. Use it for text, program files and data.

Caesar hid his letters in a shifted alphabet. Could you crack it?

The Caesar cipher

• Encryption keeps data secret: intercepted data can't be read without the key.
• An encryption algorithm turns plaintext into ciphertext.
• Caesar cipher: shift every letter the same number of places, wrapping from Z to A. The shift is the key. Shift 3: A→D, B→E, X→A.
• Only 25 shifts are useful, so an attacker can try them all: a brute-force attack.

The Vigenère cipher

• The Vigenère cipher uses a keyword instead of one shift.
• Write the keyword repeatedly under the plaintext. Each key letter gives that letter's shift: A = 0, B = 1 … Z = 25.
• Example: ATTACK with keyword LEMON gives LXFOPV.
• The same plaintext letter can become different ciphertext letters, so it is much harder to crack than Caesar.

The rail fence cipher

• The rail fence cipher moves letters around instead of replacing them.
• Write the plaintext in a zigzag down and up across a number of rows, the rails. The number of rails is the key.
• Read each rail from left to right, top rail first, to get the ciphertext.
• MEETATDAWN on 3 rails: MAW / ETTAN / ED gives MAWETTANED.

The pigpen cipher

• The pigpen cipher replaces each letter with a symbol.
• The key is two noughts-and-crosses grids and two X shapes. Each letter's symbol is the shape of the lines around its position.
• Letters in the second grid and second X also get a dot.
• Anyone with the key can decode it at once, so it hides messages only from people who don't know the method.

Big ideas

• Compression makes files smaller: less storage, faster transfer, less bandwidth.
• Lossless compression rebuilds the original exactly by storing repetition efficiently.
• RLE stores each run as a count and a value: 0000011100000011 → 5 0 3 1 6 0 2 1.
• Lossy compression permanently removes data for much smaller files.
• Encryption turns plaintext into ciphertext with a key so intercepted data can't be read.
• Caesar shifts every letter by one key; Vigenère uses a keyword of shifts; rail fence rearranges letters in a zigzag; pigpen swaps letters for symbols.
• A cipher with few possible keys, like Caesar, can be cracked by brute force.