Como medir praticamente a entropia de um arquivo?

Agora estou tentando medir muitas informações não redundantes (reais) do meu arquivo. Alguns chamam isso de quantidade de entropia.

É claro que existe o log p (x) padrão {p (x)}, mas acho que Shannon estava considerando apenas o ponto de vista da transmissão através de um canal. Portanto, a fórmula requer um tamanho de bloco (digamos em bits, 8 normalmente). Para um arquivo grande, esse cálculo é bastante inútil, ignorando correlações de curta a longa distância entre símbolos.

Existem métodos binários de árvore e Ziv-Lempel, mas estes parecem altamente acadêmicos por natureza.

A compressibilidade também é considerada uma medida de entropia, mas parece não haver um limite inferior quanto ao grau de compressão. Para o meu arquivo hiss.wav,

• hiss.wav original = 5,2 MB
• entropia via fórmula de Shannon = 4,6 MB
• hiss.zip = 4.6 MB
• hiss.7z = 4.2 MB
• hiss.wav.fp8 = 3,3 MB

Existe algum método razoavelmente praticável para medir a quantidade de entropia existente no hiss.wav?

Entropia é um recurso de uma variável aleatória . Um determinado arquivo tem zero entropia, pois é constante. A entropia faz sentido em muitas situações em que não há canal, e você pode aplicá-la a um conjunto aleatório de, por exemplo, arquivos WAV, gerados a partir de uma determinada fonte. Nesse caso, seu é o arquivo WAV inteiro .$x$

O arquivo WAV real (excluindo o cabeçalho) pode ser pensado para ser gerado por alguma fonte markoviana. Esta fonte produz amplitudes sonoras ("amostras") em uma sequência, cada uma dependendo das anteriores. Depois de executar o processo por muito tempo, a entropia de cada amostra (mais precisamente, a entropia condicional dada as amostras anteriores) fica muito próxima de algum valor limitador, que definimos como a entropia da fonte. A entropia de amostras é vezes esse número (no limite; novamente, com mais precisão, estamos medindo a entropia condicional). Lempel e Ziv mostraram que, se a entropia da amostra for bits , seu algoritmo comprime amostras para$N$$N$$H$$N$$HN + o(N)$bits, com alta probabilidade (a probabilidade está acima das amostras). A compressão Lempel – Ziv é bastante popular na prática, usada, por exemplo, no gzipformato popular .

Devido a este resultado de Lempel e Ziv, a entropia de uma fonte pode ser aproximada comprimindo uma longa sequência de amostras usando o algoritmo Lempel – Ziv. Isso não estima a entropia das amostras específicas, que não é um conceito bem definido (uma sequência constante tem entropia zero), mas a entropia da fonte que a gera.

Um conceito relacionado é a entropia algorítmica , também conhecida como complexidade de Kolmogorov . É a duração do programa mais curto que gera seu arquivo. Essa quantidade faz sentido para um arquivo individual. No caso de um arquivo gerado por uma fonte aleatória, o teorema de Lempel – Ziv mostra que a entropia algorítmica de um arquivo é limitada, com alta probabilidade, por sua entropia de Shannon. Infelizmente, a entropia algorítmica não é computável, por isso é mais um conceito teórico.

Para completar a imagem, sugiro ler o artigo de Shannon sobre Predição e entropia do inglês impresso para uma abordagem diferente para estimar a entropia de uma fonte.