Module zeta

Boldi−Vigna ζ codes.

The ζ code with parameter k ≥ 1 of a natural number n is the concatenation of of the unary code of h = ⌊⌊log₂(n + 1)⌋ / k⌋ and of the minimal binary code of n + 1 − 2ʰᵏ with 2⁽ʰ ⁺ ¹⁾ᵏ − 2ʰᵏ as upper bound.

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

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.

References

Paolo Boldi and Sebastiano Vigna. “Codes for the World−Wide Web”. Internet Math., 2(4):405−427, 2005.

Traits

ZetaRead

Trait for reading ζ codes.

ZetaReadParam

Parametric trait for reading ζ codes.

ZetaWrite

Trait for writing ζ codes.

ZetaWriteParam

Parametric trait for writing ζ codes.

Functions

len_zeta

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

len_zeta_param

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