Codificacion Huffman

CODIFICACIÓN HUFFMAN

Autores: G. E. Bojacá, C. Cuesta. Miembros USTA

Abstract— In this report examines, in a practical, basic notions on Huffman coding, using fundamental concepts of probability and entropy. For proper simulation of the procedure was used Matlab R2011a, compress the document is saved to a file extension 'txt' from which we obtain the probability of each symbol and its corresponding code. Finally, entropy is calculated, the amount of information bits for each probability weighted path length and Huffman coding result.

KeyWords — Keywords - Huffman Coding, Probability, Entropy, symbol, amount of information.

Resumen— En este informe se analiza, de forma práctica, las nociones fundamentales sobre la codificación Huffman, utilizando para ello conceptos fundamentales de probabilidad como la Entropía. Para realizar una correcta simulación del procedimiento se utilizó el programa Matlab R2011a, el documento a comprimir se encuentra guardado en un archivo de extensión ‘.txt’ a partir del cual se obtienen las probabilidades de cada símbolo y su respectivo código. Finalmente, se calcula la entropía, la cantidad de información en bits para cada probabilidad, la longitud del camino ponderado y el resultado de la codificación Huffman.

Palabras Clave — Codificación Huffman, Probabilidad, Entropía, símbolo, cantidad de información.

I. OBJETIVO GENERAL

 Desarrollar un algoritmo que permita la compresión de un archivo mediante la implementación de la codificación Huffman.

II. OBJETIVOS ESPECÍFICOS

 Adquirir destrezas en el lenguaje de programación, mediante la utilización del programa Matlab R2011a

 Comprender la forma de compresión utilizada por la codificación Huffman.

 Retomar conceptos fundamentales de la probabilidad como la entropía.

 Lograr la compresión de un archivo mediante la implementación de la codificación Huffman.

III. INTRODUCCIÓN

La codificación de Huffman es una técnica para la compresión de datos ampliamente usada y muy efectiva. Este algoritmo le asigna secuencias binarias (códigos) a los símbolos de un alfabeto de forma tal de utilizar la menor cantidad de bits posibles.

La idea del algoritmo de Huffman es que los datos a ser comprimidos contienen símbolos que aparecen con mayor frecuencia y otros que aparecen muy poco, asignándole un código más corto a los que más aparecen dentro de la secuencia [1].

La codificación Huffman es uno de los métodos clásicos de codificación de fuente de la familia de los métodos estadísticos, esto es, aquellos que necesitan conocer la distribución probabilística de la fuente.

El algoritmo básico consiste en, tras ordenar los símbolos de mayor a menor en probabilidad, ir juntando parejas de menor probabilidad formando un árbol. Cuando solamente haya dos raíces, se asigna los símbolos 0 y 1 (o 1 y 0) a cada raíz, y se itera hacia atrás.

Finalmente para conocer el código asociado a cada probabilidad se recorre el árbol en sentido inverso y se concatenan los unos o ceros por los que se va pasando hasta llegar al principio de cada ramificación [2].

IV. MARCO TEÓRICO

Para comprender cómo funciona la compresión mediante la codificación Huffman, se realizara un modelo para ejemplificar su funcionamiento, posteriormente se analizará cómo implementarlo mediante códigos de programación.

Supongamos que en un cierto texto aparecen 6 caracteres diferentes y la frecuencia de aparición de cada uno de ellos es la siguiente:

Figura N.1. Frecuencia de cada símbolo.

Se puede codificar los caracteres para comprimir el espacio ocupado utilizando un código binario de longitud fija (figura N.2) o de longitud variable (figura N.3).

Figura N.2 .Código binario de longitud fija.

Código de longitud variable en el que los más frecuentes tienen el código más corto. Restricción: ningún código es prefijo de otro.

Figura N.3. Código binario de longitud variable

Esta técnica de codificación se denomina código prefijo. Para la codificación de un texto, basta con concatenar el código de cada uno de los caracteres que conforman dicho texto:

aabacd ≡ 0⋅0⋅101⋅0⋅100⋅111≡ 001010100111

La decodificación de un texto cifrado es fácil pues ningún código es prefijo de otro código y por lo tanto no hay ambigüedad.

101011101111011100 ≡ badadcf

Para la aplicación de la codificación Huffman es necesario representar el código prefijo mediante un árbol binario, en donde:

• Las hojas representan los símbolos o los caracteres.

• El camino de la raíz a las hojas con la interpretación 0 a la izquierda y 1 a la derecha nos da el código prefijo

Para el ejemplo anterior, la codificación de longitud variable sería [1]:

Figura N.4. Desarrollo del Árbol binario.

ENTROPÍA DE LA INFORMACIÓN:

La entropía también se puede considerar como la cantidad de información promedio que contienen los símbolos usados.

Los símbolos con menor probabilidad son los que aportan mayor información; por ejemplo, si se considera como sistema de símbolos a las palabras en un texto, palabras frecuentes como "que", "el", "a" aportan poca información, mientras que palabras menos frecuentes como "corren", "niño", "perro" aportan más información.

Si de un texto dado borramos un "que", seguramente no afectará a la comprensión y se sobreentenderá, no siendo así si borramos la palabra "niño" del mismo texto original. Cuando todos los símbolos son igualmente probables (distribución de probabilidad plana), todos aportan información relevante y la entropía es máxima.

La entropía de un mensaje X, denotado por H(X), es el valor medio ponderado de la cantidad de información de los diversos estados del mensaje [3]:

[Ecu.1]

A continuación, en la tabla N.1, se ejemplifica como realizar los cálculos pertinentes a la codificación Huffman:

Tabla N.1 Ejemplo Codificación Huffman

V. METODOLOGÍA

Se Utilizó el programa Matlab R2001a para la simulación de la codificación Huffman. En primera

...