¿Cuáles son las aplicaciones del mundo real de la codificación huffman?

Question

Me han dicho que la codificación Huffman se utiliza como algoritmo de compresión de datos sin pérdidas, pero también me han dicho que los datos reales comprimen software de hacer no codificación de Huffman empleo, ya que si las claves no se distribuyen bastante descentralizado, el archivo comprimido podría ser aún más grande que el archivo original.

Esto me deja preguntándome si hay alguna aplicación en el mundo real de la codificación Huffman?

Answer 1

Huffman es ampliamente utilizado en todos los principales formatos de compresión que puede encontrar - a partir GZIP, PKZIP (WinZip, etc.) y BZIP2, a formatos de imagen como JPEG y PNG.

Todos los esquemas de compresión tienen conjuntos de datos patológicos que no se pueden comprimir significativamente; los formatos de archivo que acabo de enumerar simplemente 'almacenan' dichos archivos sin comprimir cuando se encuentran.

Más a menudo se evitan los esquemas arithmetic and range coding debido a patent issues, lo que significa que Huffman sigue siendo el caballo de batalla de la industria de la compresión.

Answer 2

Ver Wikipedia artículo sobre el tema:

codificación Huffman hoy se utiliza a menudo como un "back-end" a algún otro método de compresión. DEFLATE (algoritmo de PKZIP) y códecs multimedia como JPEG y MP3 tienen un modelo de front-end y cuantificación seguido de codificación Huffman.

Answer 3

Cuando se consideran los algoritmos de compresión, a menudo hay ventajas y desventajas para cada uno. Es la naturaleza de la compresión que, dado un conjunto de datos de entrada, existen mejores y peores algoritmos de compresión para esos datos.

Huffman es muy, muy bueno en algunas cosas. Lo más notable es que los datos repiten orden y contienen un subconjunto del espacio de caracteres. Por ejemplo, archivos de texto en inglés. El idioma inglés tiende a tener las mismas letras seguidas por las mismas otras letras.

Si su profesor o libro le dio la impresión de que Huffman no se usa, están equivocados. Por ejemplo, casi todas las comunicaciones con y desde Internet están en algún punto codificadas por Huffman. (Varios protocolos de comunicación lo usan). La mayoría de los archivos de imagen (jpegs) están codificados por Huffman. La mayoría de los archivos de música (mp3) están codificados por Huffman. Hay muchos otros ejemplos.

Una razón por la que se usa Huffman es porque se puede "descubrir" a través de un algoritmo ligeramente diferente llamado Huffman adaptativo. Mientras lee el archivo, aprende el código de Huffman y "comprime sobre la marcha". Esta es una descripción general simplificada, pero entiendes la idea.

Para resolver el uso del mejor algoritmo para el problema de la situación, los archivos zip permiten que se usen diferentes compresiones según cuál sea la mejor para un archivo determinado.

Answer 4

El código de Huffman se utiliza para convertir códigos de longitud fija en códigos de longitud variable, lo que da como resultado una compresión sin pérdida. Los códigos de longitud variable se pueden comprimir aún más utilizando las técnicas JPEG y MPEG para obtener la relación de compresión deseada.

Answer 5

Hay un montón de aplicaciones reales de Huffman Encoding. ZIP es quizás la herramienta de compresión más utilizada que utiliza Huffman Encoding como base. El último de los algoritmos de compresión sin pérdidas más eficientes, Brotli Compression, lanzado por Google el mes pasado también utiliza Huffman Coding.Aparte de eso, Brotli también usa LZ77 y algunos otros algoritmos de compresión sin pérdida fundamentales. Consulte Brotli.