// Elias Omega – asymptotisch optimale code voor gehele getallen van willekeurige grootte
Nadert het theoretische minimum voor grote getallen.
Codeert lengtes op een elegante, recursieve manier.
Werkt voor elk positief geheel getal zonder extra parameters.
Elias Omega codeert de lengte van een getal recursief totdat de waarde 1 is. We beginnen met n, coderen log₂(n), daarna log₂(log₂(n)) en gaan zo door tot 1. De code bestaat uit deze waarden in omgekeerde volgorde en eindigt met 0. Dit levert log(n) + log(log(n)) + log(log(log(n))) + ... bits op.
n=16: 16 → binair: 10000 (lengte 5) 5 → binair: 101 (lengte 3) 3 → binair: 11 (lengte 2) 2 → binair: 10 (lengte 2) 1 → stop Code achteruit opbouwen: Begin met 0 (terminator) Zet 10 vooraan (codeert 2) Zet 11 vooraan (codeert 3) Zet 101 vooraan (codeert 5) Zet 10000 vooraan (codeert 16) Resultaat: 10 11 101 10000 0 Efficiëntie vergelijken: n=100: Gamma=13, Delta=12, Omega=10 bits n=1000: Gamma=19, Delta=16, Omega=14 bits
Elias Omega is de meest geavanceerde Elias-code en gebruikt recursieve lengtecodering om asymptotische optimaliteit te bereiken. De lengte van de representatie en vervolgens de lengte van die lengte worden herhaaldelijk gecodeerd tot 1, wat zeer efficiënt is voor zeer grote gehele getallen.
Voor kleine getallen (< 10) is Gamma vaak het beste. Voor middelgrote getallen (10–1000) levert Delta kortere codes. Voor grote getallen (> 1000) wordt Omega steeds beter. Omega gebruikt log*(n) iteraties en bereikt een optimaal asymptotisch gedrag.
Een code is asymptotisch optimaal als de verhouding tussen de codelengte en het theoretische minimum naar 1 tendeert wanneer n groeit. Voor Omega geldt: length(n)/log₂(n) → 1 als n → ∞.
Ondanks zijn theoretische voordelen is Omega complexer te implementeren en te decoderen. Voor praktische datasets met begrensde waarden zijn eenvoudigere codes zoals Exp-Golomb of Rice vaak handiger. Omega is vooral nuttig in theoretische analyses en scenario’s met onbegrensde gehele getallen.