Chapter 5 · Watch, then practise
Data Compression
Separate exact reconstruction from acceptable information loss. Practice a small prefix-code calculation and a dictionary-decoding example before connecting them to real media formats.
3 questions · 3 with related videos. Matches are based on playlist titles; broader background matches are labeled.
What to study
- Lossless and lossy compression
- Prefix codes
- LZW dictionaries
Chapter playlists
Choose a playlist
Notes
How Image Compression Works
Leo Isikdogan · 6:52 · Background lecture
Image-compression background for comparing compressed representations; the exact-recovery distinction is stated in the answer.
1. Lossless versus lossy
Which kind of compression is appropriate when every original byte must be recovered, and why?
Use lossless compression, such as DEFLATE, which reconstructs the original byte sequence. Lossy media encoding trades exact reconstruction for a smaller representation under a quality target. A visually similar image is not proof that its original pixel values are preserved.
How Huffman Trees Work - Computerphile
Computerphile · 11:07
Choose a video · 2 lectures
Huffman and prefix-code explanations; this exercise supplies its own probabilities and bit string.
2. Prefix-code calculation
A code assigns A = 0, B = 10 and C = 11. For probabilities 1/2, 1/4 and 1/4, find the average length and decode 010110.
Average length = (1/2)×1 + (1/4)×2 + (1/4)×2 = 1.5 bits per symbol. Parse 0 | 10 | 11 | 0 to obtain ABCA. No codeword prefixes another, so decoding is unambiguous. Huffman coding constructs prefix codes from symbol frequencies.
7. Dynamic Dictionary - LZW Decoding
itechnica · 7:53
Supplementary LZW-decoding lecture; the simplified starting dictionary is specific to this exercise.
3. Small LZW decode
For a simplified LZW dictionary initially 0 = A and 1 = B, decode codes 0, 1, 2. Assign new entries from 2; omit format control codes.
Output A, then B; add entry 2 = previous string A plus the first character of B, giving AB. Code 2 then outputs AB. The result is ABAB; the next entry is BA. Real GIF adds clear/end codes and code-width rules omitted from this toy exercise.