¿Por qué la codificación de Huffman elimina la entropía que Lempel-Ziv no elimina?

13

El popular algoritmo DEFLATE utiliza la codificación Huffman sobre Lempel-Ziv.

En general, si tenemos una fuente de datos aleatoria (= entropía de 1 bit / bit) , es probable que ninguna codificación, incluida Huffman, la comprima en promedio. Si Lempel-Ziv fuera "perfecto" (que se acerca a la mayoría de las clases de fuentes, ya que la longitud llega al infinito), la codificación de publicaciones con Huffman no ayudaría. Por supuesto, Lempel-Ziv no es perfecto, al menos con una longitud finita, por lo que queda algo de redundancia.

Es esta redundancia restante la que la codificación Huffman elimina parcialmente y, por lo tanto, mejora la compresión.

Mi pregunta es: ¿por qué esta redundancia restante se elimina con éxito mediante la codificación de Huffman y no con LZ? ¿Qué propiedades de Huffman versus LZ hacen que esto suceda? ¿Simplemente ejecutar LZ nuevamente (es decir, codificar los datos comprimidos de LZ con LZ por segunda vez) lograría algo similar? ¿Si no, porque no? Del mismo modo, primero comprimir con Huffman y luego con LZ funcionaría, y si no, ¿por qué?

ACTUALIZACIÓN: está claro que incluso después de LZ, quedará algo de redundancia. Varias personas han hecho ese punto. Lo que no está claro es: ¿por qué Huffman aborda mejor esa redundancia restante que LZ? ¿Qué tiene de especial en contraste con la fuente original de redundancia, donde LZ funciona mejor que Huffman?

ds.algorithms it.information-theory coding-theory encoding SRobertJames
fuente

Respuestas:

13

Originalmente fue un comentario, pero se hizo demasiado largo.

Si observa DEFLATE, lo que está siendo comprimido por Huffman es la salida de LZ77; LZ77 funciona (cuando esto toma menos bits que los datos sin procesar) enviando un puntero antes a la cadena que se está comprimiendo, y una longitud de coincidencia que indica cuántos símbolos tomar después del puntero. La teoría muestra que, incluso sin compresión adicional, esta técnica finalmente converge a la entropía fuente. Sin embargo, en la compresión de datos, cada vez que tenga una distribución que no sea completamente aleatoria, también podría comprimirla. No hay razón para creer que la salida de LZ77, los punteros y las longitudes de coincidencia, sean completamente aleatorios. Deben converger para completar la aleatoriedad en el límite asintótico, ya que LZ77 es asintóticamente óptimo, pero en la práctica solo usa un diccionario finito, por lo que presumiblemente se mantienen lo suficientemente lejos de ser completamente aleatorios para que ganes al hacer una mayor compresión sobre ellos. Naturalmente, utiliza un código Huffman para los punteros y otro para las duraciones de las coincidencias, ya que estos dos procesos tienen estadísticas diferentes.

¿Por qué usar Huffman en lugar de LZ para la segunda ronda de compresión? La gran ventaja que LZ tiene sobre Huffman es en el tratamiento de dependencias entre símbolos. En inglés, si una letra es una 'q', es muy probable que la siguiente sea una 'u', y así sucesivamente. Si los símbolos son eventos independientes, Huffman es más simple y funciona igual o mejor para cadenas cortas. Para la salida de LZ77, mi intuición es que los símbolos deberían ser bastante independientes, por lo que Huffman debería funcionar mejor.

Peter Shor
fuente
Estoy contigo en tu primer párrafo: LZ todavía deja algo de redundancia para comprimir aún más. Pero su segundo párrafo todavía parece estar saltando, si no agitando la mano. Hay dos afirmaciones: 1. La redundancia que queda después de que LZ es de orden cero (es decir, p (X_n) es aproximadamente independiente de x_n-1; estoy usando el término orden cero como en el modelo de orden cero, p. Ej. data-compression.com/theory.shtml ) y 2. En redundancia de orden cero, Huffman funciona mejor que LZ; En redundancia de orden superior, LZ funciona mejor. Quizás estas afirmaciones son ciertas, pero tampoco lo has justificado
SRobertJames
2
@Robert: Las correlaciones de orden superior no tienen ningún efecto en la codificación de Huffman. LZ funciona de manera asintótica óptima para redundancia de orden superior, pero la sobrecarga adicional requerida significa que no funciona tan bien en fuentes de orden cero de longitud finita. Esto debe haber sido estudiado experimentalmente en la literatura en alguna parte; tal vez alguien más pueda dar un puntero a una referencia. Para el punto 1, mi intuición es que cualquier redundancia de orden superior que quede después de LZ es demasiado complicada para ser utilizada en cualquier esquema de codificación simple, pero no tengo una buena manera de justificar esto.
Peter Shor
10

La compresión de datos se trata realmente de dos cosas: modelado y codificación. Los algoritmos de la familia LZ modelan el texto como una concatenación de repeticiones exactas, que es asintóticamente óptimo para muchas fuentes aleatorias y razonablemente bueno para muchos textos reales. Sin embargo, para algunas entradas, este modelo puede ser bastante malo. Por ejemplo, no puede usar LZ para comprimir una matriz de sufijos directamente, aunque la matriz de sufijos sea tan comprimible como el texto original.

(pag,ℓ,C)pagℓC

Iniciar sesión⁡nortenorte

En resumen, Huffman supera a LZ al comprimir las tuplas, ya que su modelo (distribución fija frente a repeticiones exactas) es una mejor coincidencia para los datos.

Jouni Sirén
fuente
Gracias Jouni. Parece que la redundancia principal que queda es que las repeticiones son generalmente más pequeñas que grandes (no distribuidas uniformemente en [0,2 ^ n]). Huffman funciona bien en esta asimetría de orden cero, mientras que LZ realmente necesita características más grandes para funcionar bien. ¿Es eso correcto? ¿Y por qué no usar Huffman para empezar? ¿Por qué molestarse con LZ?
SRobertJames
3
Si comprimimos el texto directamente con Huffman, no podemos obtener una mejor compresión que la entropía de orden cero. Sin embargo, la mayoría de los textos reales tienen importantes fuentes de redundancia que no pueden modelarse adecuadamente con entropía de orden cero. En muchos casos, usar LZ antes de Huffman nos permite comprimir esta redundancia.
Jouni Sirén
2

Creo que la respuesta se encuentra en el tamaño del diccionario de búsqueda.

Los datos tienen un sentido de localidad (es decir, si se ha usado un dato, es probable que se vuelva a usar pronto), y el algoritmo LZ aprovecha esto en la construcción del diccionario de búsqueda. Genera un trie con una cantidad finita de nodos posibles, para mantener las búsquedas rápidas . Cuando alcanza el límite de tamaño, hace otro trie, "olvidando" el anterior. Por lo tanto, debe crear nuevamente la tabla de búsqueda para los caracteres más simples, pero si algunas palabras ya no se usan, ya no se conservan en la memoria, por lo que se puede usar una codificación más pequeña.

Por lo tanto, una salida LZ se puede reducir aún más con la codificación Huffman, ya que esta redundancia en la creación de los intentos de búsqueda se puede detectar mediante análisis estadístico.

Manuel Ferreria
fuente
Acepto el primer párrafo: usted explica por qué LZ deja la redundancia. Pero el segundo párrafo parece ser un gran salto: ¿por qué Huffman capta esta redundancia? ¿Por qué no LZ otra vez? Y, si Huffman es más completo, ¿por qué no solo para empezar?
SRobertJames
2

Tal vez estoy fuera de pista aquí, pero la codificación de Huffman mira toda la entrada para construir su tabla de codificación (árbol), mientras que Lempel-Ziv codifica a medida que avanza. Esto es tanto una ventaja como una desventaja para Huffman. La desventaja es obvia, es decir, tenemos que ver toda la información antes de poder comenzar. La ventaja es que Huffman tendrá en cuenta las estadísticas que se producen en cualquier parte de la entrada, mientras que Lempel-Ziv tiene que ir acumulando progresivamente. O para decirlo de otra manera, Lempel-Ziv tiene una "dirección" que Huffman no tiene.

Pero todo esto es solo mi ingenua manera de imaginar cómo son las cosas. Necesitaríamos una prueba real aquí para ver cómo exactamente Huffman supera a Lempel-Ziv.

Andrej Bauer
fuente
2
La gente ha definido la codificación adaptativa de Huffman, que solo mira la entrada una vez. Para los propósitos de esta discusión, la codificación adaptativa y no adaptativa de Huffman se comportará de manera bastante similar.
Peter Shor
2

La respuesta corta es que LZ es un algoritmo "universal" en el sentido de que no necesita conocer la distribución exacta de la fuente (solo necesita suponer que la fuente es estacionaria y ergódica). Pero Huffman no lo es; necesita saber la distribución exacta a partir de la cual se muestrea la fuente (para hacer el árbol Huffman). Esta información adicional hace que Huffman obtenga garantías de compresión ajustadas. Sin embargo, para los algoritmos prácticos de compresión de archivos, Huffman puede ser menos favorable, ya que primero tendrá que recopilar estadísticas empíricas del archivo y luego hacer la compresión real en una segunda mitad, mientras que LZ se puede implementar en línea.

Se pueden encontrar más detalles en los textos estándar de teoría de la información, por ejemplo, Elementos de la teoría de la información de Cover y Thomas.

MCH
fuente
Creo que la fuente ergódica estacionaria es solo una suposición que hace que LZ sea más fácil de analizar. Después de todo, la compresión se basa en las propiedades combinatorias de la entrada, que en muchos casos coinciden muy bien con las propiedades estadísticas. Considere, por ejemplo, una colección de textos en inglés en formato de texto plano, seguido de los mismos textos en formato HTML. LZ comprime esta colección bastante bien, a pesar de que no parece algo generado por una fuente ergódica estacionaria.
Jouni Sirén
@Jouni: No estaría de acuerdo con este comentario; Creo que, en cierto sentido, el idioma inglés en texto plano se parece mucho a una fuente ergódica estacionaria, y esta semejanza es exactamente de lo que LZ se está aprovechando.
Peter Shor
@ Peter: Pero en este caso, la fuente primero genera algunos textos en formato de texto plano y luego exactamente los mismos textos en formato HTML. Este cambio de texto plano a HTML en algún punto arbitrario parece romper la propiedad estacionaria ergódica. Por otro lado, los resultados de compresión son mucho mejores que al comprimir los textos sin formato y los textos HTML por separado, ya que hay mucha información mutua entre un texto en formato de texto sin formato y el mismo texto en formato HTML.
Jouni Sirén