> elias | gamma | universel <
// Elias Gamma – code universel pour entiers positifs sans paramètres
Code universel
Fonctionne pour tout entier positif sans réglage de paramètres.
Sans préfixe
Aucun code n'est le préfixe d'un autre, ce qui garantit un décodage unique.
Asymptotiquement optimal
S'approche de la compression optimale pour certaines distributions.
>> informations techniques
Comment fonctionne Elias Gamma:
Elias Gamma code un entier positif n en : 1) trouvant N = ⌊log₂(n)⌋, 2) écrivant N zéros en code unaire, 3) ajoutant la représentation binaire de n (qui contient N+1 bits). Le résultat est un code de (2N+1) bits.
Exemples d'encodage:
n=1 : log₂(1)=0 Code : 1 (aucun zéro + "1") n=2 : log₂(2)=1 Code : 010 (un zéro + "10") n=5 : log₂(5)=2 Code : 00101 (deux zéros + "101") n=10 : log₂(10)=3 Code : 0001010 (trois zéros + "1010") Formule de longueur : 2⌊log₂(n)⌋ + 1
Pourquoi utiliser Elias Gamma ?:
- >Aucun paramètre requis
- >Implémentation simple
- >Efficace pour les petits entiers
- >Code universel avec des propriétés théoriques claires
- >Important en théorie de l'information et de la compression
>> foire aux questions
Qu'est‑ce que le codage Elias Gamma ?
Elias Gamma est un code universel pour les entiers positifs, proposé par Peter Elias. Chaque entier est codé à l'aide de la longueur de sa représentation binaire en unaire, suivie de la représentation binaire elle‑même. On parle de code « universel » car il fonctionne sans connaître la distribution des données.
Quand Elias Gamma est‑il efficace ?
Elias Gamma est particulièrement efficace pour des entiers suivant une loi de puissance (P(n) ∝ n^-2). Il utilise environ 2log₂(n)+1 bits, ce qui est adapté aux petites valeurs mais moins efficace pour les grands nombres.
Gamma vs Delta vs Omega ?
Elias Gamma utilise 2log₂(n)+1 bits. Delta améliore cela à log₂(n)+2log₂(log₂(n)+1)+1 bits, et Omega apporte encore de meilleurs résultats pour de très grands nombres. Gamma est le plus simple, Delta est meilleur pour les valeurs moyennes et Omega pour les grands n.
Où les codes Elias sont‑ils utilisés ?
Les codes Elias sont utilisés en théorie de l'information, dans la recherche sur la compression de données et dans certains algorithmes de compression spécialisés. Ils sont importants sur le plan théorique comme codes universels, mais restent moins utilisés en pratique que le codage de Huffman ou arithmétique.