Module constriction.stream

Stream codes, i.e., entropy codes that amortize compressed bits over several symbols.

We provide two main stream codes:

  • Range Coding [1, 2] (in submodule queue), which is a computationally more efficient variant of Arithmetic Coding [3], and which has "queue" semantics ("first in first out", i.e., symbols get decoded in the same order in which they were encoded); and
  • Asymmetric Numeral Systems (ANS) [4] (in submodule stack), which has "stack" semantics ("last in first out", i.e., symbols get decoded in reverse order compared to the the order in which they got encoded).

In addition, the submodule model provides common entropy models and wrappers for defining your own entropy models (or for using models from the popular scipy package in constriction). These entropy models can be used with both of the above stream codes.

We further provide an experimental new "Chain Coder" (in submodule chain), which is intended for special new compression methods.

Examples

See top of the documentations of both submodules queue and stack.

References

[1] Pasco, Richard Clark. Source coding algorithms for fast data compression. Diss. Stanford University, 1976.

[2] Martin, G. Nigel N. "Range encoding: an algorithm for removing redundancy from a digitised message." Proc. Institution of Electronic and Radio Engineers International Conference on Video and Data Recording. 1979.

[3] Rissanen, Jorma, and Glen G. Langdon. "Arithmetic coding." IBM Journal of research and development 23.2 (1979): 149-162.

[4] Duda, Jarek, et al. "The use of asymmetric numeral systems as an accurate replacement for Huffman coding." 2015 Picture Coding Symposium (PCS). IEEE, 2015.

Sub-modules

constriction.stream.chain

Experimental entropy coding algorithm for advanced variants of bits-back coding …

constriction.stream.model

Entropy models and model families for use with any of the stream codes from the sister modules stack, queue, and …

constriction.stream.queue

Range Coding: a stream code with queue semantics (i.e., "first in first out") [1, 2] …

constriction.stream.stack

Asymmetric Numeral Systems (ANS): a stream code with stack semantics (i.e., "last in first out") [1] …