Trait constriction::stream::model::EntropyModel
source · pub trait EntropyModel<const PRECISION: usize> {
type Symbol;
type Probability: BitArray;
}
Expand description
Base trait for probabilistic models of a data source.
All entropy models (see module level documentation) that can be used for
encoding and/or decoding with stream codes must implement this trait and at least one of
EncoderModel
and/or DecoderModel
. This trait exposes the type of Symbol
s
over which the entropy model is defined, the type that is used to represent a
Probability
in fixed-point arithmetic, and the fixed point PRECISION
(see
discussion of type parameters).
§Blanket Implementation for &impl EntropyModel
We provide the following blanket implementation for references to EntropyModel
s:
impl<M, const PRECISION: usize> EntropyModel<PRECISION> for &M
where
M: EntropyModel<PRECISION> + ?Sized
{ ... }
This means that, if some type M
implements EntropyModel<PRECISION>
for some
PRECISION
, then so does the reference type &M
. Analogous blanket implementations are
provided for the traits EncoderModel
, DecoderModel
, and
IterableEntropyModel
. The implementations simply delegate all calls to M
(which is
possible since all methods only take an &self
receiver). Therefore:
- you don’t need to (and, in fact, currently can’t) implement
EntropyModel
,EncoderModel
, orDecoderModel
for reference types&M
; just implement these traits for “value types”M
and you’ll get the implementation for the corresponding reference types for free. - when you write a function or method that takes a generic entropy model as an argument,
always take the entropy model (formally) by value (i.e., declare your function as
fn f(model: impl EntropyModel<PRECISION>)
or asf<M: EntropyModel<PRECISION>>(model: M)
). Since all references toEntropyModel
s are alsoEntropyModel
s themselves, a function with one of these signatures can be called with an entropy model passed in either by value or by reference. If your function or method needs to pass out several copies ofmodel
then add an extra boundM: Copy
(see, e.g.,Encode::encode_iid_symbols
). This will allow users to call your function either with a reference to an entropy model (all shared references implementCopy
), or with some cheaply copyable entropy model such as a view to a lookup model (seeContiguousLookupDecoderModel::as_view
orNonContiguousLookupDecoderModel::as_view
).
§See Also
Required Associated Types§
sourcetype Symbol
type Symbol
The type of data over which the entropy model is defined.
This is the type of an item of the uncompressed data.
Note that, although any given EntropyModel
has a fixed associated Symbol
type,
this doesn’t prevent you from encoding heterogeneous sequences of symbols where each
symbol has a different type. You can use a different EntropyModel
with a different
associated Symbol
type for each symbol.
sourcetype Probability: BitArray
type Probability: BitArray
The type used to represent probabilities, cumulatives, and quantiles.
This is a primitive unsigned integer type that must hold at least PRECISION
bits.
An integer value p: Probability
semantically represents the probability,
cumulative, or quantile p * 2.0^(-PRECISION)
(where ^
denotes exponentiation and
PRECISION
is a const generic parameter of the trait EntropyModel
).
In many places where constriction
’s public API returns probabilities, they have
already been verified to be nonzero. In such a case, the probability is returned as
a Probability::NonZero
, which denotes the corresponding non-zeroable type (e.g.,
if Probability
is u32
then Probability::NonZero
is
NonZeroU32
). The “bare” Probability
type is mostly used
for left-cumulatives and quantiles (i.e., for points on the y-axis in the graph of a
cumulative distribution function).
§Enforcing the Constraints
Implementations of EntropyModel
are encouraged to enforce the constraint
1 <= PRECISION <= Probability::BITS
. The simplest way to do so is by stating it as an
assertion assert!(1 <= PRECISION && PRECISION <= Probability::BITS)
at the beginning of
relevant methods. This assertion has zero runtime cost because it can be
trivially evaluated at compile time and therefore will be optimized out if it holds.
As of constriction
0.4, implementations provided by constriction
include a similar
assertion that is checked at compile time using const evaluation tricks.
§(Internal) Representation of Probability One
The case of “probability one” is treated specially. This case does not come up in
the public API since we disallow probability one for any individual symbol under any
entropy model, and since all left-sided cumulatives always correspond to a symbol
with nonzero probability. But the value “one” still comes up internally as the
right-cumulative of the last allowed symbol for any model. Although our treatment of
“probability one” can thus be considered an implementation detail, it is likely to
become an issue in third-party implementations of EntropyModel
, so it is worth
documenting our recommended treatment.
We internally represent “probability one” by its normal fixed-point representation
of p = 1 << PRECISION
(i.e., p = 2^PRECISION
in mathematical notation) if this
value fits into Probability
, i.e., if PRECISION != Probability::BITS
. In the
(uncommon) case where PRECISION == Probability::BITS
, we represent “probability
one” as the integer zero (i.e., cutting off the overflowing bit). This means that
any probability that is guaranteed to not be one can always be calculated by
subtracting its left-sided cumulative from its right-sided cumulative in wrapping
arithmetic. However, this convention means that one has to be careful not to confuse
probability zero with probabilty one. In our implementations, these two possible
interpretations of the integer p = 0
always turned out to be easy to disambiguate
statically.