Entropy Coding

Range coding is a practical implementation variant of arithmetic coding that uses integer arithmetic instead of floating-point, avoiding patent issues and offering computational benefits. It is functionally equivalent to arithmetic coding.

• Key Difference: Operates on integers within a specified range (e.g., 32-bit), renormalizing the range to prevent underflow, which maps directly to efficient bitstream output.
• Performance: Often faster in software implementations due to the use of integer operations and lookup tables.
• Usage: The core of compression in formats like 7-Zip (LZMA) and BZIP2 (after the Burrows-Wheeler Transform).

Asymmetric Numeral Systems (ANS) is a modern entropy coding technique that combines the speed of Huffman coding with the compression ratio of arithmetic coding. It operates as a finite state machine, mapping information into a single natural number.

• Principle: Instead of subdividing an interval, ANS uses a table (tANS variant) to map a symbol and the current state to a new state, outputting bits when the state exceeds a threshold.
• Benefits: Offers better computational efficiency than arithmetic coding and is more amenable to hardware implementation. It allows for simultaneous encryption via state manipulation.
• Adoption: The foundation of the compression in Facebook's Zstandard (zstd) and Apple's LZFSE, making it a state-of-the-art choice for high-speed compression.

Run-Length Encoding (RLE) is a simple entropy coding method that compresses sequences of identical symbols (runs) into a single symbol and a count. Its efficiency is highly dependent on data redundancy.

• Process: Scans data, replacing consecutive repetitions of the same value with a count-value pair (e.g., AAAAABBB becomes 5A3B).
• Characteristics: It is a form of dictionary compression with a 1-symbol dictionary. It is lossless but ineffective for data without long runs.
• Application: Used as a basic compression layer in bitmap image formats (BMP, PCX) and is often a preprocessing step in more complex codecs like JPEG.

Golomb coding is a parameterized entropy code optimal for geometric distributions (where small values are much more frequent). Exponential-Golomb coding is a special case used extensively in video coding.

• Golomb Coding: Encodes an integer n using a tunable parameter M. The code consists of a unary prefix (n / M) and a binary remainder.
• Exponential-Golomb: Uses a parameter k to define groups of sizes that grow exponentially. The code is a unary prefix for the group index and a fixed-length suffix.
• Primary Use: Exponential-Golomb codes are the standard for encoding motion vector differences and other syntax elements in video compression standards like H.264 and H.265 (HEVC).

A compression technique where a smaller, faster student model is trained to mimic the behavior of a larger, more accurate teacher model. The student learns from the teacher's logits (soft targets) and the ground truth labels.

• Transfers generalizable knowledge rather than just function approximation.
• Enables compact models suitable for on-device deployment.
• Can be applied to ensembles, where a single student learns from multiple teachers.

Techniques to reduce the storage size and dimensionality of dense vector embeddings, which are core to semantic search in agentic memory systems.

• Quantization: Applying 8-bit or binary quantization to embedding vectors.
• Dimensionality Reduction: Using PCA or other methods to project high-dimensional embeddings into a lower-dimensional space.
• Product Quantization (PQ): Splits vectors into subvectors and quantizes them into codebooks, enabling efficient approximate nearest neighbor search.

A data format or model state where most elements are zero. Leveraging sparsity is a powerful method for compression and computational savings.

• Sparse Matrices/Tensors: Store only non-zero values and their indices.
• Enables sparse computation kernels that skip operations on zeros.
• Found in pruned networks, sparse attention patterns, and compressed sensing. Hardware support (e.g., NVIDIA's Sparsity) is growing.

A family of lossless data compression algorithms (e.g., LZ77, LZW) that replace repeated sequences with references to a dictionary of previously seen phrases.

• The core of ubiquitous formats like ZIP, GZIP, and PNG.
• Lempel-Ziv-Welch (LZW): Builds the dictionary adaptively during compression/decompression.
• While generic, it can be applied to compress model checkpoints, log files, or serialized agent memory states.