# Entropy Coders for Research and Production
The `constriction` library provides a set of composable entropy coding
algorithms with a focus on correctness, versatility, ease of use, compression
performance, and computational efficiency. The goals of `constriction` are
three-fold:
1. **to facilitate research on novel lossless and lossy compression methods** by
providing a *composable* set of primitives (e.g., you can can easily switch
out a Range Coder for an ANS coder without having to find a new library or
change how you represent exactly invertible entropy models);
2. **to simplify the transition from research code to deployed software** by
providing similar APIs and binary compatible entropy coders for both Python
(for rapid prototyping on research code) and Rust (for turning successful
prototypes into standalone binaries, libraries, or WebAssembly modules); and
3. **to serve as a teaching resource** by providing a variety of entropy coding
primitives within a single consistent framework. Check out our [additional
teaching material](https://robamler.github.io/teaching/compress21/) from a
university course on data compression, which contains some problem sets where
you use `constriction` (with solutions).
**More Information:**
[project website](https://bamler-lab.github.io/constriction)
**Live demo:**
[here's a web app](https://robamler.github.io/linguistic-flux-capacitor) that
started out as a machine-learning research project in Python and was later
turned into a web app by using `constriction` in a WebAssembly module).
## Quick Start
Add the following to your `Cargo.toml`:
```toml
[dependencies]
constriction = "0.4.2"
probability = "0.20.3" # Not strictly required but used in many examples.
```
### Encoding Example
In this example, we'll encode some symbols using a quantized Gaussian
distribution as entropy model. Each symbol will be modeled by a quantized
Gaussian with a different mean and standard deviation (so that the example is
not too simplistic). We'll use the `probability` crate for the Gaussian
distributions, so make sure you have the following dependency in your
`Cargo.toml`:
```toml
probability = "0.20"
```
Now, let's encode (i.e., compress) some symbols. We'll use an Asymmetric Numeral
Systems (ANS) Coder here for its speed and compression performance. We'll
discuss how you could replace the ANS Coder with a Range Coder or a symbol code
like Huffman Coding [below](#user-content-exercise).
```rust
use constriction::stream::{stack::DefaultAnsCoder, model::DefaultLeakyQuantizer};
use probability::distribution::Gaussian;
fn encode_sample_data() -> Vec<u32> {
// Create an empty ANS Coder with default word and state size:
let mut coder = DefaultAnsCoder::new();
// Some made up data and entropy models for demonstration purpose:
let symbols = [23i32, -15, 78, 43, -69];
let means = [35.2, -1.7, 30.1, 71.2, -75.1];
let stds = [10.1, 25.3, 23.8, 35.4, 3.9];
// Create an adapter that integrates 1-d probability density functions over bins
// `[n - 0.5, n + 0.5)` for all integers `n` from `-100` to `100` using fixed point
// arithmetic with default precision, guaranteeing a nonzero probability for each bin:
let quantizer = DefaultLeakyQuantizer::new(-100..=100);
// Encode the data (in reverse order, since ANS Coding operates as a stack):
coder.encode_symbols_reverse(
symbols.iter().zip(&means).zip(&stds).map(
|((&sym, &mean), &std)| (sym, quantizer.quantize(Gaussian::new(mean, std)))
)).unwrap();
// Retrieve the compressed representation (filling it up to full words with zero bits).
coder.into_compressed().unwrap()
}
assert_eq!(encode_sample_data(), [0x421C_7EC3, 0x000B_8ED1]);
```
### Decoding Example
Now, let's reconstruct the sample data from its compressed representation.
```rust
use constriction::stream::{stack::DefaultAnsCoder, model::DefaultLeakyQuantizer, Decode};
use probability::distribution::Gaussian;
fn decode_sample_data(compressed: Vec<u32>) -> Vec<i32> {
// Create an ANS Coder with default word and state size from the compressed data:
// (ANS uses the same type for encoding and decoding, which makes the method very flexible
// and allows interleaving small encoding and decoding chunks, e.g., for bits-back coding.)
let mut coder = DefaultAnsCoder::from_compressed(compressed).unwrap();
// Same entropy models and quantizer we used for encoding:
let means = [35.2, -1.7, 30.1, 71.2, -75.1];
let stds = [10.1, 25.3, 23.8, 35.4, 3.9];
let quantizer = DefaultLeakyQuantizer::new(-100..=100);
// Decode the data:
coder.decode_symbols(
means.iter().zip(&stds).map(
|(&mean, &std)| quantizer.quantize(Gaussian::new(mean, std))
)).collect::<Result<Vec<_>, _>>().unwrap()
}
assert_eq!(decode_sample_data(vec![0x421C_7EC3, 0x000B_8ED1]), [23, -15, 78, 43, -69]);
```
## Exercise
Try out the above examples and verify that decoding reconstructs the original
data. Then see how easy `constriction` makes it to replace the ANS Coder with a
Range Coder by making the following substitutions:
**In the encoder,**
- replace `constriction::stream::stack::DefaultAnsCoder` with
`constriction::stream::queue::DefaultRangeEncoder`; and
- replace `coder.encode_symbols_reverse` with `coder.encode_symbols` (you no
longer need to encode symbols in reverse order since Range Coding operates as
a queue, i.e., first-in-first-out). You'll also have to add the line
`use constriction::stream::Encode;` to the top of the file to bring the trait
method `encode_symbols` into scope.
**In the decoder,**
- replace `constriction::stream::stack::DefaultAnsCoder` with
`constriction::stream::queue::DefaultRangeDecoder` (note that Range Coding
distinguishes between an encoder and a decoder type since the encoder writes
to the back while the decoder reads from the front; by contrast, ANS Coding is
a stack, i.e., it reads and writes at the same position and allows
interleaving reads and writes).
*Remark:* You could also use a symbol code like Huffman Coding (see module
[`symbol`]) but that would have considerably worse compression performance,
especially on large files, since symbol codes always emit an integer number of
bits per compressed symbol, even if the information content of the symbol is a
fractional number (stream codes like ANS and Range Coding *effectively* emit a
fractional number of bits per symbol since they amortize over several symbols).
The above replacements should lead you to something like this:
```rust
use constriction::stream::{
model::DefaultLeakyQuantizer,
queue::{DefaultRangeEncoder, DefaultRangeDecoder},
Encode, Decode,
};
use probability::distribution::Gaussian;
fn encode_sample_data() -> Vec<u32> {
// Create an empty Range Encoder with default word and state size:
let mut encoder = DefaultRangeEncoder::new();
// Same made up data, entropy models, and quantizer as in the ANS Coding example above:
let symbols = [23i32, -15, 78, 43, -69];
let means = [35.2, -1.7, 30.1, 71.2, -75.1];
let stds = [10.1, 25.3, 23.8, 35.4, 3.9];
let quantizer = DefaultLeakyQuantizer::new(-100..=100);
// Encode the data (this time in normal order, since Range Coding is a queue):
encoder.encode_symbols(
symbols.iter().zip(&means).zip(&stds).map(
|((&sym, &mean), &std)| (sym, quantizer.quantize(Gaussian::new(mean, std)))
)).unwrap();
// Retrieve the (sealed up) compressed representation.
encoder.into_compressed().unwrap()
}
fn decode_sample_data(compressed: Vec<u32>) -> Vec<i32> {
// Create a Range Decoder with default word and state size from the compressed data:
let mut decoder = DefaultRangeDecoder::from_compressed(compressed).unwrap();
// Same entropy models and quantizer we used for encoding:
let means = [35.2, -1.7, 30.1, 71.2, -75.1];
let stds = [10.1, 25.3, 23.8, 35.4, 3.9];
let quantizer = DefaultLeakyQuantizer::new(-100..=100);
// Decode the data:
decoder.decode_symbols(
means.iter().zip(&stds).map(
|(&mean, &std)| quantizer.quantize(Gaussian::new(mean, std))
)).collect::<Result<Vec<_>, _>>().unwrap()
}
let compressed = encode_sample_data();
// We'll get a different compressed representation than in the ANS Coding
// example because we're using a different entropy coding algorithm ...
assert_eq!(compressed, [0x1C31EFEB, 0x87B430DA]);
// ... but as long as we decode with the matching algorithm we can still reconstruct the data:
assert_eq!(decode_sample_data(compressed), [23, -15, 78, 43, -69]);
```
## Where to Go Next?
If you already have an entropy model and you just want to encode and decode some
sequence of symbols then you can probably start by adjusting the above examples
to your needs. Or have a closer look at the `stream` module.
More examples and tutorials are linked from the
[project website](https://bamler-lab.github.io/constriction).
If you're still new to the concept of entropy coding then check out the
[teaching material](https://robamler.github.io/teaching/compress21/).
## 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 consider
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](https://bamler-lab.github.io/constriction/license.html)).
## What's With the Name?
Constriction is a library of compression primitives with bindings for Rust and
[Python](https://en.wikipedia.org/wiki/Python_(programming_language)).
[Pythons](https://en.wikipedia.org/wiki/Pythonidae) are a family of nonvenomous
snakes that subdue their prey by "compressing" it, a method known as
[constriction](https://en.wikipedia.org/wiki/Constriction).
