Module constriction.stream.model
Entropy models and model families for use with any of the stream codes from the sister
modules stack
, queue
, and chain
.
This module provides tools to define probability distributions over symbols in fixed
point arithmetic, so that the models (more precisely, their cumulative distributions
functions) are exactly invertible without any rounding errors. Being exactly
invertible is crucial for for data compression since even tiny rounding errors can have
catastrophic consequences in an entropy coder (this issue is discussed in the
motivating example of the ChainCoder
). Further, the entropy
models in this module all have a well-defined domain, and they always assign a nonzero
probability to all symbols within this domain, even if the symbol is in the tail of some
distribution where its true probability would be lower than the smallest value that is
representable in the employed fixed point arithmetic. This ensures that symbols from the
well-defined domain of a model can, in principle, always be encoded without throwing an
error (symbols with the smallest representable probability will, however, have a very
high bitrate of 24 bits).
Concrete Models vs. Model Families
The entropy models in this module can be instantiated in two different ways:
- (a) as concrete models that are fully parameterized; simply provide all model
parameters to the constructor of the model (e.g., the mean and standard deviation of a
QuantizedGaussian
, or the domain of aUniform
model). You can use a concrete model to either encode or decode single symbols, or to efficiently encode or decode a whole array of i.i.d. symbols (i.e., using the same model for each symbol in the array, see first example below). - (b) as model families, i.e., models that still have some free parameters (again,
like the mean and standard deviation of a
QuantizedGaussian
, or the range of aUniform
distribution); simply leave out any optional model parameters when calling the model constructor. When you then use the resulting model family to encode or decode an array of symbols, you can provide arrays of model parameters to the encode and decode methods of the employed entropy coder. This will allow you to use individual model parameters for each symbol, see second example below (this is more efficient than constructing a new concrete model for each symbol and looping over the symbols in Python).
Examples
Constructing and using a concrete QuantizedGaussian
model with mean 12.6 and standard deviation 7.3, and which is quantized to integers on the domain
{-100, -99, …, 100}:
model = constriction.stream.model.QuantizedGaussian(-100, 100, 12.6, 7.3)
# Encode and decode an example message:
symbols = np.array([12, 15, 4, -2, 18, 5], dtype=np.int32)
coder = constriction.stream.stack.AnsCoder() # (RangeEncoder also works)
coder.encode_reverse(symbols, model)
print(coder.get_compressed()) # (prints: [745994372, 25704])
reconstructed = coder.decode(model, 6) # (decodes 6 i.i.d. symbols)
assert np.all(reconstructed == symbols) # (verify correctness)
We can generalize the above example and use model-specific means and standard deviations by constructing and using a model family instead of a concrete model, and by providing arrays of model parameters to the encode and decode methods:
model_family = constriction.stream.model.QuantizedGaussian(-100, 100)
# Note: we omitted the mean and standard deviation, but the quantization range
# {-100, ..., 100} must always be specified when constructing the model.
# Define arrays of model parameters (means and standard deviations):
symbols = np.array([12, 15, 4, -2, 18, 5 ], dtype=np.int32)
means = np.array([13.2, 17.9, 7.3, -4.2, 25.1, 3.2], dtype=np.float64)
stds = np.array([ 3.2, 4.7, 5.2, 3.1, 6.3, 2.9], dtype=np.float64)
# Encode and decode an example message:
coder = constriction.stream.stack.AnsCoder() # (RangeEncoder also works)
coder.encode_reverse(symbols, model_family, means, stds)
print(coder.get_compressed()) # (prints: [2051958011, 1549])
reconstructed = coder.decode(model_family, means, stds)
assert np.all(reconstructed == symbols) # (verify correctness)
Classes
class Bernoulli (self, p=None)
-
A Bernoulli distribution over the alphabet {0, 1}.
Model Parameter
The model parameter can either be specified as a scalar when constructing the model, or as a rank-1 numpy array with
dtype=np.float64
when calling the entropy coder's encode or decode method (see discussion above). Note that, in the latter case, you still have to call the constructor of the model, i.e.:model_family = constriction.stream.model.Bernoulli()
— note the trailing()
.- p — the probability for the symbol being
1
rather than0
. Must be between 0.0 and 1.0 (both inclusive). Note that, even if you setp = 0.0
orp = 1.0
,constriction
still assigns a tiny probability to the disallowed outcome so that both symbols0
and1
can always be encoded, albeit at a potentially large cost in bitrate.
Ancestors
- builtins.Model
- p — the probability for the symbol being
class Binomial (self, n=None, p=None)
-
A Binomial distribution over the alphabet {0, 1, …, n}.
Models the number of successful trials out of
n
trials where the trials are independent from each other and each one succeeds with probabilityp
.Model Parameters
Each model parameter can either be specified as a scalar when constructing the model, or as a rank-1 numpy array (with
dtype=np.int32
forn
anddtype=np.float64
forp
) when calling the entropy coder's encode or decode method (see discussion above). Note that, even if you delay all model parameters to the point of encoding or decoding, then you still have to call the constructor of the model, i.e.:model_family = constriction.stream.model.Binomial()
— note the trailing()
.- n — the number of trials;
- p — the probability that any given trial succeeds; must be between 0.0 and 1.0
(both inclusive). For your convenience,
constriction
always assigns a (possibly tiny but) nonzero probability to all symbols in the range {0, 1, …, n}, even if you setp = 0.0
orp = 1.0
so that all symbols in this range can in principle be encoded, albeit possibly at a high bitrate.
Ancestors
- builtins.Model
class Categorical (self, probabilities=None)
-
A categorical distribution with explicitly provided probabilities.
Allows you to define any probability distribution over the alphabet
{0, 1, ... n-1}
by explicitly providing the probability of each symbol in the alphabet.Examples
Using a concrete (i.e., fully parameterized)
CategoricalModel
:# Define a categorical distribution over the (implied) alphabet {0,1,2,3} # with P(X=0) = 0.2, P(X=1) = 0.4, P(X=2) = 0.1, and P(X=3) = 0.3: probabilities = np.array([0.2, 0.4, 0.1, 0.3], dtype=np.float64) model = constriction.stream.model.Categorical(probabilities) # Encode and decode an example message: symbols = np.array([0, 3, 2, 3, 2, 0, 2, 1], dtype=np.int32) coder = constriction.stream.stack.AnsCoder() # (RangeEncoder also works) coder.encode_reverse(symbols, model) print(coder.get_compressed()) # (prints: [488222996, 175]) reconstructed = coder.decode(model, 8) # (decodes 8 i.i.d. symbols) assert np.all(reconstructed == symbols) # (verify correctness)
Using a model family so that we can provide individual probabilities for each encoded or decoded symbol:
# Define 3 categorical distributions, each over the alphabet {0,1,2,3,4}: model_family = constriction.stream.model.Categorical() # note empty `()` probabilities = np.array( [[0.3, 0.1, 0.1, 0.3, 0.2], # (for symbols[0]) [0.1, 0.4, 0.2, 0.1, 0.2], # (for symbols[1]) [0.4, 0.2, 0.1, 0.2, 0.1]], # (for symbols[2]) dtype=np.float64) symbols = np.array([0, 4, 1], dtype=np.int32) coder = constriction.stream.stack.AnsCoder() # (RangeEncoder also works) coder.encode_reverse(symbols, model_family, probabilities) print(coder.get_compressed()) # (prints: [152672664]) reconstructed = coder.decode(model_family, probabilities) assert np.all(reconstructed == symbols) # (verify correctness)
Model Parameters
- probabilities — the probability table, as a numpy array. You can specify the
probabilities either directly when constructing the model by passing a rank-1 numpy
array with
dtype=np.float64
and lengthn
to the constructor; or you can call the constructor with no arguments and instead provide a rank-2 tensor of shape(m, n)
when encoding or decoding an array ofm
symbols, as in the second example above.
The probability table for each symbol must be normalizable (i.e., all probabilities must be nonnegative and finite), but the probabilities don't necessarily have to sum to one. They will automatically be rescaled to an exactly normalized distribution. Further,
constriction
guarantees to assign at least the smallest representable nonzero probability to all symbols from the range{0, 1, ..., n-1}
(wheren
is the number of provided probabilities), even if the provided probability for some symbol is smaller than the smallest representable probability (including if it is exactly0.0
). This ensures that all symbols from this range can in principle be encoded.Note that, if you delay providing the probabilities until encoding or decoding as in the second example above, you still have to call the constructor of the model, i.e.,
model_family = constriction.stream.model.Categorical()
— note the empty parentheses()
at the end.Ancestors
- builtins.Model
- probabilities — the probability table, as a numpy array. You can specify the
probabilities either directly when constructing the model by passing a rank-1 numpy
array with
class CustomModel (self, cdf, approximate_inverse_cdf, min_symbol_inclusive, max_symbol_inclusive)
-
Wrapper for a model (or model family) defined via custom callback functions
A
CustomModel
provides maximum flexibility for defining entropy models. It encapsulates a user-defined cumulative distribution function (CDF) and the corresponding quantile function (inverse of the CDF, also called percent point function or PPF).A
CustomModel
can define either a concrete model or a model family (see discussion above). To define a model family, the provided callbacks for the CDF and PPF should expect additional model parameters, see second example below.Before You Read on
If you use the
scipy
python package for defining your entropy model, then there's no need to useCustomModel
. The adapterScipyModel
will be more convenient.Examples
Using a concrete (i.e., fully parameterized) custom model:
model = constriction.stream.model.CustomModel( lambda x: ... TODO ..., # define your CDF here lambda xi: ... TODO ..., # provide an approximate inverse of the CDF -100, 100) # (or whichever range your model has) # Encode and decode an example message: symbols = np.array([... TODO ...], dtype=np.int32) coder = constriction.stream.stack.AnsCoder() # (RangeEncoder also works) coder.encode_reverse(symbols, model) print(coder.get_compressed()) reconstructed = coder.decode(model, 5) # (decodes 5 i.i.d. symbols) assert np.all(reconstructed == symbols) # (verify correctness)
Using a model family so that we can provide individual model parameters for each encoded or decoded symbol:
model_family = constriction.stream.model.CustomModel( lambda x, model_param1, model_param2: ... TODO ..., # CDF lambda xi, model_param1, model_param2: ... TODO ..., # PPF -100, 100) # (or whichever range your model has) # Encode and decode an example message with per-symbol model parameters: symbols = np.array([... TODO ...], dtype=np.int32) model_params1 = np.array([... TODO ...], dtype=np.float64) model_params2 = np.array([... TODO ...], dtype=np.float64) coder = constriction.stream.stack.AnsCoder() # (RangeEncoder also works) coder.encode_reverse(symbols, model_family, model_params1, model_params2) print(coder.get_compressed()) reconstructed = coder.decode(model_family, model_params1, model_params2) assert np.all(reconstructed == symbols) # (verify correctness)
Arguments
The following arguments always have to be provided directly to the constructor of the model. They cannot be delayed until encoding or decoding. However, you may provide callback functions
cdf
andapproximate_inverse_cdf
that expect additional model parameters, which you then pass in as numpy arrays when calling the entropy coder's encode or decode method, see second example above.- cdf — the cumulative distribution function; must be
a nondecreasing function
that returns a scalar between 0.0 and 1.0 (both inclusive) when evaluated at any
mid-point between two consecutive integers within the inclusive range from
min_symbol_inclusive
tomax_symbol_inclusive
. The function signature must becdf(x, [param1, [param2, [param3, …]]])
wherex
is the value at whichconstriction
will evaluate the CDF, andparamX
will be provided if theCustomModel
is used as a model family, as in the second example above. - approximate_inverse_cdf — the inverse of the CDF, also called quantile function
or percent point function (PPF). This function does not have to return very precise
results since
constriction
will use the providedcdf
as the defining source of truth and invert it exactly; the providedapproximate_inverse_cdf
is only used to speed up the function inversion. The function signature must be analogous to above,approximate_inverse_cdf(xi, [param1, [param2, [param3, …]]])
, where you may rely on0.0 <= xi <= 1.0
. - min_symbol_inclusive and max_symbol_inclusive — define the range of integer symbols that you will be able to encode with this model, see "Guarantees And Requirements" below.
Guarantees And Requirements
The
constriction
library takes care of ensuring that the resulting entropy model is exactly invertible, which is crucial for correct encoding/decoding, and which is nontrivial due to inevitable rounding errors. In addition,constriction
ensures that all symbols within the provided range {min_symbol_inclusive
, …,max_symbol_inclusive
} are assigned a nonzero probability (even if their actual probability under the provided model is smaller than the smallest representable probability), and that the probabilities of all symbols within this range add up to exactly one, without rounding errors. This is important to ensure that all symbols within the provided range can indeed be encoded, and that encoding with ANS is surjective.The above guarantees hold only as long as the provided CDF is nondecreasing, can be evaluated on mid-points between integers, and returns a value >= 0.0 and <= 1.0 everywhere.
Ancestors
- builtins.Model
Subclasses
- builtins.ScipyModel
- cdf — the cumulative distribution function; must be
a nondecreasing function
that returns a scalar between 0.0 and 1.0 (both inclusive) when evaluated at any
mid-point between two consecutive integers within the inclusive range from
class Model (...)
-
Abstract base class for all entropy models.
This class cannot be instantiated. Instantiate one of its concrete subclasses instead.
Subclasses
- builtins.Bernoulli
- builtins.Binomial
- builtins.Categorical
- builtins.CustomModel
- builtins.QuantizedCauchy
- builtins.QuantizedGaussian
- builtins.QuantizedLaplace
- builtins.Uniform
class QuantizedCauchy (self, min_symbol_inclusive, max_symbol_inclusive, loc=None, scale=None)
-
A Cauchy distribution, quantized over bins of size 1 centered at integer values.
Analogous to
QuantizedGaussian
, just starting from a Cauchy distribution rather than a Gaussian.Before quantization, the probability density function of a Cauchy distribution is:
p(x) = 1 / (pi * gamma * (1 + ((x - loc) / gamma)^2))
where the parameters
loc
andscale
parameterize the location of the mode and the width of the distribution.Fixed Arguments
The following arguments always have to be provided directly to the constructor of the model. They cannot be delayed until encoding or decoding.
- min_symbol_inclusive and max_symbol_inclusive — specify the integer range on which the model is defined.
Model Parameters
Each of the following model parameters can either be specified as a scalar when constructing the model, or as a rank-1 numpy array (with
dtype=np.float64
) when calling the entropy coder's encode or decode method.- loc — the location (mode) of the Cauchy distribution before quantization.
- scale — the scale parameter
gamma
of the Cauchy distribution before quantization (resulting in a full width at half maximum of2 * scale
). Must be strictly positive. If the scale is calculated by a function that might return zero, then add some small regularization (e.g., 1e-16) to it to ensure the function argument is positive (note that, as with any parameters of the entropy model, regularization has to be consistent between encoder and decoder side).
Ancestors
- builtins.Model
class QuantizedGaussian (self, min_symbol_inclusive, max_symbol_inclusive, mean=None, std=None)
-
A Gaussian distribution, quantized over bins of size 1 centered at integer values.
This kind of entropy model is often used in novel deep-learning based compression methods. If you need a quantized continuous distribution that is not a Gaussian or a Laplace, then maybe
ScipyModel
orCustomModel
is for you.A
QuantizedGaussian
distribution is a probability distribution over the alphabet{-min_symbol_inclusive, -min_symbol_inclusive + 1, ..., max_symbol_inclusive}
. It is defined by taking a Gaussian (or "Normal") distribution with the specified mean and standard deviation, clipping it to the interval[-min_symbol_inclusive - 0.5, max_symbol_inclusive + 0.5]
, renormalizing it to account for the clipped off tails, and then integrating the probability density over the bins[symbol - 0.5, symbol + 0.5]
for eachconstriction.symbol
in the above alphabet. We further guarantee that all symbols within the above alphabet are assigned at least the smallest representable nonzero probability (and thus can, in principle, be encoded), even if the true probability mass on the interval[symbol - 0.5, symbol + 0.5]
integrates to a value that is smaller than the smallest representable nonzero probability.Examples
Fixed Arguments
The following arguments always have to be provided directly to the constructor of the model. They cannot be delayed until encoding or decoding.
- min_symbol_inclusive and max_symbol_inclusive — specify the integer range on which the model is defined.
Model Parameters
Each of the following model parameters can either be specified as a scalar when constructing the model, or as a rank-1 numpy array (with
dtype=np.float64
) when calling the entropy coder's encode or decode method.- mean — the mean of the Gaussian distribution before quantization.
- std — the standard deviation of the Gaussian distribution before quantization. Must be strictly positive. If the standard deviation is calculated by a function that might return zero, then add some small regularization (e.g., 1e-16) to it to ensure the function argument is positive (note that, as with any parameters of the entropy model, regularization has to be consistent between encoder and decoder side).
Ancestors
- builtins.Model
class QuantizedLaplace (self, min_symbol_inclusive, max_symbol_inclusive, mean=None, scale=None)
-
A Laplace distribution, quantized over bins of size 1 centered at integer values.
Analogous to
QuantizedGaussian
, just starting from a Laplace distribution rather than a Gaussian.Fixed Arguments
The following arguments always have to be provided directly to the constructor of the model. They cannot be delayed until encoding or decoding.
- min_symbol_inclusive and max_symbol_inclusive — specify the integer range on which the model is defined.
Model Parameters
Each of the following model parameters can either be specified as a scalar when constructing the model, or as a rank-1 numpy array (with
dtype=np.float64
) when calling the entropy coder's encode or decode method.- mean — the mean of the Laplace distribution before quantization.
- scale — the scale parameter
b
of the Laplace distribution before quantization (resulting in a variance of2 * scale**2
). Must be strictly positive. If the scale is calculated by a function that might return zero, then add some small regularization (e.g., 1e-16) to it to ensure the function argument is positive (note that, as with any parameters of the entropy model, regularization has to be consistent between encoder and decoder side).
Ancestors
- builtins.Model
class ScipyModel (self, scipy_model, min_symbol_inclusive, max_symbol_inclusive)
-
Adapter for models and model families from the
scipy
python package.This is similar to
CustomModel
but easier to use if your model's cumulative distribution function and percent point function are already implemented in the popularscipy
python package. Just provide either a fully parameterized scipy-model or a scipy model-class to the constructor. The adapter can be used both with both discrete models (over a continuous integer domain) and continuous models. Continuous models will be quantized to bins of width 1 centered at integers, analogous to the procedure described in the documentation ofQuantizedGaussian
Compatibility Warning
The
scipy
package provides some of the same models for whichconstriction
offers builtin models too (e.g., Gaussian, Laplace, Binomial). While wrapping, e.g.,scipy.stats.norm
in aScipyModel
will result in an entropy model that is similar to aQuantizedGaussian
with the same parameters, the two models will differ slightly due to different rounding operations. Even such tiny differences can have catastrophic effects when the models are used for entropy coding. Thus, always make sure you use the same implementation of entropy models on the encoder and decoder side. Generally preferconstriction
's builtin models since they are considerably faster and also available inconstriction
's Rust API.Examples
Using a concrete (i.e., fully parameterized)
scipy
model:import scipy.stats scipy_model = scipy.stats.cauchy(loc=6.7, scale=12.4) model = constriction.stream.model.ScipyModel(scipy_model, -100, 100) # Encode and decode an example message: symbols = np.array([22, 14, 5, -3, 19, 7], dtype=np.int32) coder = constriction.stream.stack.AnsCoder() # (RangeEncoder also works) coder.encode_reverse(symbols, model) print(coder.get_compressed()) # (prints: [3569876501 1944098]) reconstructed = coder.decode(model, 6) # (decodes 6 i.i.d. symbols) assert np.all(reconstructed == symbols) # (verify correctness)
Using a model family so that we can provide individual model parameters for each encoded or decoded symbol:
import scipy.stats scipy_model_family = scipy.stats.cauchy model_family = constriction.stream.model.ScipyModel( scipy_model_family, -100, 100) # Encode and decode an example message with per-symbol model parameters: symbols = np.array([22, 14, 5, -3, 19, 7 ], dtype=np.int32) locs = np.array([26.2, 10.9, 8.7, -6.3, 25.1, 8.9], dtype=np.float64) scales = np.array([ 4.3, 7.4, 2.9, 4.1, 9.7, 3.4], dtype=np.float64) coder = constriction.stream.stack.AnsCoder() # (RangeEncoder also works) coder.encode_reverse(symbols, model_family, locs, scales) print(coder.get_compressed()) # (prints: [3493721376, 17526]) reconstructed = coder.decode(model_family, locs, scales) assert np.all(reconstructed == symbols) # (verify correctness)
Arguments
The following arguments always have to be provided directly to the constructor of the model. They cannot be delayed until encoding or decoding. However, the encapsulated scipy model may expect additional model parameters, which you can pass in at encoding or decoding time as in the second example below.
- model — a
scipy
model or model class as in the examples above. - min_symbol_inclusive and max_symbol_inclusive — define the range of integer symbols that you will be able to encode with this model, see "Guarantees And Requirements" below.
Ancestors
- builtins.CustomModel
- builtins.Model
- model — a
class Uniform (self, size=None)
-
A uniform distribution over the alphabet
{0, 1, ..., size-1}
, wheresize
is an integer model parameter.Due to rounding effects, the symbol
size-1
typically has very slightly higher probability than the other symbols.Model Parameter
The model parameter can either be specified as a scalar when constructing the model, or as a rank-1 numpy array with
dtype=np.int32
when calling the entropy coder's encode or decode method. Note that, in the latter case, you still have to call the constructor of the model, i.e.:model_family = constriction.stream.model.Uniform()
— note the trailing()
.- size — the size of the alphabet / domain of the model. Must be at least 2 since
constriction
cannot model delta distributions. Must be smaller than2**24
≈ 17 millions.
Ancestors
- builtins.Model
- size — the size of the alphabet / domain of the model. Must be at least 2 since