// Elias Omega – asymptotisch optimaler Code für ganze Zahlen beliebiger Größe
Nähert sich für große Zahlen dem theoretischen Minimum.
Codiert Längen rekursiv und elegant.
Funktioniert für jede positive ganze Zahl ohne Parameter.
Elias Omega codiert die Länge einer Zahl rekursiv, bis der Wert 1 erreicht wird. Ausgehend von n codieren wir log₂(n), dann log₂(log₂(n)) und so weiter, bis wir 1 erreichen. Der Code besteht aus diesen Werten in umgekehrter Reihenfolge und endet mit 0. Dadurch ergeben sich log(n) + log(log(n)) + log(log(log(n))) + … Bits.
n=16: 16 → binär: 10000 (Länge 5) 5 → binär: 101 (Länge 3) 3 → binär: 11 (Länge 2) 2 → binär: 10 (Länge 2) 1 → Stopp Code rückwärts aufbauen: Beginne mit 0 (Terminator) Stelle 10 voran (codiert 2) Stelle 11 voran (codiert 3) Stelle 101 voran (codiert 5) Stelle 10000 voran (codiert 16) Ergebnis: 10 11 101 10000 0 Effizienz vergleichen: n=100: Gamma=13, Delta=12, Omega=10 Bits n=1000: Gamma=19, Delta=16, Omega=14 Bits
Elias Omega ist der anspruchsvollste Elias-Code und verwendet rekursive Längencodierung, um asymptotische Optimalität zu erreichen. Die Länge einer Zahl wird immer wieder codiert, bis 1 erreicht ist. Das ergibt eine sehr effiziente Codierung für sehr große ganze Zahlen.
Für kleine Zahlen (< 10) ist Gamma oft am besten. Für mittlere Zahlen (10–1000) verbessert Delta Gamma. Für große Zahlen (> 1000) wird Omega zunehmend überlegen. Omega verwendet log*(n)-Iterationen und erreicht ein optimales asymptotisches Verhalten.
Eine Codierung ist asymptotisch optimal, wenn sich das Verhältnis ihrer Länge zum theoretischen Minimum gegen 1 bewegt, wenn n wächst. Omega erfüllt dies: length(n)/log₂(n) → 1 für n → ∞.
Trotz seiner theoretischen Überlegenheit ist Omega komplizierter zu implementieren und zu dekodieren. Für praktische Daten mit begrenzten Werten sind einfachere Codes wie Exp-Golomb oder Rice oft ausreichend oder besser. Omega glänzt vor allem in der Theorie und bei unbeschränkten Integern.