Este artigo pode ser de interesse para quem está envolvido em compactação de dados ou deseja gravar seu próprio arquivador.
O artigo está escrito principalmente nos materiais do
blog , mantidos por Fabian Giesen.
1. Introdução
O método de codificação de entropia rANS (
r ange + ANS) é o irmão do algoritmo FSE, sobre o qual
escrevi anteriormente . A abreviatura ANS significa
Sistemas Numéricos Assimétricos , e o intervalo de palavras no nome sugere a semelhança desse método com a
codificação por intervalo . O autor de rANS é
Yarek Duda .
O método rANS permite alcançar uma compressão quase ideal a uma velocidade muito alta. Neste rANS não é pior que o FSE, o que não é surpreendente: ambos os algoritmos são baseados em uma base teórica comum. No entanto, o algoritmo rANS é muito mais simples de implementar que o FSE.
Primeiro, haverá uma longa parte "teórica", e depois tentaremos escrever um arquivador simples.
Descrição do método
A operação do algoritmo é determinada pelas seguintes fórmulas simples:
Codificação: C(s,x): x := (x / Fs) * M + Bs + (x % Fs)Decodificação: D(x): s = sym[x % M], x := Fs * (x / M) + (x % M) - BsVamos analisá-los em detalhes.
A função de codificação
C (s, x) recebe o caractere
s a ser codificado (seja um número inteiro) e o estado atual do codificador
x (também um número inteiro).
F s - frequência do símbolo
s . A divisão por Fs acima é um número inteiro.
M é a soma das frequências de todos os símbolos do alfabeto (
M = Σ
F s ).
Em s , o início do intervalo correspondente ao caractere codificado (na figura abaixo).
x %
Fs é o restante da divisão de
x por
F s .
O princípio de operação é o mesmo da
codificação aritmética : pegamos o segmento
[ 0,
M) e o dividimos em partes para que cada caractere
s corresponda a um intervalo de tamanho igual à frequência do caractere
Fs . A ocorrência do valor
x% M em qualquer intervalo indica a codificação do símbolo correspondente.
No início da codificação, inicialize
x com um valor adequado arbitrário e calcule a função
C (s, x) para todos os caracteres codificados em sequência.
Cada cálculo da função
C (s, x) aumenta o valor de
x . Quando ficar muito grande, você deve despejar os dados na saída:
while (x >= x_max) { writeToStream(x % b);
Esta etapa é chamada
renormalização . Depois disso, você pode continuar a codificação.
Acima no código, novas constantes apareceram:
x_max e
b . Em teoria, os números
M ,
be x_max são relacionados por algumas relações, mas na prática é mais eficaz usar os seguintes valores se o estado uint32 for usado para o estado
x :
M = 2 ^
k , onde
k <= 16
b = 2 ^ 16 (metade do tamanho de uint32)
A escolha de
M = 2 ^
k se deve ao fato de haver divisão por
M na função de decodificação, portanto, a divisão com o restante pode ser substituída por operações bit a bit.
O valor de
k é selecionado dentre as seguintes considerações: quanto maior, maior a precisão de
Fs e mais eficiente a compressão. Nesse caso, algumas despesas gerais para armazenar a tabela de frequências devem ser levadas em consideração, portanto nem sempre vale a pena usar os valores máximos de
k .
O valor de
x_max deve ser tal que nenhum estouro ocorra. Com base na função de codificação, obtemos
x <
uint32_max *
Fs /
M ou uma maneira ligeiramente diferente:
x_max <= (
b *
L ) *
Fs /
M , em que
L <=
uint32_max /
b . No código real, a condição assume a forma x / b> = L / M * Fs para evitar excesso nos cálculos.
O valor
b = 2 ^ 16 (metade do tamanho de uint32) é escolhido de tal maneira que se
x excede
x_max , uma divisão por
b é suficiente para continuar trabalhando. Como resultado, o
while terminará após a primeira iteração, o que significa que pode ser substituído por um simples
if .
Como resultado, a função de codificação assume o seguinte formato:
typedef uint32_t RansState; constexpr uint32_t RANS_L = 1u << 16; constexpr uint32_t k = 10;
No final da codificação, você deve salvar o valor de
x , pois a decodificação será iniciada a partir dela. E sim, decodificaremos do fim ao começo, ou seja, do último caractere codificado ao primeiro. (Em um artigo sobre o
FSE, este ponto é explicado em detalhes suficientes.)
Quero me aprofundar um pouco mais em como a fórmula de codificação funciona.
x := (x / Fs) * M + Bs + (x % Fs)
Após calcular (
x / Fs) * M , a variável
x contém os
k bits menos significativos (lembre-se de que
M = 2 ^
k ). A adição de
+ Bs + (x % Fs) grava essencialmente nesses bits um determinado valor no
intervalo do caractere
s , porque
Bs é o início do intervalo e (x% Fs) é o número nesse intervalo (o tamanho do intervalo é Fs). Assim, ao decodificar, podemos determinar o caractere codificado pelo intervalo em que ele cai (x% M).
DecodificaçãoVamos para a função de decodificação.
D(x): s = sym[x % M], x := Fs * (x / M) + (x % M) - Bs
Como já entendemos acima, o caractere desejado
s é determinado pelo restante da divisão
x %
M. Em que intervalo o valor (x% M) caiu, esse caractere foi codificado.
Anteriormente, definimos especificamente M = 2 ^ k para simplificar a função de decodificação. Acabou assim:
uint32_t RansDecode(RansState& x, RansInBuf& in) { assert(x >= RANS_L);
A decodificação começa com o mesmo
x que foi obtido no final da codificação. Para fazer isso, ele deve ser salvo junto com os dados codificados.
No final da decodificação, o estado do decodificador
x deve ser exatamente o mesmo que a codificação. Em geral, em cada etapa
x deve ser exatamente o mesmo que na etapa de codificação correspondente. Esse fato ajuda muito na depuração.
Como você pode ver, a decodificação funciona mais rápido que a codificação, pois não há operações de divisão.
O momento mais difícil na função de decodificação é o método para determinar em qual intervalo o valor caiu (x% M).
O método mais fácil e rápido é usar a tabela
sym [] , tamanho
M. Nesse caso, obtemos uma tabela do mesmo tamanho que no algoritmo FSE, com a diferença de que, em rANS, a tabela não está “misturada”, os caracteres estão em ordem e essa tabela é muito mais fácil de construir.
A principal desvantagem dessa abordagem é o tamanho da tabela
sym , que cresce exponencialmente com o aumento de
k .
Método de alias
Um
método alternativo foi inventado para determinar com mais eficiência o acerto em um intervalo. Este método permite determinar rapidamente o intervalo desejado usando pequenas tabelas - pelo número de caracteres no alfabeto.
Uma explicação longa e longa pode ser encontrada aqui:
Dardos, Dados e Moedas . Descreverei a essência do método resumidamente: pegamos um pedaço do intervalo mais longo e o anexamos ao intervalo mais curto para que o tamanho total seja exatamente
M /
N (onde
N é o número de caracteres no alfabeto). Acontece que, se você fizer isso sequencialmente, sempre terminará com
N pares de tamanho
M /
N.Naturalmente,
M deve ser divisível por
N. E se lembrarmos que temos
M = 2 ^
k , então o tamanho do alfabeto também será uma potência de dois. Isso não é um problema, pois você sempre pode suplementar o alfabeto ao tamanho desejado com caracteres não utilizados com uma frequência zero.
O fato de o intervalo de caracteres ser dividido em várias partes complica um pouco o procedimento de codificação, mas não muito. Se você se lembra do FSE, então os intervalos eram geralmente espalhados por todo o intervalo, como se um mixer louco tivesse trabalhado neles e nada funcionasse =)
Determinar o intervalo desejado não é difícil: divida
x por
N e caia em um dos pares. Em seguida, comparamos o restante da divisão de
x% N com o limite entre os segmentos em um par e caímos em um intervalo ou em outro.
Tentamos na prática
Usaremos o código do
exemplo finalizado .
Tomamos os dados para compactação do arquivo:
size_t in_size; uint8_t* in_bytes = read_file("book1", &in_size);
1. Primeiro, você precisa decidir sobre
a estrutura de dados .
Usamos a opção mais simples: codificaremos um byte usando o alfabeto [0 ... 255].
2. O próximo passo é determinar a
frequência dos caracteres do alfabeto:
(função
stats.count_freqs )
for (size_t i = 0; i < in_size; i++) { freqs[in_bytes[i]]++; }
3. Portanto, temos frequências de símbolos, mas agora precisamos
normalizá-las , isto é, reduzir (ou aumentar) proporcionalmente para que, no total, obtenha M = 2 ^ k. Esta não é uma tarefa tão simples como pode parecer, por isso usamos uma função pronta:
stats.normalize_freqs(...);
A propósito, você precisa determinar o valor de
k . Como nosso alfabeto consiste em 256 caracteres,
k menor que 8 não deve ser utilizado. Primeiro, use o máximo - 16 e depois tente outros valores.
4. Crie uma
tabela de alias :
stats.make_alias_table();
5. Codificamos a
partir do final e decodificamos na ordem normal.
RansState rans;
Além disso, o exemplo por referência decodifica dados compactados usando estatísticas prontas. Na vida real, para decodificação, você precisa salvar uma tabela de frequências (estatísticas) junto com os dados compactados. No caso mais simples, você terá que gastar N * k bits nele.
Como prometido acima, vejamos os resultados da compactação para vários valores de k (no código é
prob_bits ), levando em consideração o aumento de tamanho devido ao registro da tabela de frequências:
(
Tamanho original do arquivo book1: 768771)
k = 16: 435059 + 512 = 435571 bytes
k =
15 : 435078 + 480 =
435558 bytes
k = 14: 435113 + 448 = 435561 bytes
k = 13: 435239 + 416 = 435655 bytes
k = 12: 435603 + 384 = 435987 bytes
k = 11: 436530 + 352 = 436882 bytes
k = 10: 440895 + 320 = 441215 bytes
k = 9: 453418 + 288 = 453706 bytes
k = 8: 473126 + 256 = 473382 bytes
Você pode ver que quanto maior k, melhor a compactação. Mas em um certo ponto (em k = 16), a sobrecarga da tabela de frequências começa a superar os benefícios de aumentar a precisão. Se você compactar um arquivo menor, esse efeito aparecerá em k menor.
Você também precisa dizer algumas palavras sobre o truque chamado "rANS intercalados", que também é implementado
neste exemplo . A idéia é que, alternadamente, o uso de duas variáveis de estado independentes faça melhor uso do paralelismo do processador. Como resultado, a decodificação é ainda mais rápida.
Concluindo, quero observar que o método de compactação de arquivos selecionado é muito simples. Ele não leva em consideração os recursos dos dados, e é por isso que a compactação está longe de ser ótima. Se você observar atentamente a entrada, poderá descobrir que algumas
combinações de letras são mais comuns que outras, e outras nem sequer ocorrem. Usando esse fato, a compactação pode ser significativamente aprimorada. Mas este é um tópico para um artigo separado.
Posfácio
Por que escrever seu próprio arquivador quando existem muitos utilitários testados pelo tempo? A resposta é bem simples: arquivadores adaptados a um formato específico são muito melhores.
Ao desenvolver jogos na
Playrix , geralmente confiamos na necessidade de reduzir o tamanho da compilação. Os jogos estão em constante evolução, a quantidade de conteúdo está aumentando e o espaço é limitado.
Mais uma vez
, olhando
ansiosamente para os recursos, percebemos que alguns arquivos podem ser compactados muito melhor do que o zip, devido à sua estrutura. Durante os experimentos, conseguimos reduzir significativamente o tamanho do nosso próprio formato de animação; também existem algumas mudanças na compactação de arquivos gráficos.
Ao desenvolver algoritmos de compressão, um codificador de entropia universal, como rANS ou FSE, é uma ferramenta indispensável. Ele assume completamente a tarefa de escrever caracteres com o menor número de bits, permitindo que o desenvolvedor se concentre nos principais detalhes do algoritmo. E também funciona muito rápido, tanto na codificação quanto na decodificação.
Espero que este artigo ajude você a conhecer o rANS e começar a usá-lo em seus projetos.
Referências
Aqui você pode ver exemplos de implementação de rANS (com diferentes opções de otimização):
Fabian Giesen:
github.com/rygorous/ryg_ransVocê pode ler detalhes e detalhes interessantes no blog de Fabian (em inglês):
→
notas rANS→
rANS com distribuições de probabilidade estática→
rANS na prática