Codage zeta
- 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 2k 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 ]](0/bd03db7b0902b2bda29129bb97b7ca87.png)
, on code d'abord 
en unaire, puis N − (2k)h en binaire tronqué avec un alphabet de taille (2k)h + 1 − (2k)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 ζ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
Cette section est vide, insuffisamment détaillée ou incomplète.
Votre aide est la bienvenue !
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
Articles connexes
Wikimedia Foundation.
2010.
Contenu soumis à la licence CC-BY-SA. Source : Article Codage zeta de Wikipédia en français (auteurs)
Regardez d'autres dictionnaires:
Codage gamma — Le codage gamma ou codage gamma d Elias est un codage entropique inventé par Peter Elias et utilisé essentiellement en compression de données. Le code gamma produit est un code préfixe et universel. Sommaire 1 Principe 2 Codage des entiers… … Wikipédia en Français
Codage binaire tronqué — Le codage binaire tronqué est un codage entropique utilisé essentiellement en compression de données et s appuyant sur la base 2. Il est plus généralement utilisé pour coder de façon efficace en termes de longueur, un alphabet dont la taille n… … Wikipédia en Français
Codage entropique — Le codage entropique (ou codage statistique à longueur variable) est une méthode de codage de source sans pertes, dont le but est de transformer la représentation d une source de données pour sa compression et/ou sa transmission sur un canal de… … Wikipédia en Français
Codage delta — Pour les articles homonymes, voir Code Delta (émission de télévision). Le codage delta ou codage delta d Elias est un codage entropique inventé par Peter Elias et utilisé essentiellement en compression de données. Le code delta produit est un… … Wikipédia en Français
Codage omega — Le codage omega ou codage omega d Elias est un codage entropique inventé par Peter Elias et utilisé essentiellement en compression de données. Le code omega produit est un code préfixe et universel. Sommaire 1 Principe 1.1 Codage 1.2 Décodage … Wikipédia en Français
Codage de Huffman — Le codage de Huffman est un algorithme de compression de données sans perte élaboré par David Albert Huffman, lors de sa thèse de doctorat au MIT. L algorithme a été publié en 1952 dans l article A Method for the Construction of Minimum… … Wikipédia en Français
Codage de Rice — Le codage de Rice, codage de Golomb Rice ou GPO2 (pour Golomb power of 2) est un codage entropique inventé par Robert F. Rice et James R. Plaunt en 1971 et utilisé essentiellement en compression de données. Le code produit est un code préfixe.… … Wikipédia en Français
Codage de Golomb — Le codage de Golomb est un codage entropique inventé par Solomon Wolf Golomb en 1966 et utilisé essentiellement en compression de données. Le code produit est un code préfixe. Sommaire 1 Principe 2 Longueur du code 3 Optimalité … Wikipédia en Français
Codage de Shannon-Fano — Le codage de Shannon Fano est un algorithme de compression de données sans perte élaboré par Robert Fano à partir d une idée de Claude Shannon. Il s agit d un codage entropique produisant un code préfixe très similaire à un code de Huffman, bien… … Wikipédia en Français
Codage unaire — Le codage unaire est un codage entropique utilisé essentiellement en compression de données et s appuyant sur la base 1. Sommaire 1 Principe 2 Longueur du code 3 Optimalité 4 … Wikipédia en Français
