Confusão de codificação aritmética adaptativa

Question

Estou confuso sobre o ponto de codificação aritmética adaptativa.

Eu entendo que a codificação aritmética estática envolve usar probabilidades predefinidas de símbolos que permanecem estáticos durante todo o processo.Eu também entendo que a codificação aritmética adaptativa envolve alterar todas as probabilidades após cada símbolo encontrado.

No entanto, qual é o ponto de alterar a probabilidade após cada símbolo?Por que você simplesmente passaria por um arquivo inteiro primeiro e determinaram as probabilidades e depois fazer a codificação aritmética como segunda passagem?

Além disso, eu não entendo como mudar a probabilidade de símbolos impacta a compressão?Se sabermos as probabilidades verdadeiras dos símbolos no arquivo, estamos comprimindo, então fará o arquivo menor?

Answer 1

Primeiro, considere "passando por um arquivo inteiro". Há algumas suposições que valem a pena pensar aqui.

Os arquivos podem ser muito grandes, e percorrendo-os duas vezes podem ser caros. Esta é uma razão pela qual a maioria dos padrões de compactação do mundo real é baseada em blocos ou janelas.

Existem situações em que você não tem "o arquivo inteiro" para começar, como um canal de comunicação. tls (antes de 1,3, pelo menos) suporta compactação, por exemplo.

Os arquivos nem sempre são homogêneos. Arquivos (por exemplo, tar ) são um caso no ponto. Um modelo estatístico apropriado para uma parte de um arquivo pode não ser apropriado para outra parte. Codificação adaptativa também se adapta a isso.

Quanto à sua pergunta final, se o codificador e decodificador soubessem as probabilidades verdadeiras dos símbolos no arquivo, estamos comprimindo, isso não precisaria ser transmitido. E, de fato, às vezes fazemos isso no mundo real. O padrão JPEG, por exemplo, especifica tabelas de codificação padrão para aqueles momentos quando eles são apropriados, e deixa um codificador é dono quando eles não são.

Transmitindo uma tabela de codificação estática eficientemente (isto é, compactando-a) é um problema não trivial, especialmente para um alfabeto de código grande. Para um esquema bem projetado, o custo de transmissão da tabela deve ser igual ao "custo de aprendizagem" de usar um código adaptativo.