• Author / Uploaded
• TURATURA

Citation preview

´ DE UN CODEC ˜ Y PROGRAMACION DISENO HUFFMAN Cristian Aguirre Esparza [email protected] Edwin Castillo [email protected]

Abstract—A medida que la necesidad de los usuarios de enviar y recibir informaci´on cada ves es mas extensa, surgio la necesidad de comprimir dicha informaci´on de tal manera que esta sea posible enviarla y recibirla sin ocasionar perdidas pero a su ves en un numero menor de datos, de esta manera facilitar en mucho las comunicaciones. En base a esto la practica a desarrollarse, ˜ es el de disenar y programar un c´odigo HUFFMAN ya sea para audio, video o texto, y utilizando otro c´odigo sin perdidas comprobar el funcionamiento del c´odigo HUFFMAN. En nuestro caso hemos elejido texto, ya que consideramos que de los tres campos, con texto se nos facilitaria ver y entender la operaci´on y el funcionamiento del c´odigo, que es el objetivo de esta pr´actica. Keywords—Comprensi´on, matlab, texto, huffman, RLZ.

´ I. INTRODUCCION

E

N ciencias de la computaci´on y teor´ıa de la informaci´on, la codificaci´on Huffman es un algoritmo usado para compresi´on de datos. El t´ermino se refiere al uso de una tabla de c´odigos de longitud variable para codificar un determinado s´ımbolo (como puede ser un caracter en un archivo), donde la tabla ha sido rellenada de una manera espec´ıfica bas´andose en la probabilidad estimada de aparici´on 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”. Para poder utilizar el algoritmo de Huffman es necesario conocer de antemano las frecuencias de aparici´on de cada s´ımbolo, y su eficiencia depende de lo pr´oximas a las frecuencias reales que sean las estimadas. Algunas implementaciones del algoritmo de Huffman son adaptativas, actualizando las frecuencias de cada s´ımbolo conforme recorre el texto. [1]

II. OBJETIVOS 1) 2) 3) 4)

Dise˜nar un codec Huffman en base a la teor´ıa revisada. Programar el codec Huffman. Realizar pruebas de funcionamiento del codec. Validar el codec Huffman (comparar con otro codec de compresi´on con/sin p´erdidas).

´ III. MARCO TEORICO ´ DE DATOS (TEXTO) A. COMPRESION La compresi´on es un caso particular de la codificaci´on, cuya caracter´ıstica principal es que el c´odigo resultante tiene menor tama˜no que el original. En otras palabras la compresi´on de datos es la reducci´on del volumen de datos tratables para representar una determinada informaci´on empleando una menor cantidad de espacio. La compresi´on se basa fundamentalmente en buscar repeticiones en series de datos para despu´es almacenar solo el dato junto al n´umero de veces que se repite. As´ı, por ejemplo, si en un fichero aparece una secuencia como “AAAAAA”, ocupando 6 bytes se podr´ıa almacenar simplemente ”6A” que ocupa solo 2 bytes. En realidad, el proceso es mucho m´as complejo, ya que raramente se consigue encontrar patrones de repetici´on tan exactos (salvo en algunas im´agenes). Se utilizan algoritmos de compresi´on. Por un lado, algunos buscan series largas que luego codifican en formas m´as breves, por otro lado, algunos algoritmos, como el algoritmo de Huffman que es el que se utilizara en esta pr´actica, examinan los caracteres m´as repetidos para luego codificar de forma m´as corta los que m´as se repiten. Otros, como el LZW, construyen un diccionario con los patrones encontrados, a los cuales se hace referencia de manera posterior, y por ultimo, la compresi´on RLE o Run-length encoding es una forma muy simple de compresi´on de datos en la que secuencias de datos con el mismo valor consecutivas son almacenadas como un u´ nico valor m´as su recuento. ´ HUFFMAN ´ B. TECNICA DE CODIFICACION La codificaci´on Huffman usa un m´etodo espec´ıfico para elegir la representaci´on de cada s´ımbolo, que da lugar a un c´odigo 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´as comunes usando las cadenas de bits m´as cortas, y viceversa. Huffman fue capaz de dise˜nar el m´etodo de compresi´on m´as eficiente de este tipo: ninguna representaci´on alternativa de un conjunto de s´ımbolos de entrada produce una salida media m´as peque˜na cuando las frecuencias de los s´ımbolos coinciden

con las usadas para crear el c´odigo. Posteriormente se encontr´o un m´etodo para llevar esto a cabo en un tiempo lineal si las probabilidades de los s´ımbolos de entrada (tambi´en conocidas como “pesos”) est´an ordenadas. El codificador Huffman crea una estructura arb´orea ordenada con todos los s´ımbolos y la frecuencia con que aparecen. Las ramas se construyen en forma recursiva comenzando con los s´ımbolos menos frecuentes. Para un grupo de s´ımbolos con una distribuci´on de probabilidad uniforme y un n´umero de miembros que es potencia de dos, la codificaci´on Huffman es equivalente a una codificaci´on en bloque binaria, por ejemplo, la codificaci´on ASCII. La codificaci´on Huffman es un m´etodo para crear c´odigos prefijo tan extendido que el t´ermino “codificaci´on Huffman” es ampliamente usado como sin´onimo de “c´odigo prefijo”, incluso cuando dicho c´odigo no se ha producido con el algoritmo de Huffman. Aunque la codificaci´on de Huffman es o´ ptima para una codificaci´on s´ımbolo a s´ımbolo dada una distribuci´on de probabilidad, su optimalidad a veces puede verse accidentalmente exagerada. Por ejemplo, la codificaci´on aritm´etica y la codificaci´on LZW normalmente ofrecen mayor capacidad de compresi´on. Estos dos m´etodos pueden agrupar un n´umero arbitrario de s´ımbolos para una codificaci´on m´as eficiente, y en general se adaptan a las estad´ısticas de entrada reales. Este u´ ltimo es u´ til cuando las probabilidades no se conocen de forma precisa o var´ıan significativamente dentro del flujo de datos. ´ RLE ´ C. TECNICA DE CODIFICACION La compresi´on RLE o Run-length encoding es una forma muy simple de compresi’on de datos en la que secuencias de datos con el mismo valor consecutivas son almacenadas como un u´ nico valor m´as su recuento. Esto es m´as u´ til en datos que contienen muchas de estas “secuencias”; por ejemplo, gr´aficos sencillos con a´ reas de color plano, como iconos y logotipos. Por ejemplo, considera una pantalla que contiene texto en negro sobre un fondo blanco. Habr´ıa muchas secuencias de este tipo con p´ıxeles blancos en los m´argenes vac´ıos, y otras secuencias de p´ıxeles negros en la zona del texto. Supongamos una ´ınica l´ınea (o scanline), con N representando las zonas en negro y B las de blanco: “BBBBBBBBBBBBNBBBBBBBBBBBBNNNBBBB BBBBBBBBBBBBBBBBBBBBNBBBBBBBBBBBBBB” Si aplicamos la codificaci´on run-length a esta l´ınea, obtendr´ıamos lo siguiente: “12B1N12B3N24B1N14B” Interpretado esto como 12 letras B, 1 letra N , 12 letras B, 3 letras N, etc. El c´odigo run-length representa el original de 67 caracteres en tan s´olo 16. Esto quiere decir que la l´ınea original pesa 67 bytes y la cadena codificada pesa s´olo 16 bytes.

´ DEL CODEC ˜ Y PROGRAMACION IV. DISENO HUFFMAN Procedemos a realizar la compresi´on, codificaci´on y decodificaci´on de un archivo de texto, que fue previamente almacenado en la carpeta del programa para evitar errores. La realizaci´on del c´odigo se lo lleva a cabo en el software Matlab, en donde programamos la compresi´on y codificaci´on en un scrip, con el fin de generar un resultado expl´ıcito del comportamiento del sistema. A. Etapa de almacenamiento Primeramente el mensaje a codificar se lo almacena en un .txt con nombre mensaje.txt de manera que el usuario unicamente debera ingresar en este su mensaje a codificar y el programa accede a este txt para su codificaci´on. B. Etapa de asignaci´on El programa luego de ingresar al archivo txt procede a “asignar” a cada letra su respectivo c´odigo “ASCII” y lo almacena en un string de tal manera que se nos facilite trabajar con n´umeros que representara cada letra. C. Etapa de verificaci´on En esta etapa lo que realizamos es la comprobaci´on de cada caracter, de tal manera que vayamos almacenando el numero de veces que se repite cada caracter y de esta manera obtener la probabilidad del mismo, de esta manera sabremos la ocurrencia de cada uno, todas estas probabilidad se van almacenando en otro nuevo string. D. Etapa de compresi´on Hay dos funciones importantes que se encuentran incluidas en Matlab, hablamos de la funci´on ¡huffmamndict¿ que nos permite crear el diccionario d´onde la primera columna de listas del dict son los valores de los s´ımbolos y la segunda columna corresponde a las palabras c´odigo de cada s´ımbolo. La funci´on del huffmandict genera un c´odigo diccionario Huffman que corresponde a una fuente con un modelo de probabilidad conocido. Las entradas requeridas son los s´ımbolos, que corresponde a los distintos valores se˜nalados que el mensaje produce. Y tenemos tambien la funci´on ¡huffmanenco¿, la que nos permite codificar el mensaje con el diccionario anteriormente obtenido , y la funci´on ¡huffmandeco¿ la que nos permite decodificar el mensaje para asi comprobar con el mesanje asignado en un principio. E. C´odigo en la herramienta MATLAB %PRACTICA HUFFMAN CODE clc clear all % LEER ARCHIVO k=1;

fid = fopen(“Mensaje.txt”); % abrir el archivo cadena = fscanf(fid,“%c”); % archivo guardado matriz cadena

cadena %presenta el mensaje a codificar mensaje=double(cadena) %Presenta el mensaje en codigo ASCII

aux=b(j); b(j)=b(j+1); b(j+1)=aux; aux=c(j); c(j)=c(j+1); c(j+1)=aux; end end end

for i=32:255 %225 caracteres ASCII datos=char(i); %char convierte el numero ASCCI a caracter total=length(strfind(cadena,datos)); % formando una matriz con la posicion donde % fue encontrado, leghth calcula el tama˜no de la matriz

for i=1:n fprintf (’%c ⁀’, c(i)) fprintf (’%f , b(i)) i=i+1; end

x=length(cadena); probabilidad=total/length(cadena); % probablidad if(total = 0) % s´ı el total a sido diferente de cero (X,1)

bi=fliplr(b); nh=n ; for i=1:nh-1 ph=bi(i)+bi(i+1); end

fprintf(’MENSAJE A CODIFICAR”); fprintf(’salto de linea’);

L(k) = datos; % Almacena el mensaje n=length(L); V(k) = total; % Almacena las veces que se repite la letra en el texto P(k) = probabilidad; % Almacena las probabilidades de cada letra X(k) = cellstr(datos); %fprintf (“%c ⁀’’, datos) % fprintf (“%f ”,probabilidad) ⁀ veces ”,datos,total); fprintf(“Caracter: %c aparece :%d ⁀ %fprintf(“con probabilidad%f ”,probabilidad); k=k+1; end end fprintf(“Tama˜no del texto de: %d caracteres”,length(cadena));%tama˜no total del txt fprintf(“salto de linea”); % ORDENAR DE MAYOR A MENOR DEPENDIENDO SU PROBABILIDAD b=P; c=L; fprintf (“Simbolos de la fuente”) simbolos = double(c) ⁀ fprintf(“FUENTE ORDENADA”); fprintf(“salto de linea”); for i=1:n for j=1:n-i if b(j) < b(j+1)

matriz=[]; for i=1:n matriz =[matriz, b(i)]; i=i+1; end while (length(matriz)¿2); suma = matriz(length(matriz)) + matriz(length(matriz) - 1) ; matriz( length(matriz) - 1 ) = suma; matriz( length(matriz) ) = []; matriz=sort(matriz, “descend”) end fprintf(“DICCIONARIO”) dict = huffmandict(simbolos,b) %Asigna el diccionario fprintf(“MENSAJE CODIFICADO”) hcode =huffmanenco (mensaje,dict) %Codifica el mensaje dhsig = huffmandeco(hcode,dict) %Decodifica el mensaje fprintf(“MENSAJE DECODIFICADO”) mensajedeco = char(dhsig) tamano1=(length(cadena))*8 tamano2=length(hcode) fprintf(“Tama˜no del archivo original: %d bits” ,tamano1) fprintf(“Tama˜no del archivo comprimido: %d bits”,tamano2)

F. C´odigo de comparaci´on en la herramienta MATLAB %CODIGO RLE clc; clear; st = “AABCDEABCDFGHTREFTFFDVD”

codigo = “”; while length(st) codigo = [codigo st(1)]; st = st(2:end); count = 1; while st & (codigo(end) == st(1)) st = st(2:end); count = count + 1; end codigo = [codigo num2str(count)]; end Ncod=length(codigo) Nor=length(st) Tcrun=(Ncod/Nor)*100; codigo

VI. CONCLUSIONES 1) Se pudo observar y entender mas a fondo el procedimiento de la codificaci´on Huffman. 2) Se logr´o crear un algoritmo pr´opio basado en la codificaci´on Huffman con la ayuda de la herramienta matlab. 3) Se realiz´o multiples pruebas de funcionamiento del codec para verificar su validad. 4) Se valido el codec Huffman comparando el tama˜no de los archivos tanto el original como el comprimido. 5) Se valido el codec Huffman comparandolo con el c´odigo RLE 6) La compresi´o Huffman en matlab es sumamente compleja por lo que ayudarse en las funciones propias de matlab facilito mucho la tarea. 7) Al decodificar tanto utilizando Huffman como RLE se pudo obtener el mensaje original sin error alguno, por lo que se comprob´o tambien la codificaci´on sin p´erdidas.

´ V. VALIDACION Para la validaci´on se procedio a comprimir un determinado texto para luego comprobar el tama˜no en bits del mensaje original con el mensaje codificado en Huffman y a su ves con el c´odigo RLE y de esta manera determinar que codificaci´on ser´ıa la mas adecuada y la mas eficiente. La relaci´on de compresion se define por el cociente entre el tama˜no original del archivo que queremos comprimir y el tama˜no del archivo comprimido. RC =

To Tc

(1)

El texto a comprimir tiene un tama˜no de 3416 bits. El texto comprimido con Huffman tiene un tama˜no de 1975 bits. El texto comprimido con RLE tiene un tama˜no de 6784 bits. HUFFMAN

3416 1975 RC = 1.73 : 1 RC =

RLE RC =

3416 6784

VII. RECOMENDACIONES 1) En la programaci´on se debe tener mucho cuidado en la asignaci´on del codigo Huffman ya que se es propenso a cometer errores en esta etapa. 2) Tener clara la idea sobre la codificaci´on Huffman de esta manera sabemos hacia donde deseamos llegar con nuestro algoritmo. 3) Tener cuidado en el momento que se asigna la probabilidad a cada caracter. 4) Si es posible utilizar las funciones propias de matlab, utilizarlas facilitan en mucho el trabajo.

1)

(2) 2) (3) 3)

RC = 0.503 : 1 4) Podemos observar que la t´ecnica de codificaci´on Huffman tiene una relaci´on de compresi´on mayor a la codificaci´on RLE, demas de esto comparando el tama˜no de cada t´ecnica de codificaci´on, se puede observar claramente que la t´ecnica Huffman es la mas eficiente. As´ı mismo obtenemos el factor de compresi´on del c´odigo Huffman. 1 RC ∗ 100% 1 FC = 1.73 ∗ 100% F C = 59% FC =

(4)

5)

VIII. REFERENCIAS ´ CODIFICACION “Codificaci´on Huffman con Matlab”, Disponible en linea en: [http://www.buenastareas.com/ensayos/Simulaci%C3%B3nEn-Matlab-De-Codificacion-De/3052631.html], consultado el [10-11-2013] MATLAB CENTRAL “Ascii to binary”, Disponible en: [http://www.mathworks.com/matlabcentral/answers/7245],consultado el [10-11-2013]. ´ KIOSKEA “La compresiOn de datos”, Disponible en:[http://es.kioskea.net/contents/714-la-compresion-dedatos], consultado el [10-11-2013]. ´ KIOSKEA “La compresiOn RLE”, Disponible en [http://es.kioskea.net/contents/713-la-compresion-rle], consultado el [11-11-2013] SLIDESAHRE, “C´odigos de Huffman” Disponible en [http://www.slideshare.net/gugaslide/codigo-de-huffmanpresentation], consultado el [11-11-2013]