// Elias Omega – asymptotisk optimal kode for heltall av vilkårlig størrelse
Nærmer seg det teoretiske minimumet for store tall.
Koder lengder rekursivt på en elegant måte.
Fungerer for alle positive heltall uten ekstra parametere.
Elias Omega koder lengden til et tall rekursivt helt til verdien blir 1. Vi starter med n, koder log₂(n), deretter log₂(log₂(n)) og fortsetter til vi når 1. Koden består av disse verdiene i omvendt rekkefølge og avsluttes med 0. Dette gir log(n) + log(log(n)) + log(log(log(n))) + ... biter.
n=16: 16 → binær: 10000 (lengde 5) 5 → binær: 101 (lengde 3) 3 → binær: 11 (lengde 2) 2 → binær: 10 (lengde 2) 1 → stopp Bygg koden baklengs: Start med 0 (terminator) Foranstill 10 (koder 2) Foranstill 11 (koder 3) Foranstill 101 (koder 5) Foranstill 10000 (koder 16) Resultat: 10 11 101 10000 0 Sammenlign effektivitet: n=100: Gamma=13, Delta=12, Omega=10 biter n=1000: Gamma=19, Delta=16, Omega=14 biter
Elias Omega er den mest avanserte Elias-koden og bruker rekursiv lengdekoding for å oppnå asymptotisk optimalitet. Den koder lengden på representasjonen, deretter lengden av den lengden osv. helt til 1, noe som gir en svært effektiv kode for svært store heltall.
For små tall (< 10) er Gamma ofte best. For middels store tall (10–1000) gir Delta bedre resultater enn Gamma. For store tall (> 1000) blir Omega stadig mer effektiv. Omega bruker log*(n) iterasjoner og oppnår optimal asymptotisk oppførsel.
En kode er asymptotisk optimal når forholdet mellom kodelengden og det teoretiske minimumet går mot 1 når n vokser. For Omega gjelder: length(n)/log₂(n) → 1 når n → ∞.
Selv om Omega er teoretisk overlegent, er den mer kompleks å implementere og dekode. For praktiske datasett med begrensede heltall er enklere koder som Exp-Golomb eller Rice ofte å foretrekke. Omega brukes hovedsakelig i teoretiske analyser og scenarier med ubegrensede heltall.