Package constriction

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 from a university course on data compression, which contains some problem sets where you use constriction (with solutions).

More Information: project website

Live demo: here's a web app 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

Installing constriction for Python

pip install constriction~=0.4.1

Hello, World

You'll mostly use the constriction.stream submodule, which provides stream codes (like Range Coding or ANS). The following example shows a simple encoding-decoding round trip. More complex entropy models and other entropy coders are also supported, see more examples below.

import constriction
import numpy as np

message = np.array([6, 10, -4, 2, 5, 2, 1, 0, 2], dtype=np.int32)

# Define an i.i.d. entropy model (see below for more complex models):
entropy_model = constriction.stream.model.QuantizedGaussian(-50, 50, 3.2, 9.6)

# Let's use an ANS coder in this example. See below for a Range Coder example.
encoder = constriction.stream.stack.AnsCoder()
encoder.encode_reverse(message, entropy_model)

compressed = encoder.get_compressed()
print(f"compressed representation: {compressed}")
print(f"(in binary: {[bin(word) for word in compressed]})")

decoder = constriction.stream.stack.AnsCoder(compressed)
decoded = decoder.decode(entropy_model, 9) # (decodes 9 symbols)
assert np.all(decoded == message)

More Examples

Switching Out the Entropy Coding Algorithm

Let's take our "Hello, World" example from above and assume we want to switch the entropy coding algorithm from ANS to Range Coding. But we don't want to look for a new library or change how we represent entropy models and compressed data. Luckily, we only have to modify a few lines of code:

import constriction
import numpy as np

# Same representation of message and entropy model as in the previous example:
message = np.array([6, 10, -4, 2, 5, 2, 1, 0, 2], dtype=np.int32)
entropy_model = constriction.stream.model.QuantizedGaussian(-50, 50, 3.2, 9.6)

# Let's use a Range coder now:
encoder = constriction.stream.queue.RangeEncoder()         # <-- CHANGED LINE
encoder.encode(message, entropy_model)          # <-- (slightly) CHANGED LINE

compressed = encoder.get_compressed()
print(f"compressed representation: {compressed}")
print(f"(in binary: {[bin(word) for word in compressed]})")

decoder = constriction.stream.queue.RangeDecoder(compressed) #<--CHANGED LINE
decoded = decoder.decode(entropy_model, 9) # (decodes 9 symbols)
assert np.all(decoded == message)

Complex Entropy Models

This time, let's keep the entropy coding algorithm as it is but make the entropy model more complex. We'll encode the first 5 symbols of the message again with a QuantizedGaussian distribution, but this time we'll use individual model parameters (means and standard deviations) for each of the 5 symbols. For the remaining 4 symbols, we'll use a fixed categorical distribution, just to make it more interesting:

import constriction
import numpy as np

# Same message as above, but a complex entropy model consisting of two parts:
message = np.array([6,   10,   -4,   2,   5,    2, 1, 0, 2], dtype=np.int32)
means   = np.array([2.3,  6.1, -8.5, 4.1, 1.3], dtype=np.float32)
stds    = np.array([6.2,  5.3,  3.8, 3.2, 4.7], dtype=np.float32)
entropy_model1 = constriction.stream.model.QuantizedGaussian(-50, 50)
entropy_model2 = constriction.stream.model.Categorical(
    np.array([0.2, 0.5, 0.3], dtype=np.float32), # Probabilities of the symbols 0,1,2.
    perfect=False
)

# Simply encode both parts in sequence with their respective models:
encoder = constriction.stream.queue.RangeEncoder()
encoder.encode(message[0:5], entropy_model1, means, stds) # per-symbol params.
encoder.encode(message[5:9], entropy_model2)

compressed = encoder.get_compressed()
print(f"compressed representation: {compressed}")
print(f"(in binary: {[bin(word) for word in compressed]})")

decoder = constriction.stream.queue.RangeDecoder(compressed)
decoded_part1 = decoder.decode(entropy_model1, means, stds)
decoded_part2 = decoder.decode(entropy_model2, 4)
assert np.all(np.concatenate((decoded_part1, decoded_part2)) == message)

You can define even more complex entropy models by providing an arbitrary Python function for the cumulative distribution function (see CustomModel and ScipyModel). The constriction library provides wrappers that turn your models into exactly invertible fixed-point arithmetic since even tiny rounding errors could otherwise completely break an entropy coding algorithm.

Exercise

We've shown examples of ANS coding with a simple entropy model, of Range Coding with the same simple entropy model and of Range coding with a complex entropy model. One combination is still missing: ANS coding with the complex entropy model from the last example above. This should be no problem now, so try it out yourself:

  • In the last example above, change both "queue.RangeEncoder" and "queue.RangeDecoder" to "stack.AnsCoder" (ANS uses the same data structure for both encoding and decoding).
  • Then change both occurrences of .encode(…) to .encode_reverse(…) (since ANS operates as a stack, i.e., last-in-first-out, we encode the symbols in reverse order so that we can decode them in their normal order).
  • Finally, there's one slightly subtle change: when encoding the message, switch the order of the two lines that encode message[0:5] and message[5:9], respectively. Do not change the order of decoding though. This is again necessary because ANS operates as a stack.

Congratulations, you've successfully implemented your first own compression scheme with constriction.

Further Reading

You can find links to more examples and tutorials on the project website. Or just dive right into the documentation of range coding, ANS, and entropy models.

Sub-modules

constriction.stream

Stream codes, i.e., entropy codes that amortize compressed bits over several symbols …

constriction.symbol

Symbol codes. Mainly provided for teaching purpose. You'll probably want to use a stream code instead …