Name: "Hacking Data Compression" course
Author: Andy McFadden
Written: October 1992 - July 1993
Summary: 12-part course on data compression, with sample source code
for the Apple IIgs
Description:
This is a 12-part course I did for the "Apple II University" on GEnie,
back when GEnie was a major online service. This was written while
I was working on HardPressed (and working full time as a software
engineer... I was pretty busy).
The ZIP file contains twelve SHK files, one per lesson.
Lesson 1: Introduction
Course overview and introduction to compression concepts.
Lesson 2: Basics
Discussion of RLE and differential coding.
Lesson 3: Somewhat Clever Ad-Hoc Schemes
Simple character encodings, MTF, digrams; intro to higher-order
models.
Lesson 4: Shannon, Fano, and Huffman
Explanation of probability encoding.
Lesson 5: Adaptive Encoding
Adaptive vs static methods, Splay trees, adaptive Huffman.
Lesson 6: Arithmetic Coding
How arithmetic encoding works; includes the CACM sources and
variations.
Lesson 7: Ziv and Lempel
Discussion of LZ77 and LZ78.
Lesson 8: LZW
Detailed explanation of the LZW algorithm.
Lesson 9: NuFX and ShrinkIt
Discussion about the compression used in ShrinkIt.
Lesson 10: LZSS
Detailed explanation of the LZSS algorithm.
Lesson 11: LZH, LZARI, and LZB
How to improve LZSS with Huffman, arithmetic, and unary coding.
Lesson 12: HardPressed(tm)
How to write compression modules for HardPressed.
The lesson files are plain ASCII text. The sample code is (usually) in
both C and 65816 assembly. The C code should work on most platforms,
and the explanations of compression theory and the algorithms should
apply no matter what platform you're on.