Entropy coding
Entropy coding is a family of lossless coding methods that use a probability model to reduce the expected encoded length of symbols or sequences.
Expectation: Shannon's source-coding limit concerns an average for a specified stochastic source, not a promise that every file becomes shorter. A byte-frequency histogram omits order and higher-order dependencies, so its entropy is not a universal minimum file size. [1]
Model: Huffman coding, arithmetic coding and asymmetric numeral systems are different constructions. Their decoding rules and probability models must agree with the encoder; the family name does not identify an interchangeable bitstream. [2] [3]
Accounting: Model descriptions, stopping rules, byte packing and framing can outweigh payload savings on a small object. The linked exact worksheet reports payload bits and packed bytes separately and excludes model and framing costs; it is not a production compressor or benchmark. [2] [4]
Denominator: Tunstall coding assigns fixed-width indices to variable-length phrases. Its long-stream payload rate divides bits per phrase by expected phrase length; averaging each phrase's bits-per-symbol ratio uses a different weighting. The worksheet makes this distinction with 128 bits for 148 symbols. [5] [4]
Relations
- related
- Arithmetic coding, Huffman coding, Asymmetric numeral systems, Lossless compression, Tunstall coding
Citations
- Claude E. Shannon: A Mathematical Theory of Communication (1948), sections 6 and 9, Theorem 9
- Ian H. Witten, Radford M. Neal and John G. Cleary: Arithmetic Coding for Data Compression, CACM 30(6), 520-540 (1987), DOI 10.1145/214762.214771
- Jarek Duda: Asymmetric numeral systems, arXiv:1311.2540v2 (2014), sections 1-2
- Hesela: exact rational interval worksheet, synthetic two-symbol messages
- Drmota, Reznik, Savari and Szpankowski: Precise Asymptotic Analysis of the Tunstall Code, ISIT 2006, sections I-II
Sources & caveats
- Primary-source synthesis and original exact-rational teaching arithmetic; no empirical compression ratio or universal file-size bound.