// Elias Omega – code asymptotiquement optimal pour des entiers arbitrairement grands
Se rapproche du minimum théorique pour de grands nombres.
Encode récursivement les longueurs de manière élégante.
Fonctionne pour tout entier positif sans paramètre supplémentaire.
Elias Omega encode récursivement la longueur d’un nombre jusqu’à atteindre 1. À partir de n, on encode log₂(n), puis log₂(log₂(n)), et ainsi de suite jusqu’à 1. Le code est constitué de ces valeurs en ordre inverse et se termine par 0. On obtient ainsi log(n) + log(log(n)) + log(log(log(n))) + ... bits.
n=16 : 16 → binaire : 10000 (longueur 5) 5 → binaire : 101 (longueur 3) 3 → binaire : 11 (longueur 2) 2 → binaire : 10 (longueur 2) 1 → arrêt Construire le code à rebours : Commencer par 0 (terminateur) Préfixer 10 (encode 2) Préfixer 11 (encode 3) Préfixer 101 (encode 5) Préfixer 10000 (encode 16) Résultat : 10 11 101 10000 0 Comparer l’efficacité : n=100 : Gamma=13, Delta=12, Omega=10 bits n=1000 : Gamma=19, Delta=16, Omega=14 bits
Elias Omega est le code d’Elias le plus sophistiqué. Il utilise un encodage récursif des longueurs pour atteindre l’optimalité asymptotique. Il encode la longueur de la représentation, puis la longueur de cette longueur, et ainsi de suite jusqu’à 1, ce qui le rend très efficace pour de très grands entiers.
Pour les petits nombres (< 10), Gamma est souvent le meilleur choix. Pour les valeurs moyennes (10–1000), Delta améliore Gamma. Pour les grands nombres (> 1000), Omega devient de plus en plus avantageux. Omega utilise log*(n) itérations et atteint un comportement optimal à l’infini.
Un code est asymptotiquement optimal lorsque le rapport entre sa longueur et le minimum théorique tend vers 1 à mesure que les nombres grandissent. Omega vérifie cette propriété : length(n)/log₂(n) → 1 quand n → ∞.
Malgré sa supériorité théorique, Omega est plus complexe à implémenter et à décoder. Pour des données réelles avec des entiers bornés, des codes plus simples comme Exp-Golomb ou Rice sont souvent plus pratiques. Omega est surtout utilisé en analyse théorique et pour des entiers non bornés.