Codage zeta - Définition

Introduction

Le codage zeta ou codage de Boldi-Vigna est un codage entropique inventé par Paolo Boldi et Sebastiano Vigna en 2003 et utilisé essentiellement en compression de graphes.

Le code zeta produit est un code préfixe et universel.

Principe

Le codage zeta d'un entier naturel N dépend d'un paramètre k et se fait en deux étapes :

1. le codage de l'exposant de la plus grande puissance de 2^k inférieure ou égale à N avec un codage unaire ;
2. le codage de la différence entre N et cette plus grande puissance avec un codage binaire tronqué.

Mathématiquement, pour coder un entier , on code d'abord en unaire, puis N − (2^k)^h en binaire tronqué avec un alphabet de taille (2^k)^{h + 1} − (2^k)^h

On appelle ζ_k la fonction associant à un entier naturel son code zeta paramétré par k.

Le codage zeta de paramètre 1 (utilisant la fonction ζ₁) est équivalent au codage gamma et produit exactement les mêmes codes.

Codage des entiers relatifs

Comme pour les codages gamma, delta et omega, il est possible de coder des entiers relatifs avec le codage zeta en utilisant une bijection pour transformer les nombres négatifs ou nul en nombres strictement positifs avant le codage à proprement parler. Après le décodage, l'opération inverse doit être effectuée pour retrouver les entiers relatifs d'origine.

Exemples