Sebastian

main page  —  COMP 526 Applied Algorithmics

Unit 7: Compression

This is an archived version of this module from Spring 2020.
 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

  • lecture notes
  • slides
  • tutorial problems
  • Lecture 2020-03-17: Introduction

  • Lecture 2020-03-17: Character Encodings

  • Lecture 2020-03-17: Huffman Codes

  • Lecture 2020-03-23: Huffman Codes (part 2)

  • Lecture 2020-03-23: Run-Length Encoding

  • Lecture 2020-03-24: LZW encoding

  • Lecture 2020-03-24: LZW decoding

  • Lecture 2020-03-24: Move-to-front

  • Lecture 2020-03-24: Burrows-Wheeler-transform

  • Lecture 2020-04-20: Burrows-Wheeler-transform (part 2)

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