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 Spring 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 (2022-03-21, 25:37): §7.1 Compression context
    Chapters1:03 Objectives
    2:29 Subsections
    2:56 Why compression
    5:43 Questions
    6:13 Terminology
    10:56 Different compression methods
    12:40 Compression ratio
    15:53 Ultimate compression
  • Video 7-2 (2022-03-21, 25:46): §7.2 Character Encodings
    Chapters0:44 Character encodings
    3:33 Fixed-length codes - Discussion
    6:18 Clicker Question
    9:43 Variable-length codes - UTF-8
    14:39 Pitfall in variable-length codes
    18:49 Code tries
    24:07 Who decodes the decoder?
  • Video 7-3 (2022-03-21, 25:05): §7.3 Huffman codes
    Chapters0:14 Character frequencies
    1:25 Huffman coding
    7:32 Huffman's algorithm - Example
    15:41 Encoding with Huffman code
    18:10 Huffman code - Optimality
  • Video 7-4 (2022-03-24, 36:39): §7.4 Entropy and Huffman codes
    Chapters9:13 Arithmetic Coding
    13:40 Crafts Inequality
    16:24 Gibbs Inequality
    17:52 Upper Bound
    32:48 Huffman Coding
  • Video 7-5 (2022-03-24, 23:17): §7.5 Run-length encoding
    Chapters0:19 Beyond Character Encoding
    8:09 Clicker Question
    10:00 Elias codes
    18:07 Run-length encoding - Examples
    20:41 Run-length encoding - Discussion
  • Video 7-6 (2022-03-24, 14:50): §7.6 Lempel-Ziv-Welch encoding
    Chapters3:50 Structure
    5:36 Variant
    8:13 Example
    13:19 Code
  • Video 7-7 (2022-03-28, 28:01): §7.7 Lempel Ziv Welch decoding
    Chapters0:17 LZW encoding - Example
    11:08 LZW decoding-Bootstrapping
    13:15 LZW decoding - Example continued
    13:53 LZW decoding-Code
    19:37 Clicker Question
    22:51 LZW-Discussion
    27:39 Compression summary
  • Video 7-8 (2022-03-28, 17:24): §7.8 Move-to-front transform
    Chapters3:05 Text transformations
    4:30 Movetofront transform
    8:10 Alphabetic order
    11:05 Code
  • Video 7-9 (2022-03-28, 21:01): §7.9 Burrows Wheeler transform
    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 (2022-03-28, 8:26): §7.10 Inverse BWT
    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