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

35

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?

Robert
fonte
11
Poderia ser uma maneira de estimar a entropia.
pipe

Respostas:

39

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 :

H(S)=ipij pi(j)logpi(j)

Isso também pode ser representado da seguinte maneira :

H(Y)=ijμiPijlogPij

μ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.

remetente
fonte
2
Muito obrigado! Isso explica perfeitamente qual foi o erro no meu raciocínio.
robert
Sua resposta seria ainda melhor se houvesse descompressores de dados, imagens e áudio como exemplos de processos modelados. Por exemplo, na compactação de dados LZ, o modelo assume uma máquina (decodificador) que recebe como comandos de entrada como (D, L): "copie para emitir L símbolos contíguos do deslocamento D em relação à posição atual de saída" ou (c): " copie o símbolo c para a posição de saída atual ”. O codificador LZ transforma seu fluxo de símbolos de entrada na linguagem de comando do decodificador, e o fluxo de símbolos de comando possui uma entropia (e comprimento) diferente do fluxo codificado. Outros tipos de compressão têm máquinas diferentes.
piiperi 12/01
@piiperi que parece útil - eu não conheço nenhum desses detalhes. (Estou
abordando
@senderle, eu quis dizer expandir o capítulo "Taxas de entropia dependem do modelo", com alguns exemplos concretos de processos. Você fala sobre um processo que gera eventos e os componentes de processamento de compressores de dados, imagens, vídeos, áudio etc. podem ser vistos como tais processos. Um codificador de entropia pura é a etapa final de um pipeline de compactação de dados. Nenhuma das etapas do pipeline realmente "reduz a entropia". Em vez disso, cada um deles cria instruções para uma máquina que pode reproduzir o fluxo de símbolos original. E cada fluxo de instruções tem uma entropia diferente e geralmente um comprimento diferente (ou seja, menor).
piiperi 12/01
12

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.

Luke Schwartzkopff
fonte
Então, as etapas adicionais usadas nos algoritmos de compactação antes da codificação da entropia são usadas apenas para permitir que o codificador da entropia se aproxime da entropia? Um codificador de entropia não chega perto da entropia por si só quando aplicado a uma mensagem arbitrária?
robert
De fato, isso não acontece (bem, dependendo do significado exato de "fechar").
Grimmy 10/01
As etapas adicionais permitem que o codificador de entropia mantenha a entropia da mensagem original enquanto reduz as informações supérfluas com mais eficiência do que se elas fossem aplicadas por conta própria. Se você aplica o pré-processamento ou não, a entropia será preservada, mas a compactação seria menos eficaz (você acabaria com uma codificação menos eficiente).
Luke Schwartzkopff
Não, a transformação de mover para frente não gera uma lista separada que deve ser transferida para o decodificador. A menos que você queira dizer a lista inicial.
user253751 10/01
Aah, você está certo, esse não foi o melhor exemplo :)
Luke Schwartzkopff
6

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.

catraca arrepiante
fonte
Isso significa que a entropia aparente é diferente do conteúdo das informações reais de uma mensagem? Como isso está relacionado à entropia real da mensagem?
robert
com "entropia aparente", quero dizer a entropia que a codificação de entropia pode compactar até. Codificador diferente terá padrões diferentes que eles procuram. Huffman se sai melhor quando os mesmos poucos símbolos são reutilizados frequentemente usados, lempel-ziff se sai melhor quando pedaços são repetidos, etc.
catraca maníaca
Mas os algoritmos de Lempel-Ziv não são algoritmos de codificação de entropia, certo? O que eu não entendo é por que eles são usados ​​antes dos codificadores de entropia, por exemplo, no LZMA, quando o codificador de entropia por si só já poderia supostamente comprimir a mensagem ao mínimo.
robert
11
@kutschkem Isso significa que a entropia não é uma medida absoluta do conteúdo informativo de uma mensagem, mas é relativa ao que é definido como um símbolo (por exemplo, um único caractere é considerado um símbolo versus um bit sendo considerado um símbolo)? Eu acho que isso explicaria onde minhas suposições estavam erradas.
robert
11
@robert ... No entanto, há uma troca, que é a informação "fora da banda" que Luke menciona em sua resposta, que geralmente é adicionada por essas etapas (tabelas de pesquisa para decodificar as informações codificadas). Portanto, não faz sentido definir todo o conteúdo como um símbolo e codificá-lo como 0 porque em algum lugar a informação deve ser armazenada como esse 0 codifica.
kutschkem 10/01
6

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.

DW
fonte
2

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:

Espero que ajude ou seja pelo menos interessante ...

TextGeek
fonte
1

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.

Kaz
fonte