Sebastian Wild Algorithms Group · Universität Marburg

main page  —  COMP 526 Efficient Algorithms

Unit 7: Compression

This is an archived version of this module from Fall 2022.
 Click here for the current iteration.

This unit covers classic compression techniques; we discuss

  • character encodings (ASCII, UTF-8)
  • Huffman codes
  • run-length encoding (RLE)
  • Elias gamma codes
  • Lempel-Ziv-Welch (LZW)
  • move-to-front (MTF) text transform
  • Burrows-Wheeler transform (BWT)

including their properties and what types of redundancies in data they can exploit.

Learning outcomes

  1. Understand the necessity for encodings and know ASCII and UTF-8 character encodings.
  2. Understand (qualitatively) the limits of compressibility.
  3. Know and understand the algorithms (encoding and decoding) for Huffman codes, RLE, Elias codes, LZW, MTF, and BWT, including their properties like running time complexity.
  4. Select and adapt (slightly) a compression pipeline for specific type of data.

Material

  • slides

  • lecture notes

  • Video 7-1 · transcript (2022-11-28, 32:31): §7.1 Compression context: terminology, Kolmogorov complexity
    Chapters1:04 Learning Outcomes
    2:17 Overview
    6:30 Terminology
    13:59 What is a good encoding scheme?
    19:40 Clicker Question
    24:10 Limits of algorithmic compression
    28:46 What makes data compressible?
  • Video 7-2 · transcript (2022-11-28, 9:27): §7.2 Character Encodings
    Chapters1:29 Fixed-length codes food-length codes are the simplest type of character encodings
    2:30 Fixed-length codes - Discussion
    4:26 Clicker Question
    7:41 Variable-length codes - UTF-8
  • Video 7-3 · transcript (2022-11-30, 10:12): §7.2 Character Encodings
  • Video 7-4 · transcript (2022-11-30, 25:40): §7.3 Huffman codes
    Chapters1:56 Huffman coding
    7:03 Huffman's algorithm - Example
    12:41 Huffman tree-tie breaking
    15:22 Encoding with Huffman code
    18:10 Huffman code - Optimality
  • Video 7-5 · transcript (2022-11-30, 21:06): §7.4 Entropy and Huffman codes
    Chapters10:59 Entropy and Huffman codes [2]
    14:50 Clicker Question
    17:43 Huffman coding - Discussion
  • Video 7-6 · transcript (2022-11-30, 22:48): §7.5 Run-length encoding
    Chapters0:52 Beyond Character Encoding
    6:42 Elias codes
    15:25 Clicker Question
    16:50 Run-length encoding - Examples
    20:39 Run-length encoding - Discussion
  • Video 7-7 · transcript (2022-11-30, 15:47): §7.6 Lempel-Ziv-Welch encoding
    Chapters0:36 Warmup
    2:36 Clicker Question
    4:12 Lempel-Ziv Compression
    9:52 LZW encoding-Example
    13:47 LZW encoding-Code
  • Video 7-8 · transcript (2022-12-05, 26:35): §7.7 Lempel Ziv Welch decoding
    Chapters3:48 LZW decoding-Example
    8:14 LZW decoding-Bootstrapping
    10:47 LZW decoding - Code
    13:09 LZW decoding - Example continued
    16:44 Clicker Question
    20:23 LZW-Discussion
    25:51 Compression summary
  • Video 7-9 · transcript (2022-12-05, 18:52): §7.8 Move-to-front transform
    Chapters0:19 Text transformations
    3:37 Move to Front
    7:51 Clicker Question
    13:58 MTF - Example
    16:39 MTF - Discussion
  • Video 7-9 · transcript (2022-12-07, 21:01): §7.9 Burrows-Wheeler transform
    This is an archive video covering the same material; audio in recording was broken.
    Chapters0:33 BurrowsWheeler transform
    4:18 Burst Wheeler transform
    6:27 Example
    8:21 Question
    10:45 Solution
    16:57 In action
    18:18 Results
  • Video 7-10 · transcript (2022-12-07, 8:26): §7.10 Inverse BWT
    This is an archive video covering the same material; audio in recording was broken.
    Chapters3:23 Inverse BWT - The magic revealed
    6:51 BWT - Discussion
    8:02 Summary of Compression Methods

Further reading and sources

There is no textbook that covers all topics, but parts can be found in the following sources, all of which cover much more than the topics I selected.

Character encodings, Huffman codes, LZW:

The exposition of BWT is my own.

The presentation of the unit is inspired by material prepared for the module

Unit 6  ⋅  Syllabus  ⋅  Unit 8