> golomb | compressão | ótima <
// Codificação Golomb - Compressão ótima de inteiros com divisor flexível
>> recursos
Divisor flexível
Escolha qualquer valor M para máxima eficiência de compressão.
Binário truncado
Usa o mínimo de bits para codificar o resto.
Uso geral
Funciona com qualquer distribuição de inteiros não negativos.
>> informações técnicas
Como funciona a codificação Golomb
A codificação Golomb divide cada inteiro n por um divisor M para obter quociente q e resto r. O quociente é codificado em unário e o resto em binário truncado, usando o número mínimo de bits necessário para representar os valores de M. Isso cria um código ótimo para distribuições geométricas com parâmetro p = 1/M.
Exemplo de codificação Golomb (M=5)
M=5, b=⌈log₂(5)⌉=3, c=2³-5=3 0 → q=0, r=0 → 0|00 → 000 (2 bits para r<3) 1 → q=0, r=1 → 0|01 → 001 (2 bits para r<3) 2 → q=0, r=2 → 0|10 → 010 (2 bits para r<3) 3 → q=0, r=3 → 0|110 → 0110 (3 bits para r≥3) 4 → q=0, r=4 → 0|111 → 0111 (3 bits para r≥3) 5 → q=1, r=0 → 10|00 → 1000 6 → q=1, r=1 → 10|01 → 1001 7 → q=1, r=2 → 10|10 → 1010 Binário truncado: r<3 usa 2 bits, r≥3 usa 3 bits
Por que usar a codificação Golomb
- Ótimo para distribuições geométricas
- Parâmetro M flexível
- Uso mínimo de bits
- Implementação simples
- Optimalidade comprovada
>> perguntas frequentes
O que é a codificação Golomb?
A codificação Golomb é um código ótimo, livre de prefixo e de comprimento variável para distribuições geométricas. Ela divide os inteiros com um parâmetro ajustável M, codificando o quociente em unário e o resto em binário truncado, obtendo uma compressão ótima para dados que seguem P(n) = (1-p)^n × p.
Como escolher o parâmetro M?
O M ótimo depende do parâmetro geométrico p dos seus dados. Para dados com média μ, M ótimo ≈ μ + 1. Para probabilidades que decaem exponencialmente com parâmetro p, o M ótimo é M = ⌈-1/log₂(1-p)⌉. Use a função de análise para encontrar o melhor M para os seus dados.
O que é binário truncado?
O binário truncado minimiza a quantidade de bits ao codificar um dos M valores possíveis. Se M é uma potência de 2, usa-se binário padrão. Caso contrário, alguns valores usam ⌊log₂M⌋ bits e outros usam ⌈log₂M⌉ bits, garantindo decodificação única com comprimento médio mínimo.
Onde a codificação Golomb é usada?
A codificação Golomb é usada na compressão de imagens JPEG-LS, na codificação de vídeo H.264 (como Exp-Golomb) e em formatos de áudio sem perdas. É ideal para codificação de comprimentos de sequências, resíduos após predição e quaisquer dados com distribuições geométricas ou exponenciais.