Existe uma generalização da codificação de Huffman para a codificação aritmética?

11

Ao tentar entender as relações entre a codificação de Huffman, a codificação aritmética e a codificação de intervalo, comecei a pensar nas deficiências da codificação de Huffman relacionadas ao problema do empacotamento de bits fracionário .

Ou seja, suponha que você tenha 240 valores possíveis para um símbolo e precise codificá-lo em bits, você ficaria com 8 bits por símbolo, mesmo que não precise de um 8 "completo", pois 8 pode expressar 256 valores possíveis por símbolo. Uma solução para esse problema é algo que eu já vi chamado de "empacotamento fracionário de bits", onde você pode "deslocamento de bits" por uma não-potência de dois usando multiplicação. Assim como a multiplicação de potências de dois está mudando x * 2 == x << 1e x * 4 == x << 2assim por diante para todas as potências de dois, também é possível "alternar" com uma não potência de 2 multiplicando em vez disso e agrupando símbolos com tamanho de bit fracionário .

O problema é semelhante à codificação de Huffman: você acaba com códigos que devem ter um tamanho não-fracionário e, portanto, possuem essa ineficiência de empacotamento. No entanto, você não pode simplesmente usar a solução de empacotamento de bits fracitonal, porque esta solução assume símbolos de tamanho fixo.

A questão é : existem documentos ou soluções para aprimorar a codificação de Huffman com uma idéia semelhante à embalagem de bits fracionários para obter algo semelhante à codificação aritmética? (ou quaisquer resultados em contrário).

Realz Slaw
fonte
11
A codificação aritmética já é ótima. Não há necessidade de melhorá-lo.
Yuval Filmus
@YuvalFilmus sim, eu quis dizer, como melhorar a codificação de Huffman para torná-la equivalente à codificação aritmética.
Realz Slaw
11
Apenas como sugestão, você pode achar a codificação do Sistema Numérico Assimétrico (ANS) mais fácil de entender do que a codificação aritmética. Em particular, é um pouco mais fácil ver essa formulação específica como "empacotamento fracionário de bits".
Pseudônimo
@ Pseudônimo Encontrei esta página que parece fazer essa conexão entre rANS e Huffman Coding. Não posso dizer que entendi ainda, mas acho que é suficiente. Se você fizer uma resposta ao comentário, eu aceito.
Realz Slaw
@YuvalFilmus Espero que eu tenha defendido que a codificação aritmética precisava de melhorias, e o ANS é uma melhoria.
Pseudônimo

Respostas:

12

Vejamos uma maneira um pouco diferente de pensar sobre a codificação de Huffman.

Suponha que você tenha um alfabeto de três símbolos, A, B e C, com probabilidades 0,5, 0,25 e 0,25. Como as probabilidades são todas as potências inversas de dois, esse código Huffman é ideal (ou seja, é idêntico à codificação aritmética). Usaremos o código canônico 0, 10, 11 para este exemplo.

Suponha que nosso estado seja um número inteiro grande, que chamaremos de . Você pode pensar em codificação como uma função que pega o estado atual e um símbolo para codificar e retorna o novo estado:s

codificar(s,UMA)=2scodificar(s,B)=4s+2codificar(s,C)=4s+3

Então, vamos começar com o estado 11 (que é 1011 em binário), codifique o símbolo B. O novo estado é 46, que é 101110 em binário. Como você pode ver, esse é o estado "antigo", com a sequência 10 adicionada ao final. Temos essencialmente "saída" da sequência de bits 10.

Por enquanto, tudo bem.

Agora pense por um momento sobre como a codificação aritmética funciona. Se você colocar as probabilidades sobre um denominador comum, o símbolo A realmente representa o intervalo , o símbolo B representa o intervalo[2[0 04,24)e o símbolo C representa o intervalo[3[24,34).[34,44)

Basicamente, o que estamos fazendo aqui é multiplicar tudo pelo denominador comum. Imagine que o estado estava realmente na base 4. A codificação de um símbolo B está realmente gerando o dígito 2 nessa base, e a codificação de um símbolo C está gerando o dígito 3 nessa base.

No entanto, o símbolo A é um pouco diferente, porque não é um dígito inteiro na base 4.

Em vez disso, podemos pensar no alfabeto como o conjunto de símbolos A_0, A_1, B, C, com igual probabilidade. Isso, novamente, possui um código Huffman ideal 00, 01, 10, 11. Ou, novamente, podemos pensar nisso na base 4. Para codificar um símbolo, basta:

codificar(s,UMA0 0)=4s+0 0codificar(s,UMA1 1)=4s+1 1codificar(s,B)=4s+2codificar(s,C)=4s+3

UMA0 0UMA1 1

s

s=s2
Eu=smod2

codificar(s,UMAEu)

s=11s=5Eu=1 1codificar(5,UMA1 1)=4×5+1 1=21

Agora isso não produz exatamente a mesma saída de bits da codificação Huffman, mas gera uma saída que tem o mesmo comprimento. E o que eu espero que você possa ver é que isso também é decodificável. Para decodificar um símbolo, pegamos o restante quando dividido por 4. Se o valor for 2 ou 3, o símbolo será B ou C, respectivamente. Se for 0 ou 1, o símbolo é A e, em seguida, podemos colocar o bit de informações de volta multiplicando o estado por 2 e adicionando 0 ou 1.

3525

codificar(s,UMA0 0)=5s+0 0codificar(s,UMA1 1)=5s+1 1codificar(s,UMA2)=5s+2codificar(s,B0 0)=5s+3codificar(s,B1 1)=5s+4

s=s3Eu=smod3codificar(s,UMAEu)

pq

A razão pela qual é uma família de métodos de codificação é que o que vimos aqui é impraticável por si só; ele precisa de algumas modificações para lidar com o fato de que você provavelmente não possui números inteiros de precisão infinita para manipular a variável state com eficiência, e existem várias maneiras de conseguir isso. A codificação aritmética, é claro, tem um problema semelhante com a precisão de seu estado.

As variantes práticas incluem rANS (o "r" significa "proporção") e tANS ("orientado a tabelas").

O ANS tem algumas vantagens interessantes sobre a codificação aritmética, tanto práticas quanto teóricas:

  • Ao contrário da codificação aritmética, o "estado" é uma única palavra, e não um par de palavras.
  • Não apenas isso, mas um codificador ANS e seu decodificador correspondente têm estados idênticos e suas operações são completamente simétricas. Isso levanta algumas possibilidades interessantes, como a possibilidade de intercalar diferentes fluxos de símbolos codificados e tudo sincronizar perfeitamente.
  • As implementações práticas precisam, é claro, de "produzir" informações à medida que você avança, e não apenas coletá-las em um grande número inteiro para serem gravadas no final. No entanto, o tamanho da "saída" pode ser configurado em troca da perda de compactação (geralmente modesta). Portanto, onde os codificadores aritméticos devem produzir um pouco de cada vez, o ANS pode produzir um byte ou um nybble por vez. Isso oferece uma troca direta entre velocidade e compactação.
  • Parece ser tão rápido no hardware da geração atual quanto a codificação aritmética binária e, portanto, competitiva com a codificação Huffman. Isso o torna muito mais rápido que a codificação aritmética de alfabeto grande e suas variantes (por exemplo, codificação por faixa).
  • Parece estar livre de patentes.

Acho que nunca mais vou fazer codificação aritmética.

Pseudônimo
fonte
3
Agora essa é a explicação mais clara sobre a codificação ANS que eu já vi.
Michael Deardeuff
2

Como um exemplo simples, se você tivesse três símbolos com probabilidade 1/3 cada, sua codificação ideal de Huffman usaria os três símbolos 0, 10 e 11 com uma média de 5/3 bits.

Existem 243 símbolos criados concatenando 5 dos símbolos originais, cada um com probabilidade 1/243. O que é muito mais próximo de 1/256. A codificação ótima de Huffman codificará 13 desses grupos em 7 bits e 230 grupos em 8 bits, para uma média de 7,9465 bits por grupo ou 1,5983 bits por símbolo original, abaixo dos 1,66667 bits para a codificação original de Huffman, com codificação aritmética de 1,5850 bits.

Portanto, em teoria, você pode simplesmente combinar dois símbolos em um símbolo maior ou três símbolos em um símbolo maior e usar a codificação Hufman para as combinações.

gnasher729
fonte