// Elias Omega – codice asintoticamente ottimale per interi arbitrariamente grandi
Si avvicina al minimo teorico per numeri molto grandi.
Codifica le lunghezze in modo ricorsivo ed elegante.
Funziona per qualunque intero positivo senza parametri aggiuntivi.
Elias Omega codifica in modo ricorsivo la lunghezza di un numero fino a raggiungere 1. A partire da n si codifica log₂(n), poi log₂(log₂(n)) e così via finché si arriva a 1. Il codice è formato da questi valori in ordine inverso e termina con 0. Si ottengono così log(n) + log(log(n)) + log(log(log(n))) + ... bit.
n=16: 16 → binario: 10000 (lunghezza 5) 5 → binario: 101 (lunghezza 3) 3 → binario: 11 (lunghezza 2) 2 → binario: 10 (lunghezza 2) 1 → stop Costruire il codice all’indietro: Inizia da 0 (terminatore) Preponi 10 (codifica 2) Preponi 11 (codifica 3) Preponi 101 (codifica 5) Preponi 10000 (codifica 16) Risultato: 10 11 101 10000 0 Confronto di efficienza: n=100: Gamma=13, Delta=12, Omega=10 bit n=1000: Gamma=19, Delta=16, Omega=14 bit
Elias Omega è il codice più avanzato della famiglia di Elias. Utilizza una codifica ricorsiva delle lunghezze per ottenere l’ottimalità asintotica. Codifica la lunghezza della rappresentazione, poi la lunghezza di quella lunghezza e così via fino a 1, risultando molto efficiente per interi molto grandi.
Per numeri piccoli (< 10) Gamma è spesso la scelta migliore. Per numeri medi (10–1000) Delta migliora Gamma. Per numeri grandi (> 1000) Omega diventa sempre più vantaggioso. Omega usa iterazioni log*(n) e raggiunge un comportamento ottimale al limite.
Un codice è asintoticamente ottimale se il rapporto tra la sua lunghezza e il minimo teorico tende a 1 quando i numeri crescono. Per Omega vale: length(n)/log₂(n) → 1 per n → ∞.
Nonostante la superiorità teorica, Omega è più complesso da implementare e da decodificare. Per dati reali con interi limitati, codici più semplici come Exp-Golomb o Rice sono spesso preferibili. Omega è particolarmente utile nell’analisi teorica e in scenari con interi non limitati.