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:

  1. The AnsCoder consumes a fixed amount of bits (24 bits in constriction's default configuration) from the end of its encapsulated compressed data; then
  2. the AnsCoder interprets these 24 bits as a number xi between 0.0 and 1.0 in fixed point representation, and it maps xi to a symbol using the entropy model's quantile function (aka percent point function); finally
  3. 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 number xi 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

  1. 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.
  2. Create a ChainCoder, passing into the constructor the binary data and the arguments is_remainders=False and seal=True (you can set seal=False if you know that the data cannot end in a zero word, e.g., if it comes from AnsCoder.get_compressed(unseal=False)).
  3. Decode the latent variables from the ChainCoder as usual in bits-back coding.
  4. 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.
  5. 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 set seal=False in the constructor of AnsCoder), 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

  1. 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.
  2. Pass it to the constructor of ChainCoder, with additional arguments is_remainders=True (seal always has to be False when is_remainders=True because remainders data is guaranteed not to end in a zero word).
  3. Encode the latent variables back onto the new ChainCoder (in reverse order), using the same entropy models as during decoding.
  4. Recover the original binary data from encoder step 1 above by calling .get_data(unseal=True) (if you set seal=False in encoder step 2 above, then set unseal=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.