Struct NonContiguousCategoricalDecoderModel

pub struct NonContiguousCategoricalDecoderModel<Symbol, Probability, Cdf, const PRECISION: usize> { /* private fields */ }

An entropy model for a categorical probability distribution over arbitrary symbols, for decoding only.

You will usually want to use this type through one of its type aliases, DefaultNonContiguousCategoricalDecoderModel or SmallNonContiguousCategoricalDecoderModel, see discussion of presets.

This type implements the trait DecoderModel but not the trait EncoderModel. Thus, you can use a NonContiguousCategoricalDecoderModel for decoding with any of the stream decoders provided by the constriction crate, but not for encoding. If you want to encode data, use a NonContiguousCategoricalEncoderModel instead. You can convert a NonContiguousCategoricalDecoderModel to a NonContiguousCategoricalEncoderModel by calling to_generic_encoder_model on it (you’ll have to bring the trait IterableEntropyModel into scope to do so: use constriction::stream::model::IterableEntropyModel).

Example

See example for NonContiguousCategoricalEncoderModel.

When Should I Use This Type of Entropy Model?

Use a NonContiguousCategoricalDecoderModel for probabilistic models that can only be represented as an explicit probability table, and not by some more compact analytic expression.

• If you have a probability model that can be expressed by some analytical expression (e.g., a Binomial distribution), then use LeakyQuantizer instead (unless you want to encode lots of symbols with the same entropy model, in which case the explicitly tabulated representation of a categorical entropy model could improve runtime performance).
• If the support of your probabilistic model (i.e., the set of symbols to which the model assigns a non-zero probability) is a contiguous range of integers starting at zero, then it is better to use a ContiguousCategoricalEntropyModel. It has better computational efficiency and it is easier to use since it supports both encoding and decoding with a single type.
• If you want to decode only a few symbols with a given probability model, then use a LazyContiguousCategoricalEntropyModel, which will be faster (use an array to map the decoded symbols from the contiguous range 0..N to whatever noncontiguous alphabet you have). This use case occurs, e.g., in autoregressive models, where each individual model is often used for only exactly one symbol.
• If you want to decode lots of symbols with the same entropy model, and if reducing the PRECISION to a moderate value is acceptable to you, then you may want to consider using a NonContiguousLookupDecoderModel instead for even better runtime performance (at the cost of a larger memory footprint and worse compression efficiency due to lower PRECISION).

Computational Efficiency

For a probability distribution with a support of N symbols, a NonContiguousCategoricalDecoderModel has the following asymptotic costs:

• creation:
  • runtime cost: Θ(N log(N)) (when creating with the ..._fast constructor);
  • memory footprint: Θ(N);
• encoding a symbol: not supported; use a NonContiguousCategoricalEncoderModel instead.
• decoding a symbol (calling DecoderModel::quantile_function):
  • runtime cost: Θ(log(N)) (both expected and worst-case)
  • memory footprint: no heap allocations, constant stack space.

Implementations

impl<Symbol, Probability: BitArray, const PRECISION: usize> NonContiguousCategoricalDecoderModel<Symbol, Probability, Vec<(Probability, Symbol)>, PRECISION>

where Symbol: Clone,

pub fn from_symbols_and_floating_point_probabilities_fast<F>( symbols: impl IntoIterator<Item = Symbol>, probabilities: &[F], normalization: Option<F>, ) -> Result<Self, ()>

where F: FloatCore + Sum<F> + AsPrimitive<Probability>, Probability: AsPrimitive<usize>, usize: AsPrimitive<Probability> + AsPrimitive<F>,

Constructs a leaky distribution (for decoding) over the provided symbols whose PMF approximates given probabilities.

Semantics are analogous to ContiguousCategoricalEntropyModel::from_floating_point_probabilities_fast, except that this constructor has an additional symbols argument to provide an iterator over the symbols in the alphabet (which has to yield exactly probabilities.len() symbols).

See also

• from_symbols_and_floating_point_probabilities_perfect, which can be considerably slower but typically approximates the provided probabilities very slightly better.

pub fn from_symbols_and_floating_point_probabilities_perfect<F>( symbols: impl IntoIterator<Item = Symbol>, probabilities: &[F], ) -> Result<Self, ()>

where F: FloatCore + Sum<F> + Into<f64>, Probability: Into<f64> + AsPrimitive<usize>, f64: AsPrimitive<Probability>, usize: AsPrimitive<Probability>,

Slower variant of from_symbols_and_floating_point_probabilities_fast.

Similar to from_symbols_and_floating_point_probabilities_fast, but the resulting (fixed-point precision) model typically approximates the provided floating point probabilities very slightly better. Only recommended if compression performance is much more important to you than runtime as this constructor can be significantly slower.

See ContiguousCategoricalEntropyModel::from_floating_point_probabilities_perfect for a detailed comparison between ..._fast and ..._perfect constructors of categorical entropy models.

pub fn from_symbols_and_floating_point_probabilities<F>( symbols: &[Symbol], probabilities: &[F], ) -> Result<Self, ()>

where F: FloatCore + Sum<F> + Into<f64>, Probability: Into<f64> + AsPrimitive<usize>, f64: AsPrimitive<Probability>, usize: AsPrimitive<Probability>,

👎Deprecated since 0.4.0: Please use from_symbols_and_floating_point_probabilities_fast or from_symbols_and_floating_point_probabilities_perfect instead. See documentation for detailed upgrade instructions.

Deprecated constructor.

This constructor has been deprecated in constriction version 0.4.0, and it will be removed in constriction version 0.5.0.

Upgrade Instructions

Most new use cases should call from_symbols_and_floating_point_probabilities_fast instead. Using that constructor (abbreviated as ..._fast in the following) may lead to very slightly larger bit rates, but it runs considerably faster.

However, note that the ..._fast constructor breaks binary compatibility with constriction version <= 0.3.5. If you need to be able to exchange binary compressed data with a program that uses a categorical entropy model from constriction version <= 0.3.5, then call from_symbols_and_floating_point_probabilities_perfect instead (..._perfect for short). Another reason for using the ..._perfect constructor could be if compression performance is much more important to you than runtime performance. See documentation of from_symbols_and_floating_point_probabilities_perfect for more information.

Compatibility Table

(In the following table, “encoding” refers to NonContiguousCategoricalEncoderModel)

constructor used for encoding → ↓ constructor used for decoding ↓	legacy	..._perfect	..._fast
legacy (this one)	✅ compatible	✅ compatible	❌ incompatible
..._perfect	✅ compatible	✅ compatible	❌ incompatible
..._fast	❌ incompatible	❌ incompatible	✅ compatible

pub fn from_symbols_and_nonzero_fixed_point_probabilities<S, P>( symbols: S, probabilities: P, infer_last_probability: bool, ) -> Result<Self, ()>

where S: IntoIterator<Item = Symbol>, P: IntoIterator, P::Item: Borrow<Probability>,

Constructs a distribution with a PMF given in fixed point arithmetic.

This is a low level method that allows, e.g,. reconstructing a probability distribution previously exported with symbol_table. The more common way to construct a NonContiguousCategoricalDecoderModel is via from_symbols_and_floating_point_probabilities_fast.

The items of probabilities have to be nonzero and smaller than 1 << PRECISION, where PRECISION is a const generic parameter on the NonContiguousCategoricalDecoderModel.

If infer_last_probability is false then probabilities must yield the same number of items as symbols does, and the items yielded by probabilities have to to (logically) sum up to 1 << PRECISION. If infer_last_probability is true then probabilities must yield one fewer item than symbols, they must sum up to a value strictly smaller than 1 << PRECISION, and the method will assign the (nonzero) remaining probability to the last symbol.

Example

Creating a NonContiguousCategoricalDecoderModel with inferred probability of the last symbol:

use constriction::stream::model::{
    DefaultNonContiguousCategoricalDecoderModel, IterableEntropyModel
};

let partial_probabilities = vec![1u32 << 21, 1 << 22, 1 << 22, 1 << 22];
// `partial_probabilities` sums up to strictly less than `1 << PRECISION` as required:
assert!(partial_probabilities.iter().sum::<u32>() < 1 << 24);

let symbols = "abcde"; // Has one more entry than `probabilities`

let model = DefaultNonContiguousCategoricalDecoderModel
    ::from_symbols_and_nonzero_fixed_point_probabilities(
        symbols.chars(), &partial_probabilities, true).unwrap();
let symbol_table = model.floating_point_symbol_table::<f64>().collect::<Vec<_>>();
assert_eq!(
    symbol_table,
    vec![
        ('a', 0.0, 0.125),
        ('b', 0.125, 0.25),
        ('c', 0.375, 0.25),
        ('d', 0.625, 0.25),
        ('e', 0.875, 0.125), // Inferred last probability.
    ]
);

For more related examples, see ContiguousCategoricalEntropyModel::from_nonzero_fixed_point_probabilities.

pub fn from_iterable_entropy_model<'m, M>(model: &'m M) -> Self

where M: IterableEntropyModel<'m, PRECISION, Symbol = Symbol, Probability = Probability> + ?Sized,

Creates a NonContiguousCategoricalDecoderModel from any entropy model that implements IterableEntropyModel.

Calling NonContiguousCategoricalDecoderModel::from_iterable_entropy_model(&model) is equivalent to calling model.to_generic_decoder_model(), where the latter requires bringing IterableEntropyModel into scope.

impl<Symbol, Probability, Cdf, const PRECISION: usize> NonContiguousCategoricalDecoderModel<Symbol, Probability, Cdf, PRECISION>

where Symbol: Clone, Probability: BitArray, Cdf: AsRef<[(Probability, Symbol)]>,

pub fn support_size(&self) -> usize

Returns the number of symbols supported by the model, i.e., the number of symbols to which the model assigns a nonzero probability.

pub fn as_view( &self, ) -> NonContiguousCategoricalDecoderModel<Symbol, Probability, &[(Probability, Symbol)], PRECISION>

Makes a very cheap shallow copy of the model that can be used much like a shared reference.

The returned NonContiguousCategoricalDecoderModel implements Copy, which is a requirement for some methods, such as Decode::decode_iid_symbols. These methods could also accept a shared reference to a NonContiguousCategoricalDecoderModel (since all references to entropy models are also entropy models, and all shared references implement Copy), but passing a view instead may be slightly more efficient because it avoids one level of dereferencing.

pub fn to_lookup_decoder_model( &self, ) -> NonContiguousLookupDecoderModel<Symbol, Probability, Vec<(Probability, Symbol)>, Box<[Probability]>, PRECISION>

where Probability: Into<usize>, usize: AsPrimitive<Probability>,

Creates a ContiguousLookupDecoderModel or NonContiguousLookupDecoderModel for efficient decoding of i.i.d. data

While a NonContiguousCategoricalEntropyModel can already be used for decoding (since it implements DecoderModel), you may prefer converting it to a LookupDecoderModel first for improved efficiency. Logically, the two will be equivalent.

Warning

You should only call this method if both of the following conditions are satisfied:

• PRECISION is relatively small (typically PRECISION == 12, as in the “Small” preset) because the memory footprint of a LookupDecoderModel grows exponentially in PRECISION; and
• you’re about to decode a relatively large number of symbols with the resulting model; the conversion to a LookupDecoderModel bears a significant runtime and memory overhead, so if you’re going to use the resulting model only for a single or a handful of symbols then you’ll end up paying more than you gain.

Trait Implementations

impl<Symbol: Clone, Probability: Clone, Cdf: Clone, const PRECISION: usize> Clone for NonContiguousCategoricalDecoderModel<Symbol, Probability, Cdf, PRECISION>

fn clone( &self, ) -> NonContiguousCategoricalDecoderModel<Symbol, Probability, Cdf, PRECISION>

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<Symbol: Debug, Probability: Debug, Cdf: Debug, const PRECISION: usize> Debug for NonContiguousCategoricalDecoderModel<Symbol, Probability, Cdf, PRECISION>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<Symbol, Probability, Cdf, const PRECISION: usize> DecoderModel<PRECISION> for NonContiguousCategoricalDecoderModel<Symbol, Probability, Cdf, PRECISION>

where Symbol: Clone, Probability: BitArray, Cdf: AsRef<[(Probability, Symbol)]>,

fn quantile_function( &self, quantile: Self::Probability, ) -> (Symbol, Probability, Probability::NonZero)

Looks up the symbol for a given quantile.

impl<Symbol, Probability, Cdf, const PRECISION: usize> EntropyModel<PRECISION> for NonContiguousCategoricalDecoderModel<Symbol, Probability, Cdf, PRECISION>

where Probability: BitArray,

type Symbol = Symbol

The type of data over which the entropy model is defined.

type Probability = Probability

The type used to represent probabilities, cumulatives, and quantiles.

impl<'m, Symbol, Probability, M, const PRECISION: usize> From<&'m M> for NonContiguousCategoricalDecoderModel<Symbol, Probability, Vec<(Probability, Symbol)>, PRECISION>

where Symbol: Clone, Probability: BitArray, M: IterableEntropyModel<'m, PRECISION, Symbol = Symbol, Probability = Probability> + ?Sized,

fn from(model: &'m M) -> Self

Converts to this type from the input type.

impl<'m, Symbol, Probability, Cdf, const PRECISION: usize> IterableEntropyModel<'m, PRECISION> for NonContiguousCategoricalDecoderModel<Symbol, Probability, Cdf, PRECISION>

where Symbol: Clone + 'm, Probability: BitArray, Cdf: AsRef<[(Probability, Symbol)]>,

fn symbol_table( &'m self, ) -> impl Iterator<Item = (Self::Symbol, Self::Probability, <Self::Probability as BitArray>::NonZero)>

Iterates over all symbols in the unique order that is consistent with the cumulative distribution.

fn floating_point_symbol_table<F>( &'m self, ) -> impl Iterator<Item = (Self::Symbol, F, F)>

where F: FloatCore + From<Self::Probability> + 'm, Self::Probability: Into<F>,

Similar to symbol_table, but yields both cumulatives and probabilities in floating point representation.

fn entropy_base2<F>(&'m self) -> F

where F: Float + Sum, Self::Probability: Into<F>,

Returns the entropy in units of bits (i.e., base 2).

fn to_generic_encoder_model( &'m self, ) -> NonContiguousCategoricalEncoderModel<Self::Symbol, Self::Probability, PRECISION>

where Self::Symbol: Hash + Eq,

Creates an EncoderModel from this EntropyModel

fn to_generic_decoder_model( &'m self, ) -> NonContiguousCategoricalDecoderModel<Self::Symbol, Self::Probability, Vec<(Self::Probability, Self::Symbol)>, PRECISION>

where Self::Symbol: Clone,

Creates a DecoderModel from this EntropyModel

fn to_generic_lookup_decoder_model( &'m self, ) -> NonContiguousLookupDecoderModel<Self::Symbol, Self::Probability, Vec<(Self::Probability, Self::Symbol)>, Box<[Self::Probability]>, PRECISION>

where Self::Probability: Into<usize>, usize: AsPrimitive<Self::Probability>, Self::Symbol: Clone + Default,

Creates a DecoderModel from this EntropyModel

fn cross_entropy_base2<F>(&'m self, p: impl IntoIterator<Item = F>) -> F

where F: Float + Sum, Self::Probability: Into<F>,

Returns the cross entropy between argument p and this model in units of bits (i.e., base 2).

fn reverse_cross_entropy_base2<F>(&'m self, p: impl IntoIterator<Item = F>) -> F

where F: Float + Sum, Self::Probability: Into<F>,

Returns the cross entropy between this model and argument p in units of bits (i.e., base 2).

fn kl_divergence_base2<F>(&'m self, p: impl IntoIterator<Item = F>) -> F

where F: Float + Sum, Self::Probability: Into<F>,

Returns Kullback-Leibler divergence D_KL(p || self)

fn reverse_kl_divergence_base2<F>(&'m self, p: impl IntoIterator<Item = F>) -> F

where F: Float + Sum, Self::Probability: Into<F>,

Returns reverse Kullback-Leibler divergence, i.e., D_KL(self || p)

impl<Symbol: Copy, Probability: Copy, Cdf: Copy, const PRECISION: usize> Copy for NonContiguousCategoricalDecoderModel<Symbol, Probability, Cdf, PRECISION>