Lectura 4 - Aplicaciones

Módulo 4
Lectura 4
Unidad 4: Aplicaciones
Taller de Algoritmos y Estructuras de Datos II

Paula Abruzzini / Nicolas Frontini
4.1- Compresión de archivos
Introducción
La compresión de datos es una técnica muy importante en Computación; se
emplea para reducir el tamaño de los archivos guardados en disco.
El código ASCII (acrónimo inglés de American Standard Code for

Information Interchange — Código Estándar Estadounidense para el
Intercambio de Información) es un código de caracteres basado en el
alfabeto latino creado para el intercambio de información.
“Para distinguir estos caracteres se necesitan [log 100]=7 bits. Siete bits
permiten la representación de 128 caracteres, de modo que el conjunto de
caracteres ASCII contiene además algunos caracteres no imprimibles. Se
añade un octavo bit para poder realizar tests de paridad.” 1
Es decir, necesitamos 8 bits para poder representar todos los caracteres

ASCII en una codificación de longitud fija.
1
Mark Allen Weiss, “Estructuras de Datos en Java”, Adisson Weisley - 2000 - S/D - Bs As
Materia – Profesor | 2
Supongamos que tenemos un fichero que contiene sólo caracteres a, e, s, t,
además de espacios en blanco (sp) y caracteres de nueva línea (nl).
Supongamos que la frecuencia de cada carácter es 10, 15, 12 3, 4, 13 y 1,
respectivamente, como se muestra en la siguiente tabla:
Este archivo debería ocupar 174 bits, ya que contiene 58 caracteres y en este
contexto, cada carácter necesitaría sólo 3 bits para ser representado.
Por lo general, los archivos son de gran tamaño y existe una gran disparidad
entre el número de apariciones de los caracteres más frecuentes y los menos
frecuentes. Por ejemplo, muchos archivos de datos de gran tamaño tienen
una enorme cantidad de dígitos en blanco y caracteres de nueva línea
mientras que tienen muy pocos dígitos como q o x. Una forma de
comprimir archivos es reducir la cantidad de bits para la representación de
los datos. Para esto, es necesario codificar (comprimir) y decodificar
(descomprimir).
La estrategia más común es permitir que la longitud de la codificación

cambie de carácter a carácter, generando que los caracteres más frecuentes
tengan códigos más cortos. Si todos los caracteres aparecen con la misma
frecuencia, esta estrategia no tendría sentido.
Para poder tener un código de longitud variable, es necesario cumplir con la

condición del prefijo. Un código prefijo es un código, típicamente un código
de longitud variable, con la "propiedad de prefijo": ninguna palabra de
código es prefijo de cualquier otra palabra de código del conjunto. Un
código con las palabras de código {0, 10, 11} tiene la propiedad de prefijo;
un código {0, 1, 10, 11} no la tiene, porque "1" es prefijo de tanto "10" como
"11".
4.2- Algoritmo de Huffman
Contexto
Huffman fue capaz de diseñar el método de compresión más
eficiente.
La codificación Huffman es un algoritmo aplicado para compresión de

datos. El término se refiere al uso de una tabla de códigos de longitud
variable para codificar un determinado símbolo (como puede ser un
carácter en un archivo), donde la tabla ha sido rellenada de una manera
específica basándose en la probabilidad estimada de aparición de cada
posible valor de dicho símbolo. Fue desarrollado por David A. Huffman
mientras era estudiante de doctorado en el MIT, y publicado en "A Method
for the Construction of Minimum-Redundancy Codes".2
La codificación Huffman utiliza un método específico para elegir la

representación de cada símbolo, que da lugar a un código prefijo (es decir,
la cadena de bits que representa a un símbolo en particular nunca es prefijo
de la cadena de bits de un símbolo distinto) que representa los caracteres
más comunes utilizando las cadenas de bits más cortas, y viceversa.
Huffman fue capaz de diseñar el método de compresión más eficiente de
este tipo: ninguna representación alternativa de un conjunto de símbolos de
entrada produce una salida media más pequeña cuando las frecuencias de
los símbolos coinciden con las usadas para crear el código. Posteriormente
se encontró un método para llevar esto a cabo en un tiempo lineal si las
probabilidades de los símbolos de entrada (también conocidas como
"pesos") están ordenadas.
Para un grupo de símbolos con una distribución de probabilidad uniforme y

un número de miembros que es potencia de dos, la codificación Huffman es
equivalente a una codificación en bloque binaria, por ejemplo, la
codificación ASCII vista anteriormente. La codificación Huffman es un
método para crear códigos prefijo tan extendido que el término
"codificación Huffman" es ampliamente usado como sinónimo de "código
prefijo", incluso cuando dicho código no se ha producido con el algoritmo
de Huffman.
La siguiente figura muestra el árbol de Huffman generado para las

frecuencias de apariciones exactas del texto "Esto es un ejemplo de árbol de
Huffman".
2
A Method for the Construction of Minimum-Redundancy Codes, DAVID A. HUFFMAN,
ASSOCIATE, IRE
http://compression.ru/download/articles/huff/huffman_1952_minimum-redundancy-codes.pdf
Fuente: Pagina web http://es.wikipedia.org/wiki/Codificaci%C3%B3n_Huffman
Codificar esta frase usando este código requiere 156 bits, sin contar con el
espacio para el árbol.
Las frecuencias y códigos de cada carácter se muestran en la siguiente

figura:
Fuente: Pagina web http://es.wikipedia.org/wiki/Codificaci%C3%B3n_Huffman
4.3- Implementación
Codificación
El objetivo es representar símbolos con la menor cantidad de bits.
Para poder llegar a la tabla de códigos en donde los caracteres más

frecuentemente usados se representan con menor cantidad de bits, lo
primero que tenemos hacer es calcular la frecuencia de cada carácter.
Suponemos que los caracteres están en un archivo de texto para poder
generar un arreglo de frecuencias:
El método getFrecuencias crea un arreglo con todos los caracteres

disponibles, utilizando la posición del arreglo para representarlos (en
decimal, por ejemplo, ‘a’ es 97, ‘b’ es 98, etc.). Luego, se recorre el archivo
carácter por carácter para ir incrementando la frecuencia en cada posición
del arreglo.
Luego de calcular la frecuencia, necesitamos construir el árbol de Huffman.

Para esto, creamos el método construirArbol que utiliza una fila de
prioridades del tipo NodoBinario. Para que la fila de prioridades quede
ordenada por frecuencia en el momento de insertar un elemento en la fila,
debemos realizar una modificación en la clase NodoBinario para que
implemente Comparable:
A su vez, también debemos realizar algunas modificaciones en la clase Dato
para poder persistir el símbolo (carácter) la su frecuencia.
Una vez actualizado el NodoBinario y el Dato, podemos crear los nodos y

agregarlos a la fila de prioridad (por frecuencia, como indica el método
compareTo). Luego, se recorre la lista y se arma el árbol relacionando el
hijo izquierdo y el hijo derecho en cada nodo como se muestra en la
siguiente figura:
Una vez creado el árbol de Huffman, estamos en condiciones de recorrerlo

para poder armar la tabla de codificación:
Combinando todos los métodos mencionados anteriormente, obtenemos
como resultado la tabla de codificación Huffman:
Si el archivo datos.txt contiene este texto: “ESTO ES UN EJEMPLO DE

ÁRBOL DE HUFFMAN”, los símbolos quedarían representados de la
siguiente manera:
Una vez creada la tabla, resultan necesarios los métodos para codificar
(comprimir) y decodificar (descomprimir):
Finalmente, los métodos codificar y decodificar se utilizan de la siguiente
manera:
Bibliografía Lectura
Mark Allen Weiss, “Estructuras de Datos en Java”, Adisson Weisley - 2000 -
S/D - Bs As
T. Cormen, C. Leiserson, R. Rivest, C.Stein, “Introduction to Algorithms,

2nd Edition.” McGraw Hill. 2002. Sun Press, Core Java Vol. 1 Fundamentals (a
proveer por la cátedra) Sun, Java 1.5 API Especification (a proveer por la cátedra)
O"Reilly, Eclipse y Eclipse Cookbook (a proveer por la cátedra)
www.uesiglo21.edu.ar

Lectura 4 - Aplicaciones

Cargado por

Copyright:

Formatos disponibles

Lectura 4 - Aplicaciones

Cargado por

Información del documento

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Lectura 4 - Aplicaciones

Cargado por

Copyright:

Formatos disponibles

Módulo 4

Taller de Algoritmos y Estructuras de Datos II

El código ASCII (acrónimo inglés de American Standard Code for

Es decir, necesitamos 8 bits para poder representar todos los caracteres

La estrategia más común es permitir que la longitud de la codificación

Para poder tener un código de longitud variable, es necesario cumplir con la

La codificación Huffman es un algoritmo aplicado para compresión de

La codificación Huffman utiliza un método específico para elegir la

Para un grupo de símbolos con una distribución de probabilidad uniforme y

La siguiente figura muestra el árbol de Huffman generado para las

Las frecuencias y códigos de cada carácter se muestran en la siguiente

Fuente: Pagina web http://es.wikipedia.org/wiki/Codificaci%C3%B3n_Huffman

Para poder llegar a la tabla de códigos en donde los caracteres más

El método getFrecuencias crea un arreglo con todos los caracteres

Luego de calcular la frecuencia, necesitamos construir el árbol de Huffman.

Una vez actualizado el NodoBinario y el Dato, podemos crear los nodos y

Una vez creado el árbol de Huffman, estamos en condiciones de recorrerlo

Si el archivo datos.txt contiene este texto: “ESTO ES UN EJEMPLO DE

T. Cormen, C. Leiserson, R. Rivest, C.Stein, “Introduction to Algorithms,

También podría gustarte