Symbols occur at different frequencies. Shorter codes for frequent symbols can reduce the cost. The decoder also needs to know which codes were used, so code lengths must be described.
Locate this topic on the global map ↗The first 2 chapters explain algorithms, data layouts, and optimizations. The final chapter connects the proof argument. Read in order or enter from a familiar stage.
- 01IMPLEMENTATION DETAIL↗
Frequencies, heaps, and coding trees
Give frequent symbols shorter codes and follow frequencies into a coding tree.
- 02IMPLEMENTATION DETAIL↗
Length repair and canonical codes
Reconstruct the same codes from lengths while meeting the format’s length limits.
- 03PROOF ARGUMENT↗
The coding-construction proof
Connect the constructed tree, distinguishable codes, and the bits actually written.