main page — COMP 526 Efficient Algorithms
Unit 7: Compression
This is an archived version of this module from Spring 2021.
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
- Understand the necessity for encodings and know ASCII and UTF-8 character encodings.
- Understand (qualitatively) the limits of compressibility.
- 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.
- Select and adapt (slightly) a compression pipeline for specific type of data.
Material
- slides
- lecture notes
- Video 7-1 (2021-04-20):
§7.1 Compression context
- Video 7-2 (2021-04-20):
§7.2 Character Encodings
- Video 7-3 (2021-04-20):
§7.3 Huffman codes
- Video 7-4 (2021-04-21):
§7.3 Entropy
- Video 7-5 (2021-04-21):
§7.4 Run-length encoding
- Video 7-6 (2021-04-21):
§7.5 Lempel Ziv Welch introduction
- Video 7-7 (2021-04-27):
§7.5 Lempel Ziv Welch
- Video 7-8 (2021-04-27):
§7.6 Move to front text transformation
- Video 7-9 (2021-04-27):
§7.7 Burrows Wheeler transform
- Video 7-10 (2021-04-28):
§7.7 Inverse BWT
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:
- Sedgewick, Wayne: Algorithms 4th edition (2011), Pearson
Note: they discuss RLE, but not using Elias codes for run lengths!
The exposition of BWT is my own.
The presentation of the unit is inspired by material prepared for the module