El algoritmo de Huffman se usa para la compresión o encriptación de datos mediante el estudio de la frecuencia de aparición de caracteres. Fue desarrollado por el norteamericano David Albert Huffman en 1952 mientras hacía el doctorado en el MIT. El método fue publicado en una revista como A Method for the Construction of Minimum-Redundancy Codes (el artículo original). El algoritmo funciona a partir de un conjunto dado de símbolos con sus respectivos pesos. Los pesos son la frecuencia de aparición en una cadena. Por ejemplo en la cadena Genciencia el peso del símbolo i es 2, ya que aparece en dos ocasiones. La salida del algoritmo es el mismo conjunto de símbolos de entrada codificado mediante un código binario con un tamaño menor. La descripción matemática del algoritmo de Huffman es la siguiente:
Entrada
-
Conjunto de Símbolos:
-
Pesos asociados:
Donde n es la cantidad de símbolos diferentes que existe en la cadena de entrada. Así pues los pesos asociados a los símbolos pertenecientes al conjunto A se encuentran en un rango comprendido entre 1 y n (entendiendo que la entrada no va a ser una cadena vacía), es decir:
Salida
-
Conjunto de código binarios:
Meta
-
Conseguir que el peso de C sea menor que el de A:
El algoritmo se basa en el uso de un árbol binario dónde las hojas representan los símbolos del conjunto de entrada. Para conseguir el código de Huffman asociado a cada símbolo únicamente hay que seguir las aristas que unen la raíz con la hoja determinada. Vamos a comprimir la cadena de ejemplo: pablito clavo un clavito.
-
Primero calculamos los pesos de los símbolos (¡ojo!, los espacios en blanco también cuentan) y los disponemos siguiente una ordenación ascendente por frecuencia p(1)->b(1)->u(1)->n(1)->i(2)->t(2)->c(2)->v(2)->' '(3)->a(3)->l(3)->o(3)
-
En el paso anterior obtenemos n árboles. Ahora fusionamos los dos primeros árboles sumando sus frecuencias y volviendo a ordenar
-
Seguimos agrupando pares de árboles hasta obtener solamente uno. La raíz del árbol resultante debe de ser la suma de los pesos
-
Ahora a partir de nuestro árbol obtendremos la codificación de Huffman para nuestra cadena. La regla que hay que seguir es la siguiente: Cuando nos encontremos en un nodo las ramas a la izquierda valen ceros y a la derecha valen unos. Para nuestra cadena las correspondencias quedarían de la siguiente manera:
-
Traducimos la cadena de entrada con nuestras correspondencias y agrupamos en grupos de 8 bits (bytes) la cadena binaria resultante
En la cadena resultante se ha reducido la cantidad de bytes respecto a la cadena original que tenía 24 bytes. Cabe decir que también hay que almacenar información de la codificación, pues para descomprimir los datos hay que conocer las correspondencias ya que es relativo. Por esta razón para ficheros de poco tamaño la compresión no es muy grande, aunque esta afirmación es muy relativa, ya que el porcentaje de compresión depende de la entrada.
Ver 8 comentarios