Constriction Library

entropy coders for research and production

The constriction library for Python and Rust provides a collection of highly optimized entropy coders with a clear and consistent API.

constriction speeds up the transition from research to production. Start by experimenting on a new entropy model with your favorite machine learning framework and constriction's simple Python API. Then turn your working prototype into an efficient standalone binary, library, or WebAssembly module with constriction's optimized and highly flexible Rust API.

Quick Start

For Data Scientists:

Install constriction for Python:

pip install --upgrade pip
pip install constriction

Then try out this example.

For Systems Engineers:

Use constriction in your Rust project:

[dependencies] # (in Cargo.toml)
constriction = "0.4.1"

Then try out this example.

Demos

Python Demo: Try out our jupyter notebooks with a simple encoding-decoding round trip or with a more elaborate text compression method using an autoregressive machine learning model.
Rust Demo: Try out this web app, which uses constriction in a WebAssembly module to run a custom compression codec directly in your web browser, i.e., on the client side (no installation required).

Simple encoding and decoding: Python example | Rust example
Defining a custom entropy model: Python example | Rust example 1 | Rust example 2
Compressing natural language with an autoregressive machine learning model: Python tutorial
Bits-back coding with a latent variable model: Python Problem Set | Solutions
Running a compression method as a client-side web app using WebAssembly: demo | source code

Lecture notes from a university course on data compression with and without deep probabilistic models (includes problem sets with solutions).
YouTube playlist of the above university course.
Paper with benchmark results of constriction's entropy coders (in Section 5.2), and with an explanation of internals of the ANS and "Chain" entropy coders: arXiv:2201.01741

What's Included?

	`constriction` for Python	`constriction` for Rust
Range Coding	(example)	(details)
Asymmetric Numeral Systems (ANS)	(example)	(example)
Chain Coding (experimental new method, see proposal)	(example)	(example)
Huffman Coding	(example)	(example)
Efficient and exactly invertible entropy models	(list)	(list)
Adapters for custom entropy models	(details)	(example)
Compatible with `scipy.stats`	(details)	n/a
Compile-time configuration of coder details (optional)		(details)
`no_std` support (e.g., for WebAssembly)	n/a	(demo)

Benchmarks

See detailed benchmark results in the readme.

In brief, constriction's stream codes are optimized for low bit rate and fast encoding and decoding. With default settings in a real-world scenario, the provided stream codes (both Range Coding and Asymmetric Numeral Systems) achieve a bit rate that is less than 0.1 % above the theoretically achievable minimum bit rate while being considerably faster than arithmetic coding. Users of constriction's Rust API can optionally specify more advanced coder and model settings at compile time to trade off between bit rate, memory usage, and run time (see documentation).

Cite

I'd appreciate attribution if you use constriction in your scientific work. You can cite the following paper, which announces constriction (Section 5.1) and analyzes its compression performance and runtime efficiency (Section 5.2):

R. Bamler, Understanding Entropy Coding With Asymmetric Numeral Systems (ANS): a Statistician's Perspective, arXiv preprint arXiv:2201.01741.

BibTex: (copy to clipboard) @article{bamler2022constriction, title = {Understanding Entropy Coding With Asymmetric Numeral Systems (ANS): a Statistician's Perspective}, author = {Bamler, Robert}, journal = {arXiv preprint arXiv:2201.01741}, year = {2022} }

Contribute

Issues and pull requests are very welcome in our code repository.

What's With the Name?

constriction is a compression library with bindings for Rust and Python. Pythons are a family of nonvenomous snakes that subdue their prey by “compressing” it, a method known as constriction.