Codage zeta

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 :

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

Mathématiquement, pour coder un entier $N,N\in \left[(2^{k})^{h}..(2^{k})^{h+1}\right]$ , on code d'abord $h={\Big \lfloor }{\dfrac {\lfloor \log _{2}N\rfloor }{k}}{\Big \rfloor }$ en unaire, puis $N-(2^{k})^{h}$ en binaire tronqué avec un alphabet de taille $(2^{k})^{h+1}-(2^{k})^{h}$

On appelle $\zeta _{k}$ la fonction associant à un entier naturel son code zeta paramétré par $k$ .

Le codage zeta de paramètre 1 (utilisant la fonction $\zeta _{1}$ ) 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.

Longueur du code

Partie en code binaire tronqué

Le nombre $N-(2^{k})^{h}$ codé en binaire tronqué nécessite un alphabet de taille $(2^{k})^{h+1}-(2^{k})^{h}=(2^{k}-1)\cdot 2^{kh}$ . Il peut être divisé en $2^{k}-1$ groupes de $2^{kh}$ symboles. Si $kh$ bits de poids faible sont nécessairement écrits, l'indice du premier groupe peut-être tronqué à $k-1$ bits de poids fort. Les $2^{k}-2$ indices suivants sont exprimés avec $k$ bits de poids fort.

Le nombre $N-(2^{k})^{h}$ appartient au premier groupe si :
${\frac {N-(2^{k})^{h}}{2^{kh}}}<1\;\Longleftrightarrow \;{\frac {N}{2^{kh}}}<2\;\Longleftrightarrow \;\log _{2}N-kh=r<1$ avec $r$ le reste de la division entière $\log _{2}N=kh+r$ .

Partie en code unaire

Le nombre $h$ est codé sur $h+1$ bits.

En récapitulatif, le nombre N est codé sur $L=(k+1)(h+1)-{\begin{cases}1&{\text{si }}r<1\\0&{\text{sinon}}\end{cases}}$ bits, avec $h$ et $r$ définis par la division entière $\log _{2}N=kh+r$ .

Exemples

Représentation des premiers entiers naturels strictement positifs avec un codage zeta
Décimal	Binaire	Code gamma	Code zeta k = 1	Code zeta k = 2	Code zeta k = 3	Code zeta k = 4
1	00001	0	0	0 0	0 00	0 000
2	00010	10 0	10 0	0 10	0 010	0 0010
3	00011	10 1	10 1	0 11	0 011	0 0011
4	00100	110 00	110 00	10 000	0 100	0 0100
5	00101	110 01	110 01	10 001	0 101	0 0101
6	00110	110 10	110 10	10 010	0 110	0 0110
7	00111	110 11	110 11	10 011	0 111	0 0111
8	01000	1110 000	1110 000	10 1000	10 00000	0 1000

Voir aussi

Bibliographie

Paolo Boldi, Sebastiano Vigna, « The WebGraph Framework II: Codes for the World-Wide Web », Proceedings of the Data Compression Conference, pp. 528, mars 2004.

Articles connexes

Portail de l’informatique

Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.