Module constriction::stream::chain

source ·
Expand description

Experimental entropy coding algorithm for advanced variants of bitsback 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 then changing 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 example illustrates how decoding differs between an AnsCoder and a ChainCoder. We decode the same bitstring data twice with each coder: once with a sequence of toy entropy models, and then a second time with slightly different sequence of entropy models. Importantly, only the entropy model for the first decoded symbol differs between the two applications of each coder. We then observe that

  • with the AnsCoder, changing the first entropy model affects not only the first decoded symbol but also has a ripple effect that can affect subsequently decoded symbols; while
  • with the ChainCoder, changing the first entropy model affects only the first decoded symbol; all subsequently decoded symbols remain unchanged.
use constriction::stream::{
    model::DefaultContiguousCategoricalEntropyModel,
    stack::DefaultAnsCoder, chain::DefaultChainCoder, Decode
};

/// Shorthand for decoding a sequence of symbols with categorical entropy models.
fn decode_categoricals<Decoder: Decode<24, Word = u32>>(
    decoder: &mut Decoder,
    probabilities: &[[f64; 4]],
) -> Vec<usize> {
    let entropy_models = probabilities
        .iter()
        .map(
            |probs| DefaultContiguousCategoricalEntropyModel
                ::from_floating_point_probabilities(probs).unwrap()
        );
    decoder.decode_symbols(entropy_models).collect::<Result<Vec<_>, _>>().unwrap()
}

// Let's define some sample binary data and some probabilities for our entropy models
let data = vec![0x80d1_4131, 0xdda9_7c6c, 0x5017_a640, 0x0117_0a3d];
let mut probabilities = [
    [0.1, 0.7, 0.1, 0.1], // Probabilities for the entropy model of the first decoded symbol.
    [0.2, 0.2, 0.1, 0.5], // Probabilities for the entropy model of the second decoded symbol.
    [0.2, 0.1, 0.4, 0.3], // Probabilities for the entropy model of the third decoded symbol.
];

// Decoding the binary data with an `AnsCoder` results in the symbols `[0, 0, 1]`.
let mut ans_coder = DefaultAnsCoder::from_binary(data.clone()).unwrap();
let symbols = decode_categoricals(&mut ans_coder, &probabilities);
assert_eq!(symbols, [0, 0, 1]);

// Even if we change only the first entropy model (slightly), *all* decoded symbols can change:
probabilities[0] = [0.09, 0.71, 0.1, 0.1]; // was: `[0.1, 0.7, 0.1, 0.1]`
let mut ans_coder = DefaultAnsCoder::from_binary(data.clone()).unwrap();
let symbols = decode_categoricals(&mut ans_coder, &probabilities);
assert_eq!(symbols, [1, 0, 3]); // (instead of `[0, 0, 1]` from above)
// 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.
// --> Changes to entropy models (and also to compressed bits) have a *global* effect.

// Let's try the same with a `ChainCoder`:
probabilities[0] = [0.1, 0.7, 0.1, 0.1]; // Restore original entropy model for first symbol.
let mut chain_coder = DefaultChainCoder::from_binary(data.clone()).unwrap();
let symbols = decode_categoricals(&mut chain_coder, &probabilities);
assert_eq!(symbols, [0, 3, 3]);
// We get different symbols than for the `AnsCoder`, of course, but that's not the point here.

probabilities[0] = [0.09, 0.71, 0.1, 0.1]; // Change the first entropy model again slightly.
let mut chain_coder = DefaultChainCoder::from_binary(data).unwrap();
let symbols = decode_categoricals(&mut chain_coder, &probabilities);
assert_eq!(symbols, [1, 3, 3]); // (instead of `[0, 3, 3]` from above)
// The only symbol that changed was the one whose entropy model we had changed.
// --> 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?

TODO

Structs

Enums

Type Aliases