> codificação aritmética | bits fracionários | ótima <
// Codificação aritmética - codificação com bits fracionários próxima ao limite de entropia
Quase ideal
Aproxima-se do limite teórico de entropia para uma compactação eficiente.
Bits fracionários
Codifica símbolos usando bits fracionários baseados em sua probabilidade.
Streaming
Pode codificar e decodificar dados de forma incremental conforme eles chegam.
>> informações técnicas
Como funciona a codificação aritmética:
A codificação aritmética representa toda a mensagem como um único número no intervalo [0,1). Cada símbolo estreita esse intervalo com base em sua probabilidade. O intervalo final é codificado como uma fração binária, alcançando uma compactação muito próxima do limite de entropia.
Processo de codificação:
Texto: "AAB" Probabilidades: A=0.67, B=0.33 1. Início: [0, 1) 2. 'A': [0, 0.67) 3. 'A': [0, 0.45) 4. 'B': [0.30, 0.45) Saída: qualquer número em [0.30, 0.45) Binário: 0.010011...
Por que usar codificação aritmética:
- >Melhores taxas de compactação
- >Aproxima-se do limite de entropia
- >Funciona com qualquer distribuição de probabilidade
- >Usada em JPEG2000 e H.264
- >Patentes expiradas (2024)
>> perguntas frequentes
O que é codificação aritmética?
A codificação aritmética é uma forma de codificação entrópica que converte uma sequência de símbolos em um único número fracionário. Diferente da codificação de Huffman, que usa bits inteiros, a codificação aritmética pode usar bits fracionários por símbolo.
Por que ela é melhor que Huffman?
A codificação aritmética pode alcançar uma compactação arbitrariamente próxima do limite de entropia, enquanto Huffman fica limitada a bits inteiros por símbolo. Para distribuições de probabilidade muito enviesadas, a codificação aritmética pode ser significativamente melhor.
O que é o parâmetro de precisão?
A precisão controla o número de bits usados nos cálculos internos. Maior precisão permite codificar mensagens mais longas, mas exige mais memória. Para textos curtos, 16 bits geralmente são suficientes.
Onde a codificação aritmética é usada?
A codificação aritmética é usada em padrões modernos de compactação, como vídeo H.264/H.265, imagens JPEG2000 e o modo DEFLATE64 do ZIP. Antes ela era protegida por patentes, mas as principais expiraram.
// Exemplo resolvido
| Step | Symbol | low | high |
|---|---|---|---|
| 0 | — | 0 | 1 |
| 1 | A | 0 | 0.5 |
| 2 | B | 0.25 | 0.375 |
| 3 | C | 0.34375 | 0.375 |
// Exemplos de código
Model P(A)=0.5 P(B)=0.25 P(C)=0.25 -> A:[0,0.5) B:[0.5,0.75) C:[0.75,1)
Update width = high - low
high = low + width * cum_high(symbol)
low = low + width * cum_low(symbol)
Output any value in [0.34375, 0.375) e.g. 0.34375 = 0.01011b (5 bits = 1 + 2 + 2)
Entropy -log2 P(A) - log2 P(B) - log2 P(C) = 1 + 2 + 2 = 5 bits
>> Mais perguntas
P: Por que a codificação aritmética costuma ser melhor que Huffman?
R: O Huffman atribui a cada símbolo um número inteiro de bits (no mínimo 1). A codificação aritmética codifica a mensagem inteira como uma única fração em [0, 1) e se aproxima da entropia, mesmo com símbolos de probabilidade acima de 50 % que no Huffman custam 1 bit.
P: Como funciona o exemplo de intervalos ABC?
R: Com A=0,5, B=0,25, C=0,25 o intervalo se estreita a cada símbolo: [0,1) → [0,0,5) → [0,25, 0,375) → [0,34375, 0,375). Qualquer número dentro, como 0,34375 = 0,01011 em binário, codifica «ABC» com 5 bits, exatamente a entropia.
P: Onde a codificação aritmética é usada?
R: No CABAC do H.264/HEVC, no codificador MQ do JPEG 2000 e JBIG2, e em variantes como range coding (AV1) e ANS (zstd, JPEG XL). Patentes antigas frearam a adoção; hoje a maioria expirou.