¿Los algoritmos de compresión sin pérdida reducen la entropía?

35

De acuerdo con Wikipedia :

La entropía de Shannon mide la información contenida en un mensaje en oposición a la parte del mensaje que se determina (o es predecible). Ejemplos de esto último incluyen redundancia en la estructura del lenguaje o propiedades estadísticas relacionadas con las frecuencias de aparición de pares de letras o palabras, trillizos, etc.

Entonces, la entropía es una medida de la cantidad de información contenida en un mensaje. Los codificadores de entropía se utilizan para comprimir sin pérdidas dicho mensaje al número mínimo de bits necesarios para representarlo (entropía). Para mí, esto parece que un codificador de entropía perfecto sería todo lo que se necesita para comprimir sin pérdida un mensaje tanto como sea posible.

Sin embargo, muchos algoritmos de compresión usan pasos antes de la codificación de entropía para supuestamente reducir la entropía del mensaje.

Según la Wikipedia alemana

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

En inglés:

Los codificadores de entropía se combinan con frecuencia con otros codificadores. Los pasos anteriores sirven para reducir la entropía de los datos.

es decir, bzip2 usa la Transformación de Burrows-Wheeler seguida de una Transformación de mover al frente antes de aplicar la codificación de entropía (codificación de Huffman en este caso).

¿Estos pasos realmente reducen la entropía del mensaje, lo que implicaría reducir la cantidad de información contenida en el mensaje? Esto me parece contradictorio, ya que eso significaría que la información se perdió durante la compresión, evitando la descompresión sin pérdida. ¿O simplemente transforman el mensaje para mejorar la eficiencia del algoritmo de codificación de entropía? ¿O la entropía no corresponde directamente a la cantidad de información en el mensaje?

information-theory data-compression entropy robert
fuente

1

Sin embargo, podría ser una forma de estimar la entropía.

tubería

39

Muchas descripciones casuales de la entropía son confusas de esta manera porque la entropía no es una medida tan clara y ordenada como se presenta a veces. En particular, la definición estándar de la entropía de Shannon estipula que solo se aplica cuando, como dice Wikipedia, "la información debida a eventos independientes es aditiva".

En otras palabras, los eventos independientes deben ser estadísticamente independientes. Si no lo son, entonces debe encontrar una representación de los datos que defina los eventos de manera que los haga realmente independientes. De lo contrario, sobreestimarás la entropía.

Para decirlo de otra manera, la entropía de Shannon solo se aplica a distribuciones de probabilidad verdaderas, y no a procesos aleatorios en general. Para ejemplos concretos de procesos que no se ajustan a los supuestos de la entropía de Shannon, considere ...

Procesos de Markov

Un proceso de Markov genera una serie de eventos en los que el evento más reciente se muestrea a partir de una distribución que depende de uno o más eventos anteriores. Obviamente, una gran cantidad de fenómenos del mundo real se modelan mejor como procesos de Markov que como distribuciones de probabilidad discretas e independientes. Por ejemplo: ¡el texto que estás leyendo ahora mismo!

La tasa de entropía de Shannon calculada ingenuamente de un proceso de Markov siempre será mayor o igual que la tasa de entropía verdadera del proceso. Para obtener la verdadera entropía del proceso, debe tener en cuenta la dependencia estadística entre los eventos. En casos simples, la fórmula para eso se ve así :

H (S) = - \sum_{yo} {pags}_{yo} \sum_{j} {pags}_{yo} (j) Iniciar sesión {pags}_{yo} (j)

$H(\mathcal{S}) = - \sum_i p_i \sum_j \ p_i (j) \log p_i (j)$

Esto también se puede representar así :

H (Y) = - \sum_{yo j} μ_{yo} {PAGS}_{yo j} Iniciar sesión {PAGS}_{yo j}

$H(Y) = - \sum_{ij} \mu_i P_{ij} \log P_{ij}$

Nuevamente citando Wikipedia, aquí " $\mu_i$ es la distribución asintótica de la cadena", es decir, la probabilidad general de que un evento determinado ocurra en un horizonte largo.

Esta es una forma complicada de decir que incluso cuando se puede calcular la probabilidad general de un evento determinado, ciertas secuencias de eventos tienen más probabilidades que otras de ser generadas por un proceso de Markov. Entonces, por ejemplo, las siguientes tres cadenas de palabras en inglés son cada vez menos probables:

Corrieron hacia el árbol
El árbol corrió hacia ellos
Árbol que corrieron

Pero la entropía de Shannon evaluará las tres cadenas como igualmente probables. La entropía del proceso de Markov tiene en cuenta la diferencia y, como resultado, asigna una tasa de entropía más baja al proceso.

Las tasas de entropía dependen del modelo

Si se aleja, aquí está el panorama general: la tasa de entropía de una secuencia dada de eventos de una fuente desconocida depende del modelo. Asignará una tasa de entropía diferente a una serie particular de eventos dependiendo de cómo modele el proceso que los generó.

Y con mucha frecuencia, su modelo del proceso no será del todo correcto. Este no es un problema simple o fácil de resolver. De hecho, en general, es imposible asignar una tasa de entropía verdadera a una secuencia de eventos suficientemente larga y compleja si no se sabe cuál es el verdadero proceso subyacente. Este es un resultado central en la teoría de la información algorítmica .

Lo que significa en la práctica es que, dada una fuente desconocida de secuencias de eventos, diferentes modelos producirán diferentes entropías, y es imposible saber cuál es la correcta a largo plazo, aunque la que asigna la entropía más baja es probablemente la mejor.

senderle
fuente

2

¡Muchas gracias! Esto explica perfectamente cuál fue el error en mi razonamiento.

Robert

Su respuesta sería aún mejor si tuviera descompresores de datos, imágenes y audio como ejemplos de procesos modelados. En, por ejemplo, la compresión de datos LZ, el modelo supone una máquina (decodificador) que toma como comandos de entrada como (D, L): "copiar a la salida L símbolos contiguos desde el desplazamiento D en relación con la posición de salida actual", o (c): " copie el símbolo c en la posición de salida actual ". El codificador LZ transforma su secuencia de símbolos de entrada en el lenguaje de comandos del decodificador, y la secuencia de símbolos de comandos tiene una entropía (y longitud) diferente a la secuencia codificada. Otros tipos de compresión tienen máquinas diferentes.

piiperi

@piiperi eso suena útil, aunque no conozco ninguno de esos detalles. (

Llego

@senderle Me refería a ampliar el capítulo "Las tasas de entropía dependen del modelo" con algunos ejemplos de procesos concretos. Usted habla de un proceso que genera eventos, y los componentes de procesamiento de los compresores de datos, imágenes, video, audio, etc. pueden verse como tales procesos. Un codificador de entropía puro es el paso final de una tubería de compresión de datos. Ninguno de los pasos de la tubería realmente "reduce la entropía". En cambio, cada uno de ellos crea instrucciones para una máquina que puede reproducir la secuencia de símbolos original. Y cada secuencia de instrucciones tiene una entropía diferente y, a menudo, una longitud diferente (es decir, más corta).

piiperi

12

No, si el algoritmo no tiene pérdidas, ningún paso en la secuencia de compresión puede reducir su entropía; de lo contrario, no podría descomprimirse / decodificarse. Sin embargo, la entropía adicional puede almacenarse en información 'fuera de banda', como la lista que debe mantenerse para decodificar la transformación de mover al frente.

Luke Schwartzkopff
fuente

Entonces, ¿se utilizan los pasos adicionales en los algoritmos de compresión antes de la codificación de entropía para permitir que el codificador de entropía se acerque a la entropía? ¿Un codificador de entropía no se acerca a la entropía por sí solo cuando se aplica a un mensaje arbitrario?

Robert

De hecho, no lo hace (bueno, dependiendo del significado exacto de "cerrar").

Grimmy

Los pasos adicionales permiten que el codificador de entropía mantenga la entropía del mensaje original al tiempo que reduce la información superflua de manera más efectiva que si se aplicara por sí solo. Ya sea que aplique el preprocesamiento o no, se conservará la entropía, pero la compresión sería menos efectiva (terminaría con una codificación menos eficiente).

Luke Schwartzkopff

No, la transformación de mover al frente no genera una lista separada que debe transferirse al decodificador. A menos que se refiera a la lista inicial.

user253751

Aah, tienes razón, ese no fue el mejor ejemplo :)

Luke Schwartzkopff

6

Reducen la aparente entropía inherente a la estructura del mensaje original. O, en otras palabras, sintonizan el mensaje para utilizar las fortalezas de las siguientes etapas de compresión.

Un ejemplo simple sería reemplazar el nombre en las etiquetas finales de xml con un símbolo especial. Puede recrear perfectamente el xml original a partir de eso, pero el compresor no tiene que incluir el nombre completo nuevamente en ese lugar.

Un ejemplo más real es la compresión png. Su compresor de entropía es DEFLATE, que es una combinación de Lempel-Ziff y Huffman. Esto significa que funciona mejor con valores y patrones que se repiten con frecuencia. La mayoría de los píxeles adyacentes tienden a ser de colores similares. Por lo tanto, a cada fila se le asigna un filtro que convierte los valores de píxeles originales en una codificación diferencial. De esta forma, los valores que terminan codificados por DEFLATE son casi cercanos a 0. En el caso extremo, esto convertirá un gradiente suave de todos los valores diferentes en un solo valor a lo largo de la fila de la cual la porción LZ o DEFLATE hace un trabajo muy rápido.

monstruo de trinquete
fuente

¿Eso significa que la entropía aparente es diferente del contenido de información real de un mensaje? ¿Cómo se relaciona eso con la entropía real del mensaje?

Robert

con "entropía aparente" me refiero a la entropía que la codificación de entropía puede comprimir. Diferentes codificadores tendrán diferentes patrones que buscan. Huffman funciona mejor cuando los mismos pocos símbolos se reutilizan a menudo se usan a menudo, lempel-ziff funciona mejor cuando se repiten trozos, etc.

Ratchet Freak

Pero los algoritmos de Lempel-Ziv no son algoritmos de codificación de entropía, ¿verdad? Lo que no entiendo es por qué se usan antes de los codificadores de entropía, por ejemplo, en LZMA, cuando el codificador de entropía por sí solo ya podría supuestamente comprimir el mensaje al mínimo.

Robert

1

@kutschkem ¿Significa esto que la entropía no es una medida absoluta del contenido de información de un mensaje sino que es relativa a lo que se define como un símbolo (por ejemplo, un solo carácter se considera un símbolo frente a 1 bit que se considera un símbolo)? Creo que eso explicaría dónde estaban equivocados mis supuestos.

Robert

1

@robert ... Sin embargo, existe una compensación, que es la información "fuera de banda" que Luke menciona en su respuesta, que generalmente se agrega mediante esos pasos (tablas de búsqueda para poder decodificar la información codificada). Por lo tanto, no tiene sentido definir todo el contenido como un símbolo y codificarlo como 0 porque en algún lugar la información tiene que almacenarse lo que codifica este 0.

kutschkem

6

Los codificadores de entropía no comprimen el mensaje al mínimo número de bits necesarios para representarlo. Sé que es tentador pensar eso, pero no es lo que hacen. No son mágicos y no pueden lograr eso.

En cambio, hacen algo un poco menos mágico, pero aún útil. Supongamos por el momento que supiéramos que cada carácter del mensaje fue elegido independientemente de alguna distribución. Entonces sería posible construir un algoritmo de compresión sin pérdidas que comprima de manera óptima los mensajes. Estos algoritmos se denominan codificadores de entropía.

Ahora los mensajes reales generalmente no tienen esa propiedad de independencia. Por ejemplo, si ve una Q, es probable que la siguiente letra sea una U. Y así sucesivamente. Todavía es posible aplicar un algoritmo de codificador de entropía a un mensaje real, donde cada personaje no se elige independientemente del resto. El algoritmo seguirá sin pérdidas, todavía se puede usar para la compresión y, en la práctica, a menudo acortará la longitud del mensaje. Sin embargo, no lo acorta a la longitud mínima posible. No comprime el mensaje a algo cuya longitud sea igual a la entropía del mensaje; lo comprime menos que eso.

Una vez que se da cuenta de esta propiedad de los codificadores de entropía, la paradoja se evapora.

En general, cualquier paso sin pérdida nunca reduce la entropía del mensaje. Sin embargo, podría poner el mensaje en un formulario donde algún otro algoritmo de compresión sea más efectivo, por lo que aún podría ser útil (en promedio) en la práctica.

DW
fuente

2

La palabra "entropía", si se usa con frecuencia de forma un poco vaga, para referirse a dos cosas diferentes:

La "cantidad total de información" en un mensaje o sistema
La "densidad" de información, o qué tan apretada está la información.

La cita de OP de la entrada de Wikipedia para https://en.wikipedia.org/wiki/Entropy_(information_theory) se refiere a la primera:

Shannon's entropy measures the information contained in a message

Pero (al menos cuando estoy escribiendo esto) el mismo artículo comienza con:

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

Entonces, uno es una cantidad y uno es una tasa (similar a la distancia frente a la velocidad). A veces se denominan propiedades "extensivas" e "intensivas" (consulte https://en.wikipedia.org/wiki/Intensive_and_extensive_properties#Extensive_properties ).

Un ejemplo clásico de la distinción es la famosa señal de linterna de Paul Revere: "una si es por tierra y dos si es por mar". 1 bit de información total (si ignoramos el caso "ninguno si aún no he llegado a North Church"). Si Paul agregara otro juego de linternas en cada ventana del edificio, eso sería '' 'redundante' '': no más información, entonces la misma entropía "total" o "extensa"; pero mucha más longitud del mensaje, una entropía "intensiva" mucho menor.

Si comienza de esa manera pero cambia para usar solo un conjunto de linternas, esa es "compresión sin pérdidas" como en la pregunta de OP. La entropía "extensa" es la misma, pero la "entropía" intensiva es diferente: debido a que la cantidad de linternas en la segunda ventana está altamente correlacionada con la cantidad que has visto en la primera, el mensaje redundante es más predecible, o menos aleatorio, por lo que tiene una entropía intensiva mucho menor.

Hay otras dos cosas importantes para recordar:

Primero, típicamente no conocemos la entropía "verdadera" de un sistema en ningún sentido. Un espectador ingenuo no sabe si "3 linternas" sería un mensaje diferente, o si las señales en diferentes ventanas son redundantes o no. Si Paul hace que su viaje sea un hábito, podemos contar y ver si las ventanas siempre coinciden. Pero tal vez no hemos visto lo suficiente como para ver las raras excepciones (¡y probablemente importantes!).
En segundo lugar, importa cómo mides. Considere tratar de estimar cuánto se comunica por cada letra de texto sucesiva (eso es una tasa, por lo que la entropía "intensiva", a veces también llamada "entropía relativa"):
- Si observa que las personas envían mensajes de texto en unidades de 8 bits, su primer "estimado" podría ser de 8 bits por letra.
- Si cuenta el número de letras distintas que se utilizan, estimaría log2 (26), o 4.7 bits por letra (un poco más si considera espacios, mayúsculas y minúsculas, etc.).
- Si considera que "e" es una mejor apuesta para la "siguiente letra" que "z", medirá las frecuencias de las letras y obtendrá alrededor de 4.14 (consulte http://people.seas.harvard.edu/~jones/cscie129/ papers / stanford_info_paper / entropy_of_english_9.htm ).
- Si cuenta pares de letras, podrá elegir patrones como "qu", "th", etc., y obtendrá alrededor de 3.56.
- Si cuenta secuencias de hasta alrededor de 5 letras, obtendrá valores aún más bajos y, como beneficio adicional, puede distinguir de manera bastante confiable en qué idioma humano se encuentra el texto).
- Si eres tan duro e inteligente como NG Burton y JCR Licklider en "Restricciones de largo alcance en la estructura estadística del inglés impreso" (American Journal of Psychology 68 (1955)), puedes obtener hasta 10 secuencias, 0000 letras seguidas y encuentre otro valor de entropía.

Pero, por supuesto, los mensajes pueden (y tienen) muchos patrones que no están modelados por tales métodos de n-gramas, por lo que la entropía "verdadera" es aún más baja.

Si modela una fuente infinita teórica con una distribución Zipfian de tokens perfectamente aleatoria, puede calcular la entropía extensa e intensiva que tendría, lo que depende solo del número de tokens distintos posibles. Los gráficos de cómo se ve cada tipo de entropía a medida que aumenta ese número se encuentran en [ http://www.derose.net/steve/writings/dissertation/Diss.0.html] . Los dos se comportan de manera bastante diferente:

total (extenso): http://www.derose.net/steve/writings/dissertation/Graph13.png
relativo (intensivo): http://www.derose.net/steve/writings/dissertation/Graph14.png

Espero que ayude o al menos sea interesante ...

TextGeek
fuente

1

Sospecho que la redacción de la Wikipedia alemana está equivocada. Los compresores aumentan la entropía. Es decir, no la entropía general, sino la entropía por bit : la densidad de información. Por ejemplo, se aplica una codificación de longitud de ejecución y un esquema de diccionario para condensar los datos. Ahora la misma información se empaqueta en menos bits, por lo que cada bit lleva más información. La codificación posterior de Huffman hace un poco más de lo mismo; Es solo otra capa de compresión.

Kaz
fuente

¿Los algoritmos de compresión sin pérdida reducen la entropía?

Respuestas:

Procesos de Markov

Las tasas de entropía dependen del modelo