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
- 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
- Video 7-1 (2022-03-21):
§7.1 Compression context
- Video 7-2 (2022-03-21):
§7.2 Character Encodings
- Video 7-3 (2022-03-21):
§7.3 Huffman codes
- Video 7-4 (2022-03-24):
§7.4 Entropy and Huffman codes
- Video 7-5 (2022-03-24):
§7.5 Run-length encoding
- Video 7-6 (2022-03-24):
§7.6 Lempel-Ziv-Welch encoding
- Video 7-7 (2022-03-28):
§7.7 Lempel Ziv Welch decoding
- Video 7-8 (2022-03-28):
§7.8 Move-to-front transform
- Video 7-9 (2022-03-28):
§7.9 Burrows Wheeler transform
- Video 7-10 (2022-03-28):
§7.10 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