// Elias Omega – asymptotisk optimal kode til heltal af vilkårlig størrelse
Nærmer sig det teoretiske minimum for store tal.
Koder længder rekursivt på en elegant måde.
Virker for alle positive heltal uden ekstra parametre.
Elias Omega koder længden af et tal rekursivt, indtil værdien bliver 1. Vi starter med n, koder log₂(n), derefter log₂(log₂(n)) og fortsætter, indtil vi når 1. Koden består af disse værdier i omvendt rækkefølge og afsluttes med 0. Det giver log(n) + log(log(n)) + log(log(log(n))) + ... bits.
n=16: 16 → binær: 10000 (længde 5) 5 → binær: 101 (længde 3) 3 → binær: 11 (længde 2) 2 → binær: 10 (længde 2) 1 → stop Byg koden baglæns: Start med 0 (terminator) Foranstil 10 (koder 2) Foranstil 11 (koder 3) Foranstil 101 (koder 5) Foranstil 10000 (koder 16) Resultat: 10 11 101 10000 0 Sammenlign effektivitet: n=100: Gamma=13, Delta=12, Omega=10 bits n=1000: Gamma=19, Delta=16, Omega=14 bits
Elias Omega er den mest avancerede Elias-kode og bruger rekursiv længdekodning for at opnå asymptotisk optimalitet. Den koder længden, derefter længden af længden osv. indtil 1, hvilket giver en meget effektiv kode for meget store heltal.
For små tal (< 10) er Gamma ofte bedst. For mellemstore tal (10–1000) giver Delta kortere koder. For store tal (> 1000) bliver Omega gradvist bedre. Omega bruger log*(n) iterationer og opnår optimal asymptotisk opførsel.
En kode er asymptotisk optimal, hvis forholdet mellem dens længde og det teoretiske minimum går mod 1, når tallene vokser. Omega opfylder dette: length(n)/log₂(n) → 1 når n → ∞.
Selv om Omega er teoretisk overlegent, er det mere komplekst at implementere og dekode. For praktiske datasæt med begrænsede heltal er enklere koder som Exp-Golomb eller Rice ofte mere hensigtsmæssige. Omega er især nyttig i teoretisk analyse og scenarier med ubegrænsede heltal.