main page — CS 566 Efficient Algorithms
Unit 7: Text 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
— to be added —
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