¿Cómo medir prácticamente la entropía de un archivo?

9

Estoy tratando de medir ahora mucha información no redundante (real) que contiene mi archivo. Algunos llaman a esto la cantidad de entropía.

Por supuesto, existe el estándar p (x) log {p (x)}, pero creo que Shannon solo lo estaba considerando desde el punto de vista de transmitir a través de un canal. Por lo tanto, la fórmula requiere un tamaño de bloque (digamos en bits, 8 típicamente). Para un archivo grande, este cálculo es bastante inútil, ignorando correlaciones de corta a larga distancia entre símbolos.

Existen métodos de árbol binario y Ziv-Lempel, pero estos parecen de naturaleza altamente académica.

La compresibilidad también se considera una medida de entropía, pero parece que no hay un límite inferior en cuanto al grado de compresión. Para mi archivo hiss.wav,

  • hiss.wav original = 5.2 MB
  • entropía a través de la fórmula de Shannon = 4.6 MB
  • hiss.zip = 4.6 MB
  • hiss.7z = 4.2 MB
  • hiss.wav.fp8 = 3.3 MB

¿Existe algún método razonablemente factible para medir cuánta entropía existe dentro de hiss.wav?

entropy Paul Uszak
fuente
1
No entiendo lo que quieres decir con "altamente académico".
David Richerby
Muerto. Pensé que con la escala de dólares de investigación gastada globalmente para maximizar la transmisión y el almacenamiento de datos, habría una forma más desarrollada de estimar cuánto de las malditas cosas con las que realmente está tratando. No habría pensado más allá de la posibilidad de que hubiera una utilidad de archivo que pasara por encima de algunos datos que generen la estimación teórica de la entropía. ¿A qué juegan los fabricantes de discos y telecomunicaciones?
Paul Uszak

Respuestas:

9

x

NNHNHN+o(N)gzip

Debido a este resultado de Lempel y Ziv, la entropía de una fuente se puede aproximar comprimiendo una secuencia larga de muestras usando el algoritmo Lempel-Ziv. Esto no estima la entropía de las muestras específicas, que no es un concepto bien definido (una secuencia constante tiene cero entropía), sino la entropía de la fuente que lo genera.

Un concepto relacionado es la entropía algorítmica , también conocida como complejidad de Kolmogorov . Es la longitud del programa más corto que genera su archivo. Esta cantidad tiene sentido para un archivo individual. En el caso de un archivo generado por una fuente aleatoria, el teorema de Lempel-Ziv muestra que la entropía algorítmica de un archivo está limitada, con alta probabilidad, por su entropía de Shannon. Desafortunadamente, la entropía algorítmica no es computable, por lo que es más un concepto teórico.

Para completar la imagen, sugiero leer el artículo de Shannon sobre Predicción y entropía del inglés impreso para un enfoque diferente para estimar la entropía de una fuente.

Yuval Filmus
fuente
Yo tengo. Y el papel de Schurmann y Grassberger. Según sus entropías estimadas para el inglés, parece que la mejor estimación de entropía que podemos obtener es mediante la compresión con una variante PAQ8 como fp8. Hay y mis resultados se casan bastante bien para la prosa de Shakespeare.
Paul Uszak
Sin embargo, el problema parece ser que habría pensado que debe haber un valor teórico limitante para la entropía de una fuente. La determinación por compresión solo refleja la eficiencia del algoritmo de compresión. Empíricamente, su gzip es bueno, pero 7z es mejor. Y fp8 es mucho mejor como se muestra en mi pregunta. ¿Podría encontrar que hiss.wav solo contiene 10 bytes de entropía total cuando uso fp12000 en el futuro lejano?
Paul Uszak
La entropía no es propiedad de un archivo; cada archivo individual tiene cero entropía. Más bien, la entropía es una propiedad de una fuente aleatoria. Una medida de aleatoriedad apropiada para archivos específicos es la complejidad de Kolmogorov (también conocida como entropía algorítmica), pero desafortunadamente esta medida no es computable.
Yuval Filmus
Cuando comprime un archivo para estimar la entropía de una fuente, utiliza un teorema que garantiza que la tasa de compresión de los datos generados por la fuente se aproxima a la entropía de la fuente. Sin embargo, las utilidades de compresión reales no aplican el algoritmo de Vampe Lempel-Ziv, sino una versión más práctica del mismo. Si desea estimar la entropía, tal vez debería volver a implementar el algoritmo con este objetivo en mente.
Yuval Filmus
Eliminé una discusión poco constructiva; Los comentarios no son para largas discusiones, excepto para mejorar la publicación en cuestión. Si desea hablar honestamente sobre asuntos de entropía, cree una sala de chat. Recuerda mantenerlo civil.
Raphael