> elias | gamma | universal <
// Elias Gamma – código universal para inteiros positivos sem parâmetros
Código universal
Funciona para qualquer inteiro positivo sem parâmetros adicionais.
Sem prefixo
Nenhum código é prefixo de outro, garantindo decodificação única.
Assintoticamente ótimo
Aproxima-se da compressão ideal para certas distribuições.
>> informações técnicas
Como funciona o Elias Gamma:
Elias Gamma codifica um inteiro positivo n da seguinte forma: 1) Calcula N = ⌊log₂(n)⌋, 2) Escreve N zeros como código unário, 3) Acrescenta a representação binária de n (com N+1 bits). O resultado é um código de comprimento (2N+1) bits.
Exemplos de codificação:
n=1: log₂(1)=0 Código: 1 (sem zeros + "1") n=2: log₂(2)=1 Código: 010 (um zero + "10") n=5: log₂(5)=2 Código: 00101 (dois zeros + "101") n=10: log₂(10)=3 Código: 0001010 (três zeros + "1010") Fórmula do comprimento: 2⌊log₂(n)⌋ + 1
Por que usar Elias Gamma:
- >Não exige parâmetros
- >Implementação simples
- >Bom para inteiros pequenos
- >Esquema de codificação universal
- >Importante na teoria da informação e da compressão
>> perguntas frequentes
O que é a codificação Elias Gamma?
Elias Gamma é um código universal para inteiros positivos desenvolvido por Peter Elias. Cada inteiro é codificado usando o tamanho em bits na forma unária, seguido pela própria representação binária. É chamado de "universal" porque funciona sem conhecer a distribuição dos dados.
Quando Elias Gamma é eficiente?
Elias Gamma é mais eficiente para inteiros que seguem uma distribuição do tipo lei de potência (P(n) ∝ n^-2). Ele usa aproximadamente 2log₂(n)+1 bits, sendo bom para valores pequenos, mas menos eficiente para valores grandes.
Gamma vs Delta vs Omega?
Elias Gamma usa 2log₂(n)+1 bits. Delta melhora para log₂(n)+2log₂(log₂(n)+1)+1 bits, e Omega oferece compressão ainda melhor para números muito grandes. Gamma é o mais simples, Delta é melhor para valores médios e Omega para n grandes.
Onde os códigos Elias são usados?
Os códigos Elias são usados em teoria da informação, pesquisa em compressão de dados e alguns algoritmos de compressão especializados. São importantes teoricamente como códigos universais, mas na prática são menos comuns do que Huffman ou codificação aritmética.