Entropy Coding

Huffman coding is a greedy algorithm that constructs a variable-length prefix code for a set of symbols based on their frequencies. It builds a binary tree where more frequent symbols have shorter codes.

• Algorithm: Start with a forest of nodes (one per symbol). Repeatedly merge the two nodes with the lowest probability, assigning a 0 or 1 to each branch, until a single tree remains.
• Optimality: Produces an optimal prefix code for a given symbol-by-symbol probability distribution.
• Use Case: Foundational algorithm in DEFLATE (used in PNG, GZIP) and is a common final stage in compression pipelines after other techniques like LZ77.

Arithmetic coding encodes an entire message into a single fractional number in the interval [0, 1). It is more efficient than Huffman coding as it can achieve fractional bits per symbol, closely approaching the Shannon entropy limit.

• Mechanism: The algorithm recursively subdivides the current probability interval based on the cumulative probability of the next symbol. The final interval uniquely identifies the message.
• Advantage: Excels with highly skewed probability distributions and small alphabets, where Huffman's integer-bit constraint causes inefficiency.
• Application: Used in advanced compression standards like JPEG 2000, H.264/AVC (CABAC), and FLAC for audio.

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).

Quantization reduces the numerical precision of a model's weights and activations (e.g., from 32-bit floating-point to 8-bit integers). This directly decreases the memory footprint and can accelerate inference on supported hardware.

• Post-Training Quantization (PTQ): Applied after training with minimal calibration data.
• Quantization-Aware Training (QAT): Simulates quantization during training for higher accuracy retention.
• Critical for deploying large models on edge devices with constrained memory.

Pruning removes less important weights, neurons, or entire layers from a neural network to create a smaller, more efficient model.

• Unstructured Pruning: Individual weights are set to zero, creating a sparse model.
• Structured Pruning: Removes entire channels, filters, or layers, leading to direct hardware speedups.
• Often followed by fine-tuning to recover any lost accuracy. A key step in the deep compression pipeline.

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.