--- marp: true theme: default html: true --- # Run-length encoding Making data smaller ยท Compression --- ## Today **We are learning to** compression stores data in fewer numbers, so it takes less space and less time to send. Run-length encoding stores how many of each colour there are in turn (3, 4, 1) instead of every pixel. It gives back exactly the same picture (lossless), and works best on data with long runs. - I can explain why data is compressed. - I can encode and decode a row with run-length encoding. - I can say when run-length encoding saves space and when it doesn't. --- ## Why it matters > A fax machine sent whole pages down a phone line in the 1980s, as numbers. How do you send a page with far fewer numbers than it has dots? --- ๐Ÿ’ฌ Discussion ## Predict **A row of 8 pixels is 3 white, then 4 black, then 1 white. Stored pixel by pixel, that is 8 numbers. Which is the shortest way to store it so you get **exactly** the same row back?** - 3, 4, 1: how many of each colour, in turn - 8: the number of pixels - 4: just the number of black pixels - You can't: every pixel needs its own number --- โœ๏ธ Activity ## Try it {{embed: https://studio.learningwaypoints.com/tutorials/_playground-board/index.html?id=deck%2Fsystems%2Fcompression%2Frun-length%2Fstep-2&code=widget%3A+pixels%0Asize%3A+8%2C+1%0Amode%3A+bw%0Arle%3A+on%0Astart%3A+white%0Atarget%3A+wwwkkkkw%0A&fresh=1}} [Open this step in the tutorial](https://studio.learningwaypoints.com/tutorials/systems/compression/run-length/?full=step-2#step-2) --- โœ… Check ## What happened? * 3, 4, 1. Taking turns from white, those three numbers rebuild the row exactly. Storing only 4 loses where the black pixels are. --- ๐Ÿ’ฌ Discussion ## Four rows Decompressing reads the codes back and gives exactly the same picture, so run-length encoding is **lossless**. Now decode 0, 2, 6. $$3, 4, 1$$ 1) $0, 8$ โ€” Row 2 starts black, so the code starts with 0 (no whites). 2) $8$ โ€” Row 3 is all white: one run. 3) $1, 1, 1, 1, 1, 1, 1, 1$ โ€” Row 4 changes every pixel: 8 numbers, no saving. 4) $3 + 2 + 1 + 8 = 14 \text{ numbers instead of } 32$ โ€” About 44% of the size. Long runs save a lot; no runs save nothing. --- โœ… Check ## Four rows **A row's code is **0, 2, 6**. What is the row?** - 2 white, then 6 black - 6 black, then 2 white - 2 black, then 6 white - 0 white, 2 white, 6 black * Answer: 2 black, then 6 white --- โœ… Check ## Find the mistake **Sam encodes a row that starts with black. Click the line where it first goes wrong.** ``` 1 Encode the row: black, black, white, white, white, white, white, white. 2 The first run is 2 black pixels. 3 So the code starts with 2. 4 Then 6 white: the code is 2, 6. ``` * Answer: line 3 --- โœ… Check ## Why compress? **Why compress data at all?** - Computers can't store uncompressed data - It makes pictures sharper - It makes data more secure - Smaller data takes less storage and is quicker and cheaper to send * Answer: Smaller data takes less storage and is quicker and cheaper to send --- โœ๏ธ Activity ## Vary: one change at a time - **A whole run:** - **No runs:** - **Fewest numbers:** - **Compression ratio:** - **When RLE works:** [Open this step](https://studio.learningwaypoints.com/tutorials/systems/compression/run-length/?full=step-4#step-4) --- โœ… Check ## Encode **What is the code for the row: white, white, black, black, black, black, black, black?** - 2, 2, 2, 2 - 2, 6 - 6, 2 - 0, 2, 6 * Answer: 2, 6 --- โœ… Check ## Decode the length **A row is decoded from **1, 3, 2, 2**. How many pixels long is it?** * Answer: 8 --- โœ… Check ## Text **Run-length encoding on text: **aaaabbbcc** can be stored asโ€ฆ** - 9 - a4b3c2d - 4a3b2c - abc * Answer: 4a3b2c --- โœ… Check ## Bigger? **Can run-length encoding make data **bigger**?** - Yes, when there are few runs, as in abcd โ†’ 1a1b1c1d - Only for pictures - No, compression always shrinks data - Only if you compress twice * Answer: Yes, when there are few runs, as in abcd โ†’ 1a1b1c1d --- โœ๏ธ Activity ## Make: draw from the codes Then: how many numbers would the plus sign need if it were twice as big (12 ร— 12)? [Open this step](https://studio.learningwaypoints.com/tutorials/systems/compression/run-length/?full=step-6#step-6) --- โœ… Check ## Exit ticket **Encode the row black, black, black, white, white, white, white, white. Why is run-length encoding called lossless?** * 0, 3, 5. Decompressing gives back exactly the same data.