// Elias Omega – código assintoticamente ótimo para inteiros arbitrariamente grandes
Aproxima‑se do mínimo teórico para números grandes.
Codifica comprimentos de forma recursiva e elegante.
Funciona para qualquer inteiro positivo sem parâmetros extras.
Elias Omega codifica recursivamente o comprimento de um número até atingir 1. Começamos com n, codificamos log₂(n), depois log₂(log₂(n)) e assim por diante até 1. O código é composto por esses valores em ordem inversa e termina com 0. Isso resulta em log(n) + log(log(n)) + log(log(log(n))) + ... bits.
n=16: 16 → binário: 10000 (comprimento 5) 5 → binário: 101 (comprimento 3) 3 → binário: 11 (comprimento 2) 2 → binário: 10 (comprimento 2) 1 → parar Construir o código de trás para frente: Comece com 0 (terminador) Prependa 10 (codifica 2) Prependa 11 (codifica 3) Prependa 101 (codifica 5) Prependa 10000 (codifica 16) Resultado: 10 11 101 10000 0 Comparar eficiência: n=100: Gamma=13, Delta=12, Omega=10 bits n=1000: Gamma=19, Delta=16, Omega=14 bits
Elias Omega é o código mais sofisticado da família Elias. Ele usa codificação recursiva de comprimentos para obter optimalidade assintótica. Codifica o comprimento da representação, depois o comprimento desse comprimento e assim por diante até chegar a 1, sendo muito eficiente para inteiros muito grandes.
Para números pequenos (< 10), Gamma costuma ser o melhor. Para números médios (10–1000), Delta melhora os resultados. Para números grandes (> 1000), Omega torna‑se cada vez mais vantajoso. Omega usa iterações log*(n) e alcança um comportamento ótimo no limite.
Um código é assintoticamente ótimo quando a razão entre o seu comprimento e o mínimo teórico tende a 1 à medida que n cresce. Para Omega vale: length(n)/log₂(n) → 1 quando n → ∞.
Apesar da superioridade teórica, Omega é mais complexo de implementar e decodificar. Para dados reais com inteiros limitados, códigos mais simples, como Exp-Golomb ou Rice, costumam ser mais práticos. Omega brilha em análises teóricas e em cenários com inteiros sem limite superior.