Module pi 

Streamlined Apostolico−Drovandi π codes

The streamlined π code with parameter k ≥ 0 of a natural number n is the concatenation of the Rice code with parameter 2ᵏ of ⌊log₂(n + 1)⌋ and of the binary representation of n + 1 with the most significant bit removed.

The implied distribution of a π code with parameter k code is ≈ 1/x^{1 + 1/2ᵏ}.

Note that π₀ = ζ₁ = γ and π₁ = ζ₂. However, due to subtle problems with endianness, in the little-endian case π₁ and ζ₂ have the same codeword lengths but slightly permuted bits.

This module provides a generic implementation of π codes, and a specialized implementation for π₂ that may use tables.

The supported range is [0 . . 2⁶⁴ – 1) for k in [0 . . 64).

In the original paper the definition of the code is very convoluted, as the authors appear to have missed the connection with Rice codes. The codewords implemented by this module are equivalent to the ones in the paper, in the sense that corresponding codewords have the same length, but the codewords for k ≥ 2 are different, and encoding/decoding is faster—hence the name “streamlined π codes”.

References

Alberto Apostolico and Guido Drovandi. “Graph Compression by BFS”, Algorithms, 2:1031-1044, 2009.

Traits

PiRead

Trait for reading π codes.

PiReadParam

Parametric trait for reading π codes.

PiWrite

Trait for writing π codes.

PiWriteParam

Parametric trait for writing π codes.

Functions

len_pi

Returns the length of the π code for n with parameter k using a default value for USE_TABLE.

len_pi_param

Returns the length of the π code with parameter k for n.