Os algoritmos de compactação sem perdas reduzem a entropia?

De acordo com a Wikipedia :

A entropia de Shannon mede as informações contidas em uma mensagem em oposição à parte da mensagem que é determinada (ou previsível). Exemplos deste último incluem redundância na estrutura da linguagem ou propriedades estatísticas relacionadas às frequências de ocorrência de pares de letras ou palavras, trigêmeos etc.

Portanto, entropia é uma medida da quantidade de informação contida em uma mensagem. Os codificadores de entropia são usados ​​para compactar sem perda essa mensagem no número mínimo de bits necessário para representá-la (entropia). Para mim, parece que um codificador de entropia perfeito seria tudo o que é necessário para compactar sem perdas uma mensagem o máximo possível.

Muitos algoritmos de compactação, no entanto, usam etapas antes da codificação da entropia para reduzir supostamente a entropia da mensagem.

De acordo com a Wikipedia alemã

Entropiekodierer werden häufig mit anderen Kodierern kombiniert. Dabei dienen vorgeschaltete Verfahren dazu, the Entropie der Daten zu verringern.

Em inglês:

Codificadores de entropia são freqüentemente combinados com outros codificadores. As etapas anteriores servem para reduzir a entropia dos dados.

ou seja, o bzip2 usa a Burrows-Wheeler-Transform seguida de uma Move-To-Front-Transform antes de aplicar a codificação de entropia (codificação de Huffman neste caso).

Essas etapas realmente reduzem a entropia da mensagem, o que implicaria na redução da quantidade de informações contidas na mensagem? Isso me parece contraditório, pois isso significaria que as informações foram perdidas durante a compactação, impedindo a descompressão sem perdas. Ou eles apenas transformam a mensagem para melhorar a eficiência do algoritmo de codificação da entropia? Ou a entropia não corresponde diretamente à quantidade de informações na mensagem?

Muitas descrições casuais de entropia são confusas dessa maneira, porque a entropia não é uma medida tão clara e organizada quanto às vezes apresentada. Em particular, a definição padrão de entropia de Shannon estipula que ela só se aplica quando, como a Wikipedia coloca, "as informações devido a eventos independentes são aditivas".

Em outras palavras, eventos independentes devem ser estatisticamente independentes. Se não estiverem, será necessário encontrar uma representação dos dados que definam os eventos de maneira a torná-los verdadeiramente independentes. Caso contrário, você superestimará a entropia.

Em outras palavras, a entropia de Shannon se aplica apenas a verdadeiras distribuições de probabilidade, e não a processos aleatórios em geral. Para exemplos concretos de processos que não se encaixam nas suposições da entropia de Shannon, considere ...

Processos de Markov

Um processo de Markov gera uma série de eventos nos quais o evento mais recente é amostrado de uma distribuição que depende de um ou mais eventos anteriores. Obviamente, um grande número de fenômenos do mundo real é melhor modelado como processos de Markov do que como distribuições de probabilidade independentes e discretas. Por exemplo: o texto que você está lendo agora!

A taxa de entropia de Shannon calculada ingenuamente de um processo de Markov sempre será maior ou igual à taxa de entropia verdadeira do processo. Para obter a verdadeira entropia do processo, é necessário levar em consideração a dependência estatística entre os eventos. Em casos simples, a fórmula para isso é assim :

Isso também pode ser representado da seguinte maneira :

$\mu_i$

Essa é uma maneira complicada de dizer que, mesmo quando você pode calcular a probabilidade geral de um determinado evento, certas sequências de eventos têm mais probabilidade do que outras de serem geradas por um processo de Markov. Por exemplo, as três seqüências de palavras em inglês a seguir são cada vez menos prováveis:

• Eles correram para a árvore
• A árvore correu para eles
• Árvore que eles correram

Mas a entropia de Shannon avaliará todas as três seqüências como igualmente prováveis. A entropia do processo de Markov leva em consideração a diferença e, como resultado, atribui uma taxa de entropia mais baixa ao processo.

As taxas de entropia dependem do modelo

Se você diminuir o zoom, eis o quadro geral: a taxa de entropia de uma determinada sequência de eventos de uma fonte desconhecida depende do modelo. Você atribuirá uma taxa de entropia diferente a uma série específica de eventos, dependendo de como modelar o processo que os gerou.

E com muita frequência, seu modelo do processo não será muito correto. Este não é um problema simples ou fácil de resolver. De fato, em geral, é impossível atribuir uma taxa de entropia verdadeira a uma sequência de eventos suficientemente longa e complexa se você não souber qual é o verdadeiro processo subjacente. Este é um resultado central na teoria algorítmica da informação .

Na prática, o que isso significa é que, dada uma fonte desconhecida de sequências de eventos, diferentes modelos produzirão diferentes entropias, e é impossível saber qual é o correto a longo prazo - embora o que atribua a menor entropia seja provavelmente o melhor.

Não, se o algoritmo estiver sem perdas, nenhuma etapa na sequência de compactação poderá reduzir sua entropia - caso contrário, não seria possível descomprimir / decodificar. No entanto, a entropia adicional pode ser armazenada em informações 'fora da banda' - como a lista que precisa ser mantida para decodificar a transformação de mover para frente.

Eles reduzem a entropia aparente inerente à estrutura da mensagem original. Ou, em outras palavras, eles ajustam a mensagem para fazer uso dos pontos fortes dos próximos estágios da compressão.

Um exemplo simples seria substituir o nome nas tags finais do xml por um símbolo especial. Você pode recriar perfeitamente o xml original a partir disso, mas o compressor não precisa incluir o nome completo novamente nesse local.

Um exemplo mais real é a compactação png. Seu compressor de entropia é DEFLATE, que é uma combinação de Lempel-Ziff e Huffman. Isso significa que funciona melhor com valores e padrões que se repetem com frequência. A maioria dos pixels adjacentes costuma ter cores semelhantes. Portanto, a cada linha é atribuído um filtro que transforma os valores originais do pixel em uma codificação diferencial. Dessa forma, os valores que acabam sendo codificados pelo DEFLATE são praticamente próximos de 0. No caso extremo, isso transformará um gradiente suave de todos os valores diferentes em um único valor em toda a linha da qual a parte LZ ou o DEFLATE faz um trabalho muito rápido.

Os codificadores de entropia não compactam a mensagem para o número mínimo de bits necessário para representá-la. Eu sei que é tentador pensar isso, mas não é o que eles fazem. Eles não são mágicos e não conseguem isso.

Em vez disso, eles fazem algo um pouco menos mágico - mas ainda são úteis. Suponha, por um momento, que soubéssemos que cada caractere da mensagem foi escolhido independentemente de alguma distribuição. Então seria possível criar um algoritmo de compactação sem perdas que comprima as mensagens de maneira ideal. Esses algoritmos são chamados de codificadores de entropia.

Agora, mensagens reais geralmente não têm essa propriedade de independência. Por exemplo, se você vê um Q, é provável que a próxima letra seja um U. E assim por diante. Ainda é possível aplicar um algoritmo de codificador de entropia a uma mensagem real, em que cada caractere não é escolhido independentemente do restante. O algoritmo continuará sem perdas, ainda poderá ser usado para compactação e, na prática, ainda reduzirá o tamanho da mensagem. No entanto, não o reduz ao tamanho mínimo possível. Não compacta a mensagem para algo cujo tamanho é igual à entropia da mensagem; comprime menos que isso.

Depois que você percebe essa propriedade dos codificadores de entropia, o paradoxo evapora.

Em geral, qualquer etapa sem perdas nunca reduz a entropia da mensagem. No entanto, ele pode colocar a mensagem em um formato em que algum outro algoritmo de compactação seja mais eficaz, portanto ainda pode ser útil (em média) na prática.

A palavra "Entropia", se usada com muita frequência, para se referir a duas coisas diferentes:

• A "quantidade total de informações" em uma mensagem ou sistema

• A "densidade" da informação, ou com que precisão a informação é compactada.

A citação do OP da entrada da Wikipedia para https://en.wikipedia.org/wiki/Entropy_(information_theory) refere-se ao primeiro:

Shannon's entropy measures the information contained in a message

Mas (pelo menos quando estou escrevendo isso) o mesmo artigo começa com:

Information entropy is the average rate at which information is produced by a stochastic source of data.

Então, um é uma quantidade e um é uma taxa (semelhante à distância versus velocidade). Às vezes, essas são chamadas de propriedades "extensivas" e "intensivas" (consulte https://en.wikipedia.org/wiki/Intensive_and_extensive_properties#Extensive_properties ).

Um exemplo clássico da distinção é o famoso sinal de lanterna de Paul Revere: "um se por terra e dois se por mar". 1 bit de informação total (se ignorarmos o caso "nenhum, se ainda não cheguei à Igreja do Norte"). Se Paulo adicionasse outro conjunto de lanternas em cada janela do edifício, isso seria '' 'redundante' '': não há mais informações; portanto, a mesma entropia "total" ou "extensa"; mas muito mais comprimento da mensagem, entropia "intensiva" muito menor.

Se ele começa dessa maneira, mas muda para usar apenas um conjunto de lanternas, isso é "compressão sem perdas", como na pergunta do OP. A entropia "extensa" é a mesma, mas a entropia "intensiva" é diferente: como o número de lanternas na 2ª janela está altamente correlacionado com o número que você viu na primeira, a mensagem redundante é mais previsível ou menos aleatório, tem uma entropia intensiva muito menor.

Há duas outras coisas importantes a serem lembradas:

• Primeiro, normalmente não sabemos a entropia "verdadeira" de um sistema em nenhum sentido. Um espectador ingênuo não sabe se "3 lanternas" seriam uma mensagem diferente ou se os sinais em uma janela diferente são redundantes ou não. Se Paul cria um hábito, podemos contar e ver se as janelas sempre se combinam. Mas talvez não tenhamos assistido o suficiente para ver as raras (e provavelmente importantes!) Exceções.

• Segundo, importa como você mede. Considere tentar estimar quanto é comunicado por cada letra sucessiva de texto (que é uma taxa, portanto, entropia "intensiva", também chamada de "entropia relativa"):

  • Se você perceber que as pessoas enviam texto em unidades de 8 bits, sua primeira "estimativa" pode ser de 8 bits por letra.
  • Se você contar o número de letras distintas usadas, estimará log2 (26) ou 4,7 bits por letra (um pouco mais alto se considerar espaços, maiúsculas e minúsculas etc.).
  • Se você considerar que "e" é uma aposta melhor para "próxima letra" do que "z", medirá as frequências das letras e obterá cerca de 4,14 (consulte http://people.seas.harvard.edu/~jones/cscie129/ papers / stanford_info_paper / entropy_of_english_9.htm ).
  • Se você contar pares de letras, verá padrões como "qu", "th" etc., e obterá cerca de 3,56.
  • Se você contar sequências de até 5 letras, obterá valores ainda mais baixos e, como bônus, poderá distinguir de maneira bastante confiável em qual idioma humano o texto está).
  • Se você é tão perspicaz e inteligente quanto NG Burton e JCR Licklider em "Restrições de longo alcance na estrutura estatística do inglês impresso" (American Journal of Psychology 68 (1955)), pode obter sequências de 10, 0000 letras seguidas e encontre outro valor de entropia.

Mas é claro que as mensagens podem (e têm) muitos padrões que não são modelados por métodos n-grama, portanto a entropia "verdadeira" é ainda mais baixa.

Se você modelar uma fonte infinita teórica com distribuição de tokens Zipfian perfeitamente aleatória, poderá calcular a entropia extensa e intensa que ela teria, que acaba depender apenas do número de possíveis tokens distintos. Os gráficos de como cada tipo de entropia se parece com o aumento desse número estão em [ http://www.derose.net/steve/writings/dissertation/Diss.0.html] . Os dois se comportam de maneira bem diferente:

• total (extenso): http://www.derose.net/steve/writings/dissertation/Graph13.png
• relativa (intensiva): http://www.derose.net/steve/writings/dissertation/Graph14.png

Espero que ajude ou seja pelo menos interessante ...

Suspeito que a redação da Wikipedia alemã esteja errada. Compressores aumentam a entropia. Ou seja, não a entropia geral, mas a entropia por bit : a densidade da informação. Por exemplo, é aplicada alguma codificação de duração e esquema de dicionário para condensar os dados. Agora, a mesma informação é compactada em menos bits, portanto, cada bit carrega mais informações. A codificação subsequente de Huffman faz um pouco mais do mesmo; é apenas mais uma camada de compressão.