Home › Compression

Compression

Entropy coding, LZ coding, transforms and integer/float codecs.

Entropy coding

Coding symbols near their information content.

Huffman coding

Optimal prefix code with whole-bit codeword lengths; table-driven decoding at about one symbol per few cycles, the entropy stage of DEFLATE, JPEG and zstd literals.

build O(n log n) for n symbols; encode and decode O(1) per symbol with a 2^L-entry table

Arithmetic coding

low

Encodes a whole message as one number in [0,1), spending fractional bits per symbol; pairs with adaptive context models for the best ratios.

O(1) per binary decision (one multiply, one compare); O(log alphabet) decisions per symbol with a bit tree

Asymmetric numeral systems (ANS)

low

Entropy coder that packs fractional bits into a single integer state; arithmetic-coding ratio at Huffman-like speed, the entropy stage of zstd and LZFSE.

O(1) per symbol (rANS - one multiply, one table lookup; tANS - one table lookup), table build O(2^R)

context modeling

Planned.

LZ / dictionary coding

Replacing repeats with back-references.

LZ77

low

Replace repeated byte strings with (distance, length) back-references into a sliding window; the parsing stage of gzip, LZ4, zstd, Brotli and xz.

decode O(n); encode O(n·chain) with hash chains, O(n log w) with binary-tree match finders

LZ4

low

Byte-aligned LZ77 with no entropy stage; compresses at hundreds of MB/s and decompresses at several GB/s per core, for when speed beats ratio.

compress O(n) with one hash probe per position; decompress O(n) memory copies

Zstandard (zstd)

low

LZ77 plus Huffman and FSE entropy coding, with levels from LZ4-like speed to xz-like ratio, all decoding at about 1-2 GB/s.

decode O(n), level-independent; encode O(n) at fast levels to O(n log w) with binary-tree optimal parsing

Dictionary compression

low

Prime the compressor with shared, pre-trained content so small messages can reference it; often 2-5x better ratio on sub-KB records.

training O(total sample size); per message same as the base codec, plus dictionary load (avoid by preparing it once)

deflate

Planned.

Transforms

Reshaping data so it compresses better.

Burrows-Wheeler transform (BWT)

low

Reversible permutation that sorts every character by the context following it, clustering equal bytes into runs; the core of bzip2 and of FM-index text search.

forward O(n) with linear suffix sorting (SA-IS); inverse O(n) time, but one random memory access per byte

Delta encoding

low

Store differences between consecutive values instead of the values, turning sorted IDs, timestamps and counters into small numbers that pack into few bits.

encode and decode O(n); decode is a prefix sum (1 add/element, vectorizable)

run length encoding

Planned.

prefix compression

Planned.

dictionary encoding

Planned.

vector quantization

Planned.

Integer codecs

Compressing integer arrays and IDs.

Varint (LEB128)

low

Variable-length integers in 7-bit groups with a continuation bit; small numbers take 1 byte, the wire format of Protobuf, WebAssembly and DWARF.

O(bytes) per value, 1-10 bytes for u64; decode is a short loop with a data-dependent branch per byte

Bit packing and PFOR

low

Store blocks of integers with exactly b bits each and patch rare outliers separately (PFOR); the fastest integer codec family, billions of values per second.

O(n) encode and decode; decode is branch-free shifts and masks, about 1 cycle or less per value with SIMD