Composable entropy coding primitives for research and production (Python and Rust).
Project description
Composable Entropy Coding Primitives for Research and Production
The constriction
library provides a set of composable implementations of entropy coding
algorithms. It has APIs for both the Python and Rust languages and it focuses on
correctness, versatility, ease of use, compression performance, and computational
efficiency. The goals of constriction
are to three-fold:
- to facilitate research on novel lossless and lossy compression methods by providing a
composable set of entropy coding primitives rather than a rigid implementation of a
single preconfigured method; in compression research, different applications put
different requirements on the entropy coding method. For example, you may prefer a Range
Coder for an autoregressive entropy model (because it preserves the order of encoded
symbols), but you may prefer an ANS Coder for a hierarchical entropy model (because it
supports bits-back coding). With many other libraries, swapping out a Range Coder for an
ANS Coder would mean that you not only have to find and learn how to use new library, but
you would also have to port the part of your code that represents probabilistic entropy
models so that it adheres to the rules of the new library. By contrast, the composable
architecture of
constriction
lets you seamlessly swap out individual components of your compression pipeline (such as the core entropy coding algorithm) independently from other components (such as the fixed-point representation of entropy models or the strategy for dealing with zero probability symbols). - to simplify the transition from research code to reliable software products by
exposing the exact same functionality via both a Python API (for rapid prototyping on
research code) and a Rust API (for turning successful prototypes into production); This
approach bridges the gap between two communities that have vastly different requirements
on their software development tools: while data scientists and machine learning
researchers need the quick iteration cycles that scripting languages like Python
provide, real-world compression codecs that are to be used outside of laboratory
conditions have to be implemented in a compiled language that runs fast and that doesn't
require setting up a complex runtime environment with lots of dependencies. With
constriction
, you can seamlessly turn your Python research code into a high-performance standalone binary, library, or WebAssembly module. By default, the Python and Rust API are binary compatible, so you can gradually port one component at a time without breaking things. On top of this, the Rust API provides optional fine-grained control over issues relevant to real-world deployments such as the trade-off between compression effectiveness, memory usage, and run-time efficiency, as well as hooks into the backing data sources and sinks, while preventing accidental misuse through Rust's powerful type system. - to serve as a teaching resource by providing a collection of several complementary entropy coding algorithms within a single consistent framework, thus making the various algorithms easily discoverable and comparable on practical examples; additional teaching material is being made publicly available as a by-product of an ongoing university course on data compression with deep probabilistic models.
For an example of a compression codec that started as research code in Python and was then
deployed as a fast and dependency-free WebAssembly module using constriction
's Rust API,
have a look at The Linguistic Flux
Capacitor.
Project Status
We currently provide implementations of the following entropy coding algorithms:
- Asymmetric Numeral Systems (ANS): a fast modern entropy coder with near-optimal compression effectiveness that supports advanced use cases like bits-back coding.
- Range Coding: a computationally efficient variant of Arithmetic Coding, that has essentially the same compression effectiveness as ANS Coding but operates as a queue ("first in first out"), which makes it preferable for autoregressive models.
- Chain Coding: an experimental new entropy coder that combines the (net) effectiveness of stream codes with the locality of symbol codes; it is meant for experimental new compression approaches that perform joint inference, quantization, and bits-back coding in an end-to-end optimization. This experimental coder is mainly provided to prove to ourselves that the API for encoding and decoding, which is shared across all stream coders, is flexible enough to express complex novel tasks.
- Huffman Coding: a well-known symbol code, mainly provided here for teaching purpose; you'll usually want to use a stream code like ANS or Range Coding instead since symbol codes can have a considerable overhead on the bitrate, especially in the regime of low entropy per symbol, which is common in machine-learning based compression methods.
Further, constriction
provides implementations of common probability distributions in
fixed-point arithmetic, which can be used as entropy models in either of the above stream
codes. The library also provides adapters for turning custom probability distributions into
exactly invertible fixed-point arithmetic.
The provided implementations of entropy coding algorithms and probability distributions are
extensively tested and should be considered reliable (except for the still experimental
Chain Coder). However, their APIs may change in future versions of constriction
if more
user experience reveals any shortcomings of the current APIs in terms of ergonomics. Please
file an issue if you run into a
scenario where the current APIs are suboptimal.
Quick Start Guides And Examples in Python and Rust
Python
The easiest way to install constriction
for Python is via pip
(the following command
also installs scipy
, which is not required but useful if you want to use constriction
with custom probability distributions):
pip install constriction numpy scipy
Then go ahead and use it:
import constriction
import numpy as np
# Let's use a Range Coder in this example. Constriction also provides an ANS
# Coder, a Huffman Coder, and an experimental new "Chain Coder".
encoder = constriction.stream.queue.RangeEncoder()
# Define some data and a sequence of entropy models. We use quantized Gaussians
# here, but you could also use other models or even provide your own.
min_supported_symbol, max_supported_symbol = -100, 100
symbols = np.array([23, -15, 78, 43, -69], dtype=np.int32)
means = np.array([35.2, -1.7, 30.1, 71.2, -75.1], dtype=np.float64)
stds = np.array([10.1, 25.3, 23.8, 35.4, 3.9], dtype=np.float64)
# Encode the symbols and get the compressed data.
encoder.encode_leaky_gaussian_symbols(
symbols, min_supported_symbol, max_supported_symbol, means, stds)
compressed = encoder.get_compressed()
print(compressed)
# Create a decoder and recover the original symbols.
decoder = constriction.stream.queue.RangeDecoder(compressed)
reconstructed = decoder.decode_leaky_gaussian_symbols(
min_supported_symbol, max_supported_symbol, means, stds)
assert np.all(reconstructed == symbols)
There's a lot more you can do with constriction
's Python API. Please check out the Python
API Documentation.
Rust
Add this line to your Cargo.toml
:
[dependencies]
constriction = "0.1.2"
probability = "0.17" # Not strictly required but used in many code examples.
If you compile in no_std
mode then you have to deactivate constriction
's default
features (and you can't use the probability
crate):
[dependencies]
constriction = {version = "0.1.2", default-features = false} # for `no_std` mode
Then go ahead and use it:
use constriction::stream::{model::DefaultLeakyQuantizer, stack::DefaultAnsCoder, Decode};
// Let's use an ANS Coder in this example. Constriction also provides a Range
// Coder, a Huffman Coder, and an experimental new "Chain Coder".
let mut coder = DefaultAnsCoder::new();
// Define some data and a sequence of entropy models. We use quantized Gaussians here,
// but `constriction` also provides other models and allows you to implement your own.
let symbols = vec![23i32, -15, 78, 43, -69];
let quantizer = DefaultLeakyQuantizer::new(-100..=100);
let means = vec![35.2f64, -1.7, 30.1, 71.2, -75.1];
let stds = vec![10.1f64, 25.3, 23.8, 35.4, 3.9];
let models = means.iter().zip(&stds).map(
|(&mean, &std)| quantizer.quantize(probability::distribution::Gaussian::new(mean, std))
);
// Encode symbols (in *reverse* order, because ANS Coding operates as a stack).
coder.encode_symbols_reverse(symbols.iter().zip(models.clone())).unwrap();
// Obtain temporary shared access to the compressed bit string. If you want ownership of the
// compressed bit string, call `.into_compressed()` instead of `.get_compressed()`.
println!("Encoded into {} bits: {:?}", coder.num_bits(), &*coder.get_compressed().unwrap());
// Decode the symbols and verify correctness.
let reconstructed = coder.decode_symbols(models).collect::<Result<Vec<_>, _>>().unwrap();
assert_eq!(reconstructed, symbols);
There's a lot more you can do with constriction
's Rust API. Please check out the Rust API
Documentation.
Compiling From Source
Users of constriction
typically don't need to manually compile the library from source.
Just install constriction
via pip
or cargo
as described in the above quick start guides.
Contributors can compile constriction
manually as follows:
- Prepare your system:
- If you don't have a Rust toolchain, install one as described on https://rustup.rs
- If you already have a Rust toolchain, make sure it's on version 1.51 or later. Run
rustc --version
to find out andrustup update stable
if you need to update.
git clone
the repository andcd
into it.- To compile the Rust library:
- compile in development mode and execute all tests:
cargo test
- compile in release mode (i.e., with optimizations) and run the benchmarks:
cargo bench
- compile in development mode and execute all tests:
- If you want to compile the Python module:
- install poetry.
- install Python dependencies:
cd
into the repository and runpoetry install
- build the Python module:
poetry run maturin develop '--cargo-extra-args=--features pybindings'
- run Python unit tests:
poetry run pytest tests/python
- start a Python REPL that sees the compiled Python module:
poetry run ipython
Contributing
Pull requests and issue reports are welcome. Unless contributors explicitly state otherwise at the time of contributing, all contributions will be assumed to be licensed under either one of MIT license, Apache License Version 2.0, or Boost Software License Version 1.0, at the choice of each licensee.
There's no official guide for contributions since nobody reads those anyway. Just be nice to other people and act like a grown-up (i.e., it's OK to make mistakes as long as you strive for improvement and are open to respectfully phrased opinions of other people).
License
This work is licensed under the terms of the MIT license, Apache License Version 2.0, or
Boost Software License Version 1.0. You can choose between one of them if you use this work.
See the files whose name start with LICENSE
in this directory. The compiled python
extension module is linked with a number of third party libraries. Binary distributions of
the constriction
python extension module contain a file LICENSE.html
that includes all
licenses of all dependencies (the file is also available
online).
What's With the Name?
Constriction is a library of compression primitives 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.
Project details
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distributions
Built Distributions
Hashes for constriction-0.1.4-cp310-none-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 89ee7b3026b5817b64a541eb7ed5b5fbff3c8f0ab9170e1703bfaf170e7232c0 |
|
MD5 | ca9b9605ce7a58b294b3b199391448a2 |
|
BLAKE2b-256 | 5850e00f0c0abe1963f5092bbb60ec6d83201e4e6cfc53534b2ae5c98c7f18ed |
Hashes for constriction-0.1.4-cp310-cp310-manylinux2010_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | ea7bd32cc731c8c9f06d4b751bd058f5f45161ba040ba30e9057d1391aa2987b |
|
MD5 | 230f2e6d42c103fbb82bcc666af6f203 |
|
BLAKE2b-256 | 0a0e6952188f2bc2f8d45f91c4fb26c6f1f5817e2f72ef2698bcdfa7912042f6 |
Hashes for constriction-0.1.4-cp310-cp310-macosx_10_9_universal2.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 3a6a57b509dbfddb39d9f58dffe278561fd477c3a4aae630959e103511002767 |
|
MD5 | 1e87b44249968111d542051672c3f841 |
|
BLAKE2b-256 | 2628a543ee8570724b51e9d19011a3a8df2e7d8027f3ce10e4968f5044c905ac |
Hashes for constriction-0.1.4-cp310-cp310-macosx_10_7_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 44d4b0ca3b0652c38afc6fe17cfbd3cb2fd7e923ec49bcc77107580623632081 |
|
MD5 | 6d0bb4367ee7223c779fce41910542c4 |
|
BLAKE2b-256 | 37dde7bbf45cc6966eb80f4c7c1403a3f6c1a70dfe0fb28980109021cb54a76b |
Hashes for constriction-0.1.4-cp39-none-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | ed386536ea0a3bb16123d433cfe656b984ecb002b29b066866262a1969f346e2 |
|
MD5 | 5b81b4565353522a86e5b8d53c915d2c |
|
BLAKE2b-256 | d9f8e5788ccc23f1221edbfba049178198a2732200986b626a13d73475874a80 |
Hashes for constriction-0.1.4-cp39-cp39-manylinux2010_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 810750df5e2f949ee5b6e829147df37cc8afce5cd46ea8739c9abc558fbf5570 |
|
MD5 | 63ae2e496fe83f47fb5c01feee7a8883 |
|
BLAKE2b-256 | cccd91a2c8ad78aad0fa32cdc3c2f9432d2f6565bee4a2441b8d86f43ef613c9 |
Hashes for constriction-0.1.4-cp39-cp39-macosx_10_9_universal2.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | bdf02582adadd38ee2aa5096ee589dcd6ed7594565cac891ce149f78921c5a83 |
|
MD5 | 5b7082be44ce13b0636440952cf81c67 |
|
BLAKE2b-256 | 20793f7df667d6de4518234f6de79e5a0f4548de326da4d65fe3cb95656e40f6 |
Hashes for constriction-0.1.4-cp39-cp39-macosx_10_7_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 6db4402b2f00e94e86c9c52028e1c53dcb661e9a419a030251870f1cb4fc4a04 |
|
MD5 | d0a39b5619096ddb4fab2f795b6fbb7e |
|
BLAKE2b-256 | e17e4ff454ca2ec940a4853ccdc96d0f1956e6a2c39e00bb660960af221e2de7 |
Hashes for constriction-0.1.4-cp38-none-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | ce61c578f73f8f271413f5b4511132dc6778f2a9b7501656eb96405d7b019d75 |
|
MD5 | ac6e585f0d4e66f3a4bf89c309ef59bb |
|
BLAKE2b-256 | 2a3bd3b2556b2626263ce0c2a9f85607bd2d084f1d6bd61cb26a8214816228bb |
Hashes for constriction-0.1.4-cp38-cp38-manylinux2010_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 7ee03f2f0b5b3ad15f9606518ff1c0f3dcc1edd9421f8f23d1a509dc0a29ef2f |
|
MD5 | ebb643eefbb83e75c50e86742fe628d1 |
|
BLAKE2b-256 | 298e2c854a9aee374557ee32bf8f421f1ba6db431d24efc3ad797556f1ba69d2 |
Hashes for constriction-0.1.4-cp38-cp38-macosx_10_9_universal2.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 7852b8f2c849d38819c2c2d08cc92d555ef44aa230abacb4ec4a85c6e6c4e9b7 |
|
MD5 | 18e7765fdbb85f0a398402e4027cb097 |
|
BLAKE2b-256 | b08613e190ef858ebf1cd8940ed9ad9325bfddd50f186b48bfeb34cf446b4ac3 |
Hashes for constriction-0.1.4-cp38-cp38-macosx_10_7_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 6bd737bae4ee94c6bff2aa8b702beaa734141e5d9cc200a3e6200799cc28e197 |
|
MD5 | be29be1d7ef0bcc95da6b9f1e4401b31 |
|
BLAKE2b-256 | 3c27a51902f885f7e34c44b869c915c27a87e50683a5518277ca37b10f7f3898 |
Hashes for constriction-0.1.4-cp37-none-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 6ff5757fb5de08a419cf42b247e0aca5dddea840a668d0c63d8e6fab8b41b4cd |
|
MD5 | 58ed2aefd22fb3489bab96eeb9efb24f |
|
BLAKE2b-256 | b5bfaee3a5cce597864d3596cc9ef0fc81a0a8847146b06310b9a5395fca5efd |
Hashes for constriction-0.1.4-cp37-cp37m-manylinux2010_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 12232d062e0aef59d260837ae2a918ba07a1ea296b0e4cc160e88e38fc82127b |
|
MD5 | f2d765d11ac74423f3c2a0b8e4215746 |
|
BLAKE2b-256 | 44d72aa60d7c974dc9818792918628afe3deb00f93a7e517384d0d9a2f30812f |
Hashes for constriction-0.1.4-cp37-cp37m-macosx_10_9_universal2.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 8235df6b534c0bcf4542eba16868105dac14291b9ad7ef7b58559c315d4ad9c7 |
|
MD5 | dafe6258aeda75296e80cb4f520a9678 |
|
BLAKE2b-256 | 32da6eaef7d7cb85c94b706ab0de1adf6681638b42bbba308bf343b9b31a4fc0 |
Hashes for constriction-0.1.4-cp37-cp37m-macosx_10_7_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 70a7273562a3bcc8ceae43c85e73dce81f33c07a6759d0ff80b7b8beb0177d79 |
|
MD5 | 12fcd4a51e34f5f975afef8d5e6c9038 |
|
BLAKE2b-256 | 096848313c7d691ded79cbe54e38bef3575a842fcca686b87f26c18953e34af2 |