algorithm - ejemplo - ¿Cuáles son las aplicaciones reales de la codificación huffman?
huffman algorithm (5)
Me dicen que la codificación de Huffman se usa como algoritmo de compresión de datos sin pérdida , pero también se me dice que el software de compresión de datos reales no emplea la codificación de Huffman, porque si las claves no se distribuyen lo suficientemente descentralizadas, el archivo comprimido podría ser incluso más grande que el original expediente.
Esto me deja preguntándome: ¿hay alguna aplicación en el mundo real de la codificación de Huffman?
Cuando uno considera los algoritmos de compresión, a menudo hay beneficios y desventajas para cada uno. Es la naturaleza de la compresión que, dado un conjunto de entradas, existen algoritmos de compresión mejores y peores para esos datos.
Huffman es realmente bueno en algunas cosas. Lo más notable es que los datos que se repiten ordenan mucho 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 de las mismas otras letras.
Si su profesor o libro le dio la impresión de que Huffman no se usa, se equivocan. Por ejemplo, casi todas las comunicaciones con y desde Internet están en algún punto codificadas por Huffman. (Una serie de protocolos de comunicación lo utilizan.) La mayoría de los archivos de imagen (jpegs) están codificados en Huffman. La mayoría de los archivos de música (mp3) están codificados en Huffman. Hay muchos otros ejemplos.
Una de las razones por las que se usa Huffman es porque se puede "descubrir" mediante un algoritmo ligeramente diferente llamado Huffman adaptativo. A medida que lee el archivo, aprende el código de Huffman y "comprime mientras avanza". Este es un resumen simplificado, pero entiendes la idea.
Para resolver el uso del mejor algoritmo para el problema de la situación, los archivos zip permiten el uso de varias compresiones diferentes en función de cuál es la mejor para un archivo determinado.
El código de Huffman se usa para convertir códigos de longitud fija en códigos de longitud variable, lo que resulta en una compresión sin pérdidas. Los códigos de longitud variable pueden comprimirse aún más utilizando técnicas JPEG y MPEG para obtener la relación de compresión deseada.
Hay muchas aplicaciones reales de Huffman Encoding. ZIP es quizás la herramienta de compresión más utilizada que utiliza la codificación Huffman como base. El último de los algoritmos de compresión sin pérdida más eficientes, Brotli Compression, lanzado por Google el mes pasado, también utiliza la codificación Huffman. Aparte de eso, Brotli también usa LZ77 y algunos otros algoritmos de compresión sin pérdida fundamentales. Consulte a Brotli.
Huffman se usa ampliamente en todos los formatos de compresión principales que puede encontrar, desde GZIP, PKZIP (winzip, etc.) y BZIP2, hasta formatos de imagen como JPEG y PNG.
Todos los esquemas de compresión tienen conjuntos de datos patológicos que no pueden comprimirse de manera significativa; Los formatos de archivo que enumeré anteriormente simplemente "almacenan" dichos archivos sin comprimir cuando se encuentran.
Los esquemas aritméticos y de codificación de rango más nuevos a menudo se evitan debido a problemas de patentes , lo que significa que Huffman sigue siendo el caballo de batalla de la industria de la compresión.
Ver artículo de Wikipedia sobre el tema:
La codificación de Huffman en la actualidad se usa a menudo como un "back-end" para algún otro método de compresión. DEFLATE (el algoritmo de PKZIP) y los códecs multimedia como JPEG y MP3 tienen un modelo de front-end y cuantificación seguidos de la codificación de Huffman.