main page — COMP 526 Applied Algorithmics
Unit 5: Compression
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 5-1 (2023-10-27):
§5.1 Compression context: terminology, Kolmogorov complexity
- Video 5-2 (2023-10-27):
§5.2 Character Encodings
- Video 5-3 (2023-11-02):
§5.3 Huffman codes
- Video 5-4 (2023-11-02):
§5.4 Entropy and Huffman codes
- Video 5-5 (2023-11-03):
§5.5 Run-length encoding
- Video 5-6 (2023-11-03):
§5.6 Lempel-Ziv-Welch encoding
- Video 5-8 (2023-11-03):
§5.7 Lempel Ziv Welch decoding
- Video 5-9 (2023-11-03):
§5.8 Move-to-front transform
- Video 5-9 (2023-11-16):
§5.9 Burrows-Wheeler transform
- Video 5-10 (2023-11-16):
§5.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 analysis of BWT based compression is found in here:
- Manzini: An analysis of the Burrows-Wheeler transform (2001), Journal of the ACM
- Kempa, Kociumaka: Resolution of the Burrows-Wheeler Transform Conjecture (2022), Communication of the ACM
The presentation of the unit is inspired by material prepared for the module