Module constriction.stream.chain
Experimental entropy coding algorithm for advanced variants of bits-back coding.
This module provides the ChainCoder
, an experimental entropy coder that is similar
to an AnsCoder
in that it operates as
a stack (i.e., a last-in-first-out data structure). However, different to an AnsCoder
,
a ChainCoder
treats each symbol independently. Thus, when decoding some bit string
into a sequence of symbols, any modification to the entropy model for one symbol does
not affect decoding for any other symbol (by contrast, when decoding with an AnsCoder
or RangeDecoder
, a change to the entropy model for one symbol can affect all
subsequently decoded symbols too, see Motivation below).
This property of treating symbols independently upon decoding can be useful for advanced compression methods that combine inference, quantization, and bits-back coding.
Motivation
The following two examples illustrate how decoding differs between an AnsCoder
and a
ChainCoder
. In the first example, we decode from the same bitstring data
twice with
an AnsCoder
: a first time with an initial sequence of toy entropy models, and then a
second time with a slightly different sequence of entropy models. Importantly, we change
only the entropy model for the first decoded symbol (and the change is small). The
entropy models for all other symbols remain exactly unmodified. We observe, however,
that changing the first entropy model affects not only the first decoded symbol. It also
has a ripple effect on subsequently decoded symbols.
# Some sample binary data and sample probabilities for our entropy models
data = np.array([0x80d14131, 0xdda97c6c, 0x5017a640, 0x01170a3d], np.uint32)
probabilities = np.array(
[[0.1, 0.7, 0.1, 0.1], # (<-- probabilities for first decoded symbol)
[0.2, 0.2, 0.1, 0.5], # (<-- probabilities for second decoded symbol)
[0.2, 0.1, 0.4, 0.3]]) # (<-- probabilities for third decoded symbol)
model_family = constriction.stream.model.Categorical()
# Decoding `data` with an `AnsCoder` results in the symbols `[0, 0, 1]`:
ansCoder = constriction.stream.stack.AnsCoder(data, seal=True)
print(ansCoder.decode(model_family, probabilities)) # (prints: [0, 0, 1])
# Even if we change only the first entropy model (slightly), *all* decoded
# symbols can change:
probabilities[0, :] = np.array([0.09, 0.71, 0.1, 0.1])
ansCoder = constriction.stream.stack.AnsCoder(data, seal=True)
print(ansCoder.decode(model_family, probabilities)) # (prints: [1, 0, 3])
It's no surprise that the first symbol changed since we changed its entropy model. But note that the third symbol changed too even though we hadn't changed its entropy model. Thus, in ANS (as in most codes), changes to entropy models have a global effect.
Now let's try the same with a ChainCoder
:
# Same compressed data and original entropy models as in our first example
data = np.array([0x80d14131, 0xdda97c6c, 0x5017a640, 0x01170a3d], np.uint32)
probabilities = np.array(
[[0.1, 0.7, 0.1, 0.1],
[0.2, 0.2, 0.1, 0.5],
[0.2, 0.1, 0.4, 0.3]])
model_family = constriction.stream.model.Categorical()
# Decode with the original entropy models, this time using a `ChainCoder`:
chainCoder = constriction.stream.chain.ChainCoder(data, seal=True)
print(chainCoder.decode(model_family, probabilities)) # (prints: [0, 3, 3])
# We obtain different symbols than for the `AnsCoder`, of course, but that's
# not the point here. Now let's change the first model again:
probabilities[0, :] = np.array([0.09, 0.71, 0.1, 0.1])
chainCoder = constriction.stream.chain.ChainCoder(data, seal=True)
print(chainCoder.decode(model_family, probabilities)) # (prints: [1, 3, 3])
Notice that the only symbol that changed was the one whose entropy model we had changed.
Thus, in a ChainCoder
, changes to entropy models (and also to compressed bits) only
have a local effect on the decompressed symbols.
How does this work?
A ChainCoder
is a variant on ANS. To understand how a ChainCoder
works, one first
has to understand how an AnsCoder
works. When an AnsCoder
decodes a symbol, it
performs the following three steps:
- The
AnsCoder
consumes a fixed amount of bits (24 bits inconstriction
's default configuration) from the end of its encapsulated compressed data; then - the
AnsCoder
interprets these 24 bits as a numberxi
between 0.0 and 1.0 in fixed point representation, and it mapsxi
to a symbol using the entropy model's quantile function (aka percent point function); finally - the
AnsCoder
uses the bits-back trick to write (24 - inf_content) bits worth of (amortized) bits back onto the encapsulated compressed data; these "returned" bits reflect the information contained in the precise position of the numberxi
within the whole range of numbers that the quantile function would map to the same symbol.
A ChainCoder
breaks these three steps apart. It encapsulates two rather than just
one bitstring buffers, referred to in the following as "compressed" and "remainders".
When you call the constructor of ChainCoder
with argument is_remainders=False
(which
is the default) then the provided argument data
is used to initialize the "compressed"
buffer. When the ChainCoder
decodes a symbol, it executes steps 1-3 from above, with
the modification that step 1 reads from the "compressed" buffer while step 3 writes to
the "remainders" buffer. Since step 1 is independent of the employed entropy model,
changes to the entropy model have no effect on subsequently decoded symbols.
Once you're done decoding a sequence of symbols, you can concatenate the two buffers to a single one.
Usage for Bits-Back Coding
A typical usage cycle of a ChainCoder
goes along the following steps:
When compressing data using the bits-back trick
- Start with some array of (typically already compressed) binary data, which you want to piggy-back into the choice of latent variables in a latent variable entropy model.
- Create a
ChainCoder
, passing into the constructor the binary data and the argumentsis_remainders=False
andseal=True
(you can setseal=False
if you know that the data cannot end in a zero word, e.g., if it comes fromAnsCoder.get_compressed(unseal=False)
). - Decode the latent variables from the
ChainCoder
as usual in bits-back coding. - Export the remaining data on the
ChainCoder
by calling its method.get_remainders()
. The method returns two numpy arrays, which you may concatenate in order. - You can now use this remaining binary data in an
AnsCoder
(it is guaranteed not to have a zero word at the end, so you can setseal=False
in the constructor ofAnsCoder
), and you can encode a message on top of it using entropy models that are conditioned on the latent variables you just decoded.
When decompressing the data
- Recreate the binary data that you had after encoder step 4 above, and the latent variables that you decoded in encoder step 3 above, as usual in bits-back coding.
- Pass it to the constructor of
ChainCoder
, with additional argumentsis_remainders=True
(seal
always has to beFalse
whenis_remainders=True
because remainders data is guaranteed not to end in a zero word). - Encode the latent variables back onto the new
ChainCoder
(in reverse order), using the same entropy models as during decoding. - Recover the original binary data from encoder step 1 above by calling
.get_data(unseal=True)
(if you setseal=False
in encoder step 2 above, then setunseal=False
now). The method returns two arrays, which you may concatenate in order.
Classes
class ChainCoder (self, compressed, is_remainders=False, seal=False)
-
See above usage instructions for explanation of constructor arguments.
Methods
def clone(self)
-
Creates a deep copy of the coder and returns it.
The returned copy will initially encapsulate the identical compressed data and remainders as the original coder, but the two coders can be used independently without influencing other.
def decode(self, model, *optional_amt_or_model_params)
-
Decodes one or more symbols.
Usage is analogous to
AnsCoder.decode
.Decoding consumes the fixed amount of 24 bits per encoded symbol from the internal "compressed" buffer, regardless of the employed entropy model(s), and it appends (24 bits - inf_content) per symbol to the internal "remainders" buffer (where "inf_content" is the information content of the decoded symbol under the employed entropy model).
def encode_reverse(self, symbols, model, *optional_model_params)
-
Encodes one or more symbols.
Usage is analogous to
AnsCoder.encode_reverse
.Encoding appends the fixed amount of 24 bits per encoded symbol to the internal "compressed" buffer, regardless of the employed entropy model(s), and it consumes (24 bits - inf_content) per symbol from the internal "remainders" buffer (where "inf_content" is the information content of the encoded symbol under the employed entropy model).
def get_data(self, unseal=False)
-
Returns a copy of the compressed data after re-encoding symbols, split into two arrays that you may want to concatenate.
See above usage instructions for further explanation.
def get_remainders(self)
-
Returns a copy of the remainders after decoding some symbols, split into two arrays that you may want to concatenate.
See above usage instructions for further explanation.