// Elias Omega – asymptotiskt optimal kod för heltal av godtycklig storlek
Närmar sig det teoretiska minimumet för stora tal.
Kodar längder rekursivt på ett elegant sätt.
Fungerar för alla positiva heltal utan extra parametrar.
Elias Omega kodar längden på ett tal rekursivt tills värdet blir 1. Vi börjar med n, kodar log₂(n), sedan log₂(log₂(n)) och fortsätter tills vi når 1. Koden består av dessa värden i omvänd ordning och avslutas med 0. Detta ger log(n) + log(log(n)) + log(log(log(n))) + ... bitar.
n=16: 16 → binärt: 10000 (längd 5) 5 → binärt: 101 (längd 3) 3 → binärt: 11 (längd 2) 2 → binärt: 10 (längd 2) 1 → stopp Bygg koden baklänges: Börja med 0 (terminator) Föranställ 10 (kodar 2) Föranställ 11 (kodar 3) Föranställ 101 (kodar 5) Föranställ 10000 (kodar 16) Resultat: 10 11 101 10000 0 Jämför effektivitet: n=100: Gamma=13, Delta=12, Omega=10 bitar n=1000: Gamma=19, Delta=16, Omega=14 bitar
Elias Omega är den mest avancerade koden i Elias‑familjen och använder rekursiv längdkodning för att uppnå asymptotisk optimalitet. Den kodar längden på representationen, sedan längden på den längden och så vidare tills 1, vilket ger en mycket effektiv kod för mycket stora heltal.
För små tal (< 10) är Gamma ofta bäst. För medelstora tal (10–1000) ger Delta kortare koder. För stora tal (> 1000) blir Omega alltmer överlägsen. Omega använder log*(n)‑iterationer och uppnår asymptotiskt optimalt beteende.
En kod är asymptotiskt optimal när förhållandet mellan dess längd och det teoretiska minimumet går mot 1 när n växer. För Omega gäller: length(n)/log₂(n) → 1 när n → ∞.
Trots sin teoretiska överlägsenhet är Omega mer komplex att implementera och avkoda. För praktiska datasätt med begränsade heltal är enklare koder som Exp-Golomb eller Rice ofta mer lämpliga. Omega används främst i teoretiska analyser och scenarier med obegränsade heltal.