> elias | omega | asintotico <
// Elias Omega – codice asintoticamente ottimale per interi arbitrariamente grandi
Asintoticamente ottimale
Si avvicina al minimo teorico per numeri molto grandi.
Struttura ricorsiva
Codifica le lunghezze in modo ricorsivo ed elegante.
Codice universale
Funziona per qualunque intero positivo senza parametri aggiuntivi.
>> informazioni tecniche
Come funziona Elias Omega:
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.
Procedura di codifica Omega:
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
Perché usare Elias Omega:
- ▸Ideale per numeri molto grandi
- ▸Comportamento asintoticamente ottimale
- ▸Importante nella teoria della codifica degli interi
- ▸Nessun bit sprecato nel limite
- ▸Struttura ricorsiva elegante
>> domande frequenti
Che cos’è la codifica Elias Omega?
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.
Come si confronta Omega con Gamma e Delta?
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.
Che cosa significa ottimalità asintotica?
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 → ∞.
Perché Omega non è usato ovunque?
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.