Codificação Aritmética e a Identidade Entre Prever e Comprimir

Item da lista de Ilya: nenhum, diretamente. Este artigo constrói a equivalência entre modelo e compressor sobre a qual toda a Parte I se apoia, e que Rissanen — tratado em IL04 e IL05 — usa sem demonstrar.

Índice da Série: A Lista de Ilya

• 1. A Lista, a Tese e Por Que Ela Começa em Compressão
• 2. Códigos, a Desigualdade de Kraft e o Limite de Shannon
• 3. Codificação Aritmética e a Identidade Entre Prever e Comprimir (Você está aqui)

O artigo anterior terminou com uma derrota disfarçada de teorema. Provamos que o código de Huffman é ótimo entre todos os que atribuem uma palavra inteira a cada símbolo, e que seu comprimento médio satisfaz

O limite superior é o problema. Um bit de folga por símbolo é aceitável quando os símbolos carregam muita informação, e ruinoso quando carregam pouca. Um modelo de linguagem que atinge um bit por token teria o arquivo dobrado de tamanho por um codificador que desperdiça um bit por token. A fonte não diádica de IL02 desperdiçava $0{,}078072$ bit por símbolo, o que é modesto e ainda assim é $3{,}7\%$.

O diagnóstico é preciso e vale repetir: a folga existe porque $\ell_i$ é inteiro e $-\log_2 p_i$ não é. Não é defeito do Huffman. É defeito do formato da resposta. Enquanto insistirmos que cada símbolo receba um número inteiro de bits, sobra resto.

Este artigo abandona a insistência. Em vez de perguntar qual a melhor palavra-código para cada símbolo, pergunta qual o melhor número real para a mensagem inteira. A resposta elimina a folga por símbolo, separa o modelo do codificador, e — o que importa mais — transforma a fórmula que a série vem usando desde o primeiro artigo em uma identidade exata.

1. A folga que sobrou

Recuperemos os números de IL02, porque o artigo inteiro é uma conversa com eles.

A fonte não diádica $p = (2/5, 1/5, 1/5, 1/10, 1/10)$ tem $H(p) = 2{,}121928$ bits e comprimento médio de Huffman $\bar{L} = 2{,}200000$. A mensagem ABRACADABRA, com contagens $(5,2,1,1,2)$ para $(A,B,C,D,R)$, custa 23 bits sob Huffman contra um piso de entropia de $22{,}4441$.

Meio bit jogado fora em onze símbolos. E a razão para não conseguirmos recuperá-lo é geométrica: o símbolo $A$, com probabilidade $5/11$, merece $1{,}1375$ bit, e o Huffman só sabe dar 1 ou 2.

A saída começa por uma pergunta ingênua. Se o problema é que $1{,}1375$ não é inteiro, por que não emitimos $1{,}1375$ bit?

Emitir fração de bit não faz sentido isoladamente — um bit é a menor unidade que um canal transporta. Mas faz sentido em média, e faz sentido se o que emitimos não for uma palavra por símbolo, e sim uma quantidade total para a mensagem toda. É a diferença entre pagar cada café com moeda inteira e fechar a conta no fim do mês.

2. Um número real para a mensagem inteira

Considere o intervalo $[0, 1)$ e um modelo $Q$ sobre o alfabeto. Vamos particionar o intervalo em pedaços, um por símbolo, com comprimentos iguais às probabilidades.

Com o modelo de ordem zero de ABRACADABRA — $Q(A) = 5/11$, $Q(B) = Q(R) = 2/11$, $Q(C) = Q(D) = 1/11$, na ordem alfabética $A, B, C, D, R$ — a partição é

As larguras somam 1 exatamente, como devem.

Agora a ideia. Para codificar uma mensagem, escolhemos o pedaço do primeiro símbolo, ampliamos esse pedaço para ocupar toda a largura, e repetimos com o segundo símbolo. A cada passo o intervalo corrente encolhe, e mensagens diferentes acabam em intervalos disjuntos. Codificar é nomear o intervalo final; nomear é dar bits suficientes de qualquer número que caia dentro dele.

A figura codifica ABRA. Repare no que acontece com a coluna de larguras: $1$, depois $4{,}5455 \times 10^{-1}$, depois $8{,}2645 \times 10^{-2}$, depois $1{,}5026 \times 10^{-2}$, e por fim $6{,}8301 \times 10^{-3}$. Cada passo multiplicou a largura pela probabilidade do símbolo escolhido.

Guarde essa observação. Ela é o artigo inteiro.

3. O estreitamento, símbolo a símbolo

Formalizemos. Seja $[\mathrm{lo}, \mathrm{hi})$ o intervalo corrente, de largura $w = \mathrm{hi} - \mathrm{lo}$, e seja

a probabilidade acumulada dos símbolos que precedem $a$ na ordem canônica do alfabeto — a função de distribuição acumulada, avaliada logo antes de $a$. Ao codificar o símbolo $x_t$, o intervalo passa a ser

Essa é a única fórmula de que o artigo precisa. Ela diz: pegue a posição relativa do pedaço de $x_t$ dentro de $[0,1)$ e transfira-a, em escala, para dentro do intervalo corrente.

Façamos AB à mão, em frações exatas, para que a leitora possa conferir cada dígito.

Começamos com $\mathrm{lo} = 0$, $\mathrm{hi} = 1$, $w = 1$.

Símbolo $A$. Não há símbolos antes de $A$, logo $F(A) = 0$. Então

e a nova largura é $w’ = 5/11$.

Símbolo $B$. Agora $F(B) = Q(A) = 5/11$, e $Q(B) = 2/11$. Então

com largura $w’’ = 10/121$.

E $-\log_2(10/121) = 3{,}596935$ bits. Guarde também esse número; ele vai reaparecer em um lugar improvável.

4. A identidade

Olhe para a sequência de larguras da seção anterior: $1$, depois $5/11$, depois $10/121$. Cada uma é a anterior multiplicada pela probabilidade do símbolo. Isso não é acidente do exemplo — é o que a fórmula de atualização faz, e a prova é uma linha de indução.

Proposição. Após codificar $x = x_0 x_1 \ldots x_{n-1}$, a largura do intervalo corrente vale

Prova. Para $n = 0$, o intervalo é $[0,1)$ e $w_0 = 1$, que é o produto vazio. Suponha $w_t = \prod_{s<t} Q(x_s \mid x_{<s})$. Pela fórmula de atualização,

porque os dois termos em $F(x_t)$ se cancelam. O passo indutivo fecha, e o produto telescópico é exatamente a regra da cadeia. $\blacksquare$

Tomando logaritmo:

O lado direito é a fórmula que o primeiro artigo desta série apresentou como definição de trabalho, pedindo licença. O lado esquerdo é uma propriedade geométrica de um intervalo que a leitora pode desenhar numa folha. São o mesmo número.

Vejamos em ABRACADABRA, com aritmética exata de frações:

Não é aproximação, não é limite assintótico, não vale “para $n$ grande”. É identidade, e ela vale para toda mensagem e todo modelo.

O programa da Seção 7 imprime essa tabela; o laboratório da Seção 6 recalcula a diferença para qualquer mensagem que a leitora digitar, e ela fica na ordem de $10^{-15}$ — que é o erro de arredondamento do double, não do argumento.

5. Quantos bits para nomear um intervalo

Falta converter o intervalo em bits de verdade.

Um intervalo de largura $w$ contém pelo menos uma fração diádica de denominador $2^{\lceil -\log_2 w \rceil + 1}$ — isto é, existe um número da forma $m/2^k$ dentro dele com $k = \lceil -\log_2 w \rceil + 1$. Emitindo os $k$ primeiros bits da expansão binária desse número, o receptor identifica o intervalo sem ambiguidade. Logo

A folga total é menor que dois bits na mensagem inteira. Não por símbolo. É a diferença estrutural em relação ao Huffman, e a razão de o aritmético ter vencido a história.

Uma advertência sobre o que essa cota é. Ela é uma garantia superior, não uma previsão — a mesma distinção que IL02 encontrou ao examinar a cota $1/n$ da blocagem, e que se repete aqui de forma quase idêntica. Para ABRACADABRA sob ordem zero, a cota promete no máximo $\lceil 22{,}444107 \rceil + 1 = 24$ bits. O codificador implementado emite 23, porque o intervalo final já continha uma fração diádica de 23 bits e o bit de terminação não foi necessário.

Vinte e três é também o custo do Huffman em IL02. Empate.

O empate é instrutivo e eu não vou disfarçá-lo com adjetivos. Em uma mensagem de onze símbolos, o codificador aritmético não ganha nada. Se o argumento a favor dele fosse “comprime melhor”, o argumento morreria aqui.

Não é esse o argumento. Vejamos qual é.

6. Trocar de modelo é o que vale

Mantenha o codificador. Troque o modelo.

Um modelo de ordem um condiciona cada símbolo ao anterior. As transições de ABRACADABRA, com contagens:

Cinco das dez transições são determinísticas e custam zero. O custo ideal cai de $22{,}444107$ para $7{,}137504$ bits.

Com ordem dois, cai para $3{,}596935$ — e este é o número que pedi para a leitora guardar na Seção 3. Não é coincidência: sob ordem dois, todo contexto de dois símbolos em ABRACADABRA determina o seguinte, então só os dois primeiros símbolos custam alguma coisa, e eles custam exatamente $-\log_2(5/11) - \log_2(2/11) = -\log_2(10/121)$, que é a largura do intervalo de AB calculada à mão. A conta manual de duas linhas previu o custo de ordem dois da mensagem inteira.

A tabela completa, com o que o codificador de referência realmente emite:

De 23 para 8 bits. E o codificador não mudou uma linha.

Aqui está a assimetria que decide a questão. Trocar de modelo, no aritmético, custa nada: as probabilidades condicionais entram na fórmula de atualização a cada símbolo, e podem ser diferentes a cada símbolo. Trocar de modelo, no Huffman, exige reconstruir a árvore — a cada símbolo, se o modelo for condicional. O aritmético separa modelo de codificador; o Huffman os funde.

E como o ganho de trocar o modelo (fator de quase três, aqui) é muito maior que qualquer ganho de codificação (meio bit em onze símbolos), um codificador que dificulte a troca de modelo está otimizando a coisa errada.

6.1 O excesso é por mensagem, não por símbolo

Vale medir a afirmação em duas escalas. O programa comprime a mesma mensagem repetida duzentas vezes, dando 2 200 símbolos:

Multiplicamos o comprimento por 200 e o excesso continuou abaixo de dois bits. Em onze símbolos ele representa $2{,}5\%$ do total; em 2 200, representa $0{,}03\%$. A folga do Huffman, sendo por símbolo, permaneceria em $3{,}7\%$ nos dois casos.

6.2 O laboratório

O painel de cima refaz a figura da Seção 2 ao vivo. Digite uma mensagem sobre A B C D R, troque a ordem do modelo, e observe duas coisas: a largura final despencando quando o modelo melhora, e a diferença entre $-\log_2 w$ e a soma de $-\log_2 p$ ficando na ordem de $10^{-15}$, que é o double reclamando, não a matemática.

Vale tentar deliberadamente uma sequência que o modelo julgue impossível — digite DD, por exemplo, sob ordem um. O intervalo colapsa para largura nula, e o laboratório explica por que um modelo que atribui probabilidade zero a um evento observado não é um compressor.

7. O programa

O codificador publicado usa inteiros de 64 bits, com um intervalo de 32 bits efetivos, renormalização e tratamento de underflow. Compilação de referência:

g++ -std=c++23 -O3 -march=native -Wall -Wextra IL03_arithmetic_coder.cpp -o IL03

A derivação deste artigo usou frações exatas, porque a leitora precisa refazer as contas. Um codificador de verdade não pode: frações exatas crescem sem limite, e ponto flutuante não é reprodutível entre máquinas. A solução clássica, de Witten, Neal e Cleary, mantém o intervalo em inteiros e o renormaliza sempre que possível.

A renormalização tem três casos, e o terceiro é o que separa uma implementação correta de uma quase correta.

Se o intervalo inteiro cai na metade inferior, o primeiro bit já está decidido: é zero. Emite-se, e o intervalo é dobrado. Se cai na metade superior, o bit é um; emite-se, subtrai-se o meio, dobra-se.

O terceiro caso é o incômodo: o intervalo está a cavalo sobre o meio, contido no quarto central. Nenhum bit está decidido — pode ainda virar 0111... ou 1000... — mas o intervalo é pequeno demais e precisa ser expandido, ou a precisão acaba. A solução é expandir em torno do meio e contar um bit pendente. Quando o próximo bit real finalmente sair, emitem-se tantos bits invertidos quantos foram os pendentes, porque é exatamente isso que a expansão significa.

void codificar(std::uint64_t cum_baixo, std::uint64_t cum_alto,
               std::uint64_t total) {
    const std::uint64_t faixa = alto_ - baixo_ + 1;
    alto_ = baixo_ + faixa * cum_alto / total - 1;
    baixo_ = baixo_ + faixa * cum_baixo / total;
    for (;;) {
        if (alto_ < kMeio) {
            emitir(false);
        } else if (baixo_ >= kMeio) {
            emitir(true);
            baixo_ -= kMeio; alto_ -= kMeio;
        } else if (baixo_ >= kUm4 && alto_ < kTres4) {
            ++pendentes_;
            baixo_ -= kUm4; alto_ -= kUm4;
        } else {
            break;
        }
        baixo_ = baixo_ << 1;
        alto_ = (alto_ << 1) | 1;
    }
}

Três decisões de implementação merecem nota.

A primeira: o modelo entrega contagens inteiras, nunca probabilidades. Codificador e decodificador precisam ver exatamente os mesmos números; um erro de arredondamento de uma unidade no último bit de um double faz o decodificador escolher o símbolo errado, e a partir dali tudo é lixo. Com inteiros, o problema não existe.

A segunda: o fluxo de saída é std::vector<std::uint8_t>, e não std::vector<bool>. A especialização vector<bool> empacota bits e não tem armazenamento contíguo, então não se converte em std::span<const bool> — o compilador recusa, e com razão. Um bit por byte desperdiça memória que aqui não faz falta, e evita a única especialização da biblioteca padrão que não se comporta como um contêiner.

A terceira: o programa verifica a si mesmo. Toda chamada comprime, descomprime e afirma que a volta é igual à ida:

const auto fluxo = comprimir(mod, texto);
const auto volta = descomprimir(mod, fluxo, texto.size());
assert(volta == texto && "ida e volta precisa devolver a entrada");

Um codificador que comprime mas não descomprime não é um codificador; é um triturador. A saída, para a mensagem curta:

--- ABRACADABRA (11 simbolos, alfabeto ABCDR) ---
  ordem 0: ideal   22,444107 bits | emitidos  23 bits | bruto  25,5412 bits | ida e volta: ok
  ordem 1: ideal    7,137504 bits | emitidos   8 bits | bruto  25,5412 bits | ida e volta: ok
  ordem 2: ideal    3,596935 bits | emitidos   5 bits | bruto  25,5412 bits | ida e volta: ok

O arquivo completo está em lista_ilya/codigo/IL03_arithmetic_coder.cpp.

8. A volta: todo compressor é um modelo

Provamos que todo modelo define um compressor. Falta a direção contrária, que quase nunca se ensina e é metade da tese da série.

Seja $\mathcal{C}$ um compressor sem perdas qualquer — gzip, zstd, um programa que alguém escreveu ontem — que mapeia cada mensagem $x$ em uma sequência de $L(x)$ bits, de forma unicamente decodificável. Defina

Pelo teorema de McMillan, demonstrado em IL02, todo código unicamente decodificável satisfaz $\sum_x 2^{-L(x)} \le 1$. Logo $Q_{\mathcal{C}}$ é uma distribuição de probabilidade sobre as mensagens, a menos de massa não atribuída — e a massa faltante, $1 - \sum_x Q_{\mathcal{C}}(x)$, mede exatamente a capacidade que o compressor pagou e não usou.

Junte as duas direções:

Todo modelo probabilístico é um compressor com custo $-\log_2 Q(x)$, e todo compressor é um modelo com probabilidade $2^{-L(x)}$. Melhorar o modelo e encurtar o arquivo são a mesma operação, escrita em dois vocabulários.

Isto tem consequências práticas imediatas, e vale nomear duas.

A primeira: a razão de compressão de um arquivo por um compressor genérico é uma estimativa da entropia daquele arquivo, sob o modelo implícito naquele compressor. Não é uma analogia. É a identidade lida da direita para a esquerda. IL12 vai usar exatamente isso para medir a complexidade de configurações de um autômato celular, sem escrever um estimador de entropia — só chamando um compressor.

A segunda: quando um artigo relata que um modelo de linguagem atinge $1{,}8$ bit por token, ele está relatando uma taxa de compressão. É a mesma quantidade, medida no mesmo lugar.

9. Três nomes do mesmo número

O ramo tem três vocabulários para $-\log_2 Q$, e a leitora vai encontrar os três.

Em treinamento, a média de $-\ln Q(x_t \mid x_{<t})$ sobre o corpus é a perda de entropia cruzada, ou negative log-likelihood, medida em nats porque o logaritmo natural é mais conveniente para derivar. A série Transformers derivou essa quantidade pelo lado probabilístico em A Probabilidade da Linguagem, e a relação entre as bases é a de sempre:

Em avaliação, a mesma média em base dois chama-se bits por token, e sua exponencial chama-se perplexidade:

Em compressão, chama-se taxa, e comparada com o modelo uniforme dá a razão de compressão:

Com $V = 50\,257$, o vocabulário do GPT-2, o uniforme custa $15{,}6170$ bits por token:

Três colunas, um número. Quem otimiza entropia cruzada está encurtando um arquivo, saiba disso ou não.

E é aqui que a Parte VI da série já lança sua sombra: se treinar é comprimir, e se o modelo também custa bits, então existe uma pergunta quantitativa sobre como esse número cai conforme o modelo e os dados crescem. A resposta é uma lei de potência estável ao longo de sete ordens de grandeza, e IL45 vai derivá-la.

10. A pergunta que fica

Terminamos com um resultado e um desconforto.

O resultado: um modelo melhor sempre encurta os dados, e o encurtamento é mensurável em bits com precisão exata. De ordem zero para ordem um, ABRACADABRA foi de $22{,}44$ para $7{,}14$ bits.

O desconforto: se é assim, por que parar? Um modelo de ordem dez sobre onze símbolos daria custo de dados praticamente nulo — cada contexto de dez símbolos ocorre uma vez só e determina o seguinte. Custo zero. Compressão perfeita.

E completamente inútil, porque o modelo de ordem dez é a mensagem, escrita de outro jeito. Transmiti-lo custaria mais do que transmitir os dados originais.

Falta a metade da conta. O próximo artigo a completa, e o nome dela é comprimento de descrição mínima.

Um modelo probabilístico não se parece com um compressor. Ele é um, e a única coisa que faltava era o codificador certo.

11. Exercícios

1. Execute os dois passos do estreitamento para a mensagem AB sob o modelo de ordem zero, em frações exatas, e calcule $-\log_2 w$.

2. Calcule $-\log_2 Q(x)$ para ABRA somando $-\log_2 p$ símbolo a símbolo, e confira contra a largura do intervalo da figura da Seção 2.

3. Converta uma entropia cruzada de $1{,}6$ bit por token em perplexidade e em razão de compressão sobre um vocabulário de $32\,000$ símbolos.

4. Verifique que os cinco intervalos de um símbolo particionam $[0,1)$ exatamente, exibindo os extremos em frações.

5. Calcule o custo de ABRACADABRA sob um modelo uniforme sobre cinco símbolos e compare com os $22{,}4441$ bits do modelo empírico.

6. A partir de qual comprimento de mensagem o aritmético passa a bater o Huffman na fonte não diádica de IL02?

7. Prove por indução que $w_n = Q(x)$.

8. Um compressor mapeia três mensagens em códigos de comprimentos $(1,3,3)$. Exiba a distribuição induzida e calcule a massa desperdiçada.

9. O modelo de ordem um deu $7{,}14$ bits para a mensagem, mas ele próprio precisa ser transmitido. Estime esse custo e decida se ele se paga em onze símbolos. Determine o comprimento de equilíbrio.

10. Um compressor sem perdas que encurtasse toda entrada é impossível. Prove por contagem, e explique o que essa impossibilidade diz sobre a afirmação “modelos melhores comprimem mais”.

12. Soluções

1. Está feito na Seção 3. Após $A$, o intervalo é $[0, 5/11)$ com $w = 5/11$; após $B$, é $[25/121, 35/121)$ com $w = 10/121$. E

2. Somando: $-\log_2\frac{5}{11} - \log_2\frac{2}{11} - \log_2\frac{2}{11} - \log_2\frac{5}{11} = 7{,}193870$ bits. A largura do intervalo na figura é $6{,}830135 \times 10^{-3}$, e $-\log_2$ disso dá $7{,}193870$. Idênticos, e o produto das frações confirma: $w = 100/14641 = (5 \cdot 2 \cdot 2 \cdot 5)/11^4$.

3. $\mathrm{PPL} = 2^{1{,}6} = 3{,}0314$. E $\log_2 32\,000 = 14{,}9658$, logo a razão é $14{,}9658/1{,}6 = 9{,}3536\times$.

4. Os extremos são $0$, $5/11$, $7/11$, $8/11$, $9/11$, $1$, e as larguras $5/11$, $2/11$, $1/11$, $1/11$, $2/11$, que somam $11/11 = 1$. A partição é exata porque as probabilidades somam 1 — a mesma razão pela qual a soma de Kraft de um código completo dá 1, e não é coincidência: são a mesma conta em dois formatos.

5. Sob o uniforme, cada símbolo custa $\log_2 5 = 2{,}3219$ bits, e a mensagem custa $11 \times 2{,}3219 = 25{,}5412$. O modelo empírico custa $22{,}4441$, economizando $3{,}0971$ bits. Modesto — o modelo de ordem zero sabe apenas que $A$ é frequente.

6. O Huffman perde $\bar{L} - H = 2{,}200000 - 2{,}121928 = 0{,}078072$ bit por símbolo, sempre. O aritmético perde uma constante na mensagem inteira. O aritmético vence quando

Com o excesso teórico de 2 bits, $n > 25{,}6$, ou seja $n \ge 26$. Com o excesso medido de $\approx 1{,}2$ bit, $n > 15{,}4$, ou seja $n \ge 16$. A partir de algumas dezenas de símbolos a constante já perdeu para a taxa, e a partir daí a distância só cresce.

7. Está na Seção 4. O núcleo é que a subtração $\mathrm{hi}’ - \mathrm{lo}’$ cancela os dois termos em $F(x_t)$, deixando $w_t \cdot Q(x_t \mid x_{<t})$, e o produto telescópico resultante é a regra da cadeia.

8. $Q = (2^{-1}, 2^{-3}, 2^{-3}) = (1/2, 1/8, 1/8)$, com soma $3/4$. A massa desperdiçada é $1/4$.

Isso significa que o código é incompleto: existe capacidade de árvore paga e não usada. Por Kraft, e pelo argumento do Exercício 9 de IL02, algum comprimento pode ser encurtado sem violar a desigualdade — de fato, $(1,2,2)$ tem $K = 1$ e comprimento médio estritamente menor para qualquer distribuição.

9. O modelo de ordem um precisa de uma tabela de contagens por contexto. Em ABRACADABRA há cinco contextos observados — $A$, $B$, $C$, $D$, $R$ — e cada um precisa de cinco contagens, uma por símbolo do alfabeto. Codificando cada contagem em quatro bits, já que nenhuma passa de 10:

A economia em onze símbolos é $22{,}4441 - 7{,}1375 = 15{,}3066$ bits. Cem bits de modelo para economizar quinze: não se paga, e não chega nem perto.

O comprimento de equilíbrio sai dividindo o custo do modelo pela economia por símbolo:

Este exercício é o artigo seguinte, resolvido em um caso particular. A pergunta “quando o modelo se paga” tem nome, tem teoria e tem dois artigos dedicados a ela.

10. Suponha um compressor sem perdas que encurte toda entrada de comprimento $L$. Há $2^L$ entradas distintas. As saídas teriam comprimento menor que $L$, e o número total de sequências binárias de comprimento menor que $L$ é

Menos saídas que entradas. Pelo princípio da casa dos pombos, duas entradas distintas receberiam a mesma saída, e o código não seria injetivo — logo não seria sem perdas. Contradição.

Sobre o que isso diz da afirmação “modelos melhores comprimem mais”: ela é verdadeira para as entradas que o modelo descreve bem, e necessariamente falsa para outras. Toda probabilidade que um modelo concede a um padrão é retirada de outro, porque as probabilidades somam 1; e toda redução de comprimento em um conjunto de mensagens é paga com aumento em outro, porque a soma de Kraft é limitada por 1.

Um compressor de texto em português não comprime ruído branco, e não é um defeito: é a mesma conta que o faz funcionar em português. Compressão não é mágica de propósito geral; é uma aposta declarada sobre que tipo de dado vai aparecer — que é, palavra por palavra, o que um modelo é.

Progresso na lista: este artigo não fecha nenhum item — é pré-requisito. Continuam 0 de 30 itens estudados, 30 pela frente.

13. Acrônimos e Abreviações neste artigo

A seguir está a lista de todos os acrônimos e abreviações identificados no texto, organizados em ordem alfabética com o termo original em inglês e a tradução para o português:

14. Referências

COVER, T. M.; THOMAS, J. A. Elements of Information Theory. 2. ed. Hoboken: Wiley, 2006.

HOWARD, P. G.; VITTER, J. S. Arithmetic Coding for Data Compression. Proceedings of the IEEE, v. 82, n. 6, p. 857–865, 1994.

MacKAY, D. J. C. Information Theory, Inference, and Learning Algorithms. Cambridge: Cambridge University Press, 2003.

MOFFAT, A.; NEAL, R. M.; WITTEN, I. H. Arithmetic Coding Revisited. ACM Transactions on Information Systems, v. 16, n. 3, p. 256–294, 1998.

RISSANEN, J.; LANGDON, G. G. Arithmetic Coding. IBM Journal of Research and Development, v. 23, n. 2, p. 149–162, 1979.

SHANNON, C. E. A Mathematical Theory of Communication. Bell System Technical Journal, v. 27, n. 3, p. 379–423, 1948.

WITTEN, I. H.; NEAL, R. M.; CLEARY, J. G. Arithmetic Coding for Data Compression. Communications of the ACM, v. 30, n. 6, p. 520–540, 1987.