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 k 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.

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.

PiWrite

Trait for writing π codes.

Functions

len_pi

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