Teoria de la información y las comunicaciones. Etapa de Contextualizatión

TEORIA DE LA INFORMACION Y LAS COMUNICACIONES  Etapa de Contextualization

FUNDACION UNIVERSITARIA COMPENSAR

 Jorge Mario Zambrano Sanchez  

^[1] 

Algoritmo de Huffman.

El algoritmo de Huffman es un método de compresión de datos que se utiliza para reducir el tamaño de los archivos mediante la asignación de códigos de longitud variable a los diferentes caracteres. Este algoritmo fue propuesto por David A. Huffman en 1952 y es ampliamente utilizado en la compresión de archivos, especialmente en la compresión de datos sin pérdida.

El algoritmo consiste en la creación de un árbol binario que tiene cada uno de los símbolos por hoja, y construido de tal forma que siguiéndolo desde la raíz a cada una de sus hojas se obtiene el código Huffman asociado.

1. Se crean varios árboles, uno por cada uno de los símbolos del alfabeto, consistiendo cada uno de los árboles en un nodo sin hijos, y etiquetado cada uno con su símbolo asociado y su frecuencia de aparición.

2. Se toman los dos árboles de menor frecuencia, y se unen creando un nuevo árbol. La etiqueta de la raíz será la suma de las frecuencias de las raíces de los dos árboles que se unen, y cada uno de estos árboles será un hijo del nuevo árbol. También se etiquetan las dos ramas del nuevo árbol: con un 0 la de la izquierda, y con un  la de la derecha.

3. Se repite el paso 2 hasta que sólo quede un árbol.

Con este árbol se puede conocer el código asociado a un símbolo, así como obtener el símbolo asociado a un determinado código.

Funcionamiento del Algoritmo de Huffman:

1. Recopilación de frecuencias:

Se inicia con una fase de análisis del conjunto de datos que se va a comprimir. Se determina la frecuencia de cada símbolo o carácter en los datos.

1. Construcción del árbol de Huffman:

Se crea un nodo para cada símbolo con su frecuencia como valor del nodo.

Los nodos se organizan en una cola de prioridad (o un montículo mínimo) según sus frecuencias

Los nodos se organizan en una cola de prioridad (o un montículo mínimo) según sus frecuencias

Se toman los dos nodos con las frecuencias más bajas y se combinan en un nuevo nodo cuya frecuencia es la suma de las frecuencias originales.

Este proceso se repite hasta que solo queda un nodo en la cola, que se convierte en la raíz del árbol.

Asignación de códigos:

• Se asignan códigos binarios a cada símbolo basándose en el árbol de Huffman.
• Cada vez que se desciende por la rama izquierda, se añade un "0" al código; por cada descenso por la rama derecha, se añade un "1".
• Los códigos resultantes son códigos prefijos, lo que significa que ninguno de ellos es prefijo de otro. Esto es esencial para la decodificación sin ambigüedades.

[pic 1]A.                

Aplicación del Algoritmo de Huffman:

1. Creación de la tabla de códigos:

• Se crea una tabla que asocia cada símbolo con su correspondiente código de Huffman.

1. Reemplazo de símbolos por códigos:

• Se escanea el conjunto de datos original y cada vez que se encuentra un símbolo, se reemplaza por su código de Huffman correspondiente.

1. Generación del archivo comprimido:

• Los códigos de Huffman generados se concatenan para formar una secuencia de bits que representa la versión comprimida del archivo.
• Se debe incluir en el archivo comprimido la información necesaria para la posterior decodificación, como la tabla de códigos y, a veces, la estructura del árbol de Huffman.

[pic 2]

Decodificación:

1. Utilización del árbol de Huffman:

• La información de la tabla de códigos o la estructura del árbol de Huffman se utiliza para decodificar la secuencia de bits comprimida y recuperar los datos originales.

1. Reconstrucción del archivo original:

• Se sigue la ruta a través del árbol de Huffman según la secuencia de bits, y cada vez que se llega a una hoja, se registra el símbolo correspondiente.
• Esto se repite hasta que se ha procesado toda la secuencia de bits, recuperando así los datos originales.

El algoritmo de Huffman se aplica en situaciones donde la compresión de datos es necesaria para reducir el tamaño de archivos o transmisiones de datos, y donde la frecuencia de aparición de los diferentes símbolos no es uniforme. Aquí hay algunos casos comunes en los que se utiliza el algoritmo de Huffman:

El algoritmo de Huffman se aplica en situaciones donde la compresión de datos es necesaria para reducir el tamaño de archivos o transmisiones de datos, y donde la frecuencia de aparición de los diferentes símbolos no es uniforme. Aquí hay algunos casos comunes en los que se utiliza el algoritmo de Huffman:

1. Compresión de archivos de texto:

• Los archivos de texto suelen contener caracteres con frecuencias desiguales. El algoritmo de Huffman puede ser eficiente para comprimir texto, especialmente cuando ciertos caracteres (como espacios o letras comunes) aparecen con mayor frecuencia.

1. Compresión de imágenes:

• En la compresión de imágenes, el algoritmo de Huffman se puede utilizar en combinación con otras técnicas de compresión, como la codificación Run-Length y la transformada discreta del coseno (DCT), para reducir el tamaño de los archivos de imágenes.

1. Compresión de audio:

• En la compresión de archivos de audio, como en el formato MP3, el algoritmo de Huffman se utiliza para comprimir la información de las frecuencias de sonido, contribuyendo así a la reducción del tamaño del archivo.

1. Compresión de archivos ejecutables:

• Los ejecutables de programas también pueden beneficiarse de la compresión mediante el algoritmo de Huffman. Algunos sistemas operativos utilizan técnicas de compresión para reducir el tamaño de los archivos ejecutables y acelerar la carga de programas.

1. Compresión en transmisiones de datos:

• En aplicaciones de transmisión de datos, como la comunicación por redes, el algoritmo de Huffman puede ser utilizado para comprimir datos antes de ser enviados, reduciendo así el ancho de banda necesario para la transmisión.

1. Compresión en almacenamiento de datos:

• En sistemas de almacenamiento, el algoritmo de Huffman puede utilizarse para comprimir datos antes de almacenarlos en dispositivos de almacenamiento, permitiendo un uso más eficiente del espacio en disco.

[pic 3]

Para demostrar cómo funciona el algoritmo de Huffman, primero generaremos un conjunto de secuencias binarias ficticias y luego aplicaremos el algoritmo para comprimirlas. Supongamos que tenemos las siguientes secuencias binarias:

...