HolaMundo.pascal (online)

¡Algoritmos en YouTube!

2011-11-10T08:22:00.050-03:00

Algoritmos y Estructuras de Datos (en UTN-FRBA)

Curso dictado en la Universidad Tecnológica Nacional (Buenos Aires, Argentina) por Pablo Sznajdleder. Se trabaja con Delphi 10 (aplicaciones de consola tipo Pascal) y diagramas de Chapín para la representación de algoritmos.

Algoritmos I con Java (en UNSAM)

Curso dictado en la Universidad Nacional de San Martín (Buenos Aires, Argentina) por Pablo Sznajdleder. Se trabaja con Java 5 y Eclipse 3.6.

Capítulo 1

2008-08-24T15:08:00.000-03:00

.
Introducción

Comenzaremos por dar algunas definiciones básicas que nos ayudarán a comprender el alcance de este trabajo.

Problema – Situación planteada que queremos resolver.
Algoritmo – Secuencia finita de acciones con las que podemos resolver el problema.

Según el Teorema de la Programación Estructurada todo problema computacional puede resolverse mediante la aplicación de tres tipos de acciones fundamentales que llamaremos "Estructuras de Control de Flujo de Datos".

Estas acciones son las siguientes:

Ejecutar una acción, luego otra, luego otra,... (lo llamamos acción simple)
Decidir entre ejecutar una u otra acción en función de que se cumpla o no una determinada condición (lo llamamos acción condicional)
Ejecutar repetidas veces la misma acción mientras se cumpla una determinada condición (lo llamamos acción iterativa).

Estructuras de Control de Flujo de Datos

Acción Simple

Esta es la más básica de las estructuras. Se considera acción simple a las acciones de leer (por teclado o desde un archivo), escribir (por pantalla, impresora o en un archivo) y asignar. Graficamente lo representamos de la siguiente manera:

Lectura (o entrada) – Leemos (por teclado) un valor y lo almacenamos en la variable a.

Asignación – Asignamos el valor de la variable a a la variable b.

Escritura (o salida) – Mostramos (por pantalla o impresora) la frase “Hola Mundo” seguida del valor que contenga la variable b.

Variables y Tipos de Datos

Una variable representa un espacio de memoria (RAM) en el cual podemos almacenar temporalmente valores.

Podemos tener valores numéricos, alfanuméricos, lógicos y definidos por el programador. Es decir: valores de diferentes tipos (de datos).

Si hablamos del valor 123 estamos hablando de un valor numérico entero. Podemos decir entonces que 123 es un entero. En cambio, si hablamos del valor 12.3 estamos hablando de un valor numérico real.

También podemos hablar del valor “Hola Mundo”. En este caso estamos hablando de un valor alfanumérico. Decimos que este valor es una cadena de caracteres o simplemente una cadena.

Otro valor alfanumérico podría ser "123 Hola Mundo 456" que contiene caracteres letras y números. Es alfanumérico.

Obviamente no es lo mismo el valor “123” que 123. El primero es un valor alfanumérico (está encerrado entre comillas) mientras que el segundo es un entero.

Otro tipo de datos es el dato lógico o booleano. Los datos booleanos solo pueden contener valores lógicos: verdadero o falso (true o false).

Resumiendo lo anterior diremos que podemos tener variables de diferentes tipos de datos. Los tipos de datos pueden ser numéricos, alfanuméricos, booleanos o definidos por el programador (pero esto lo veremos más adelante).

Las variables se identifican con un nombre (o identificador). El nombre de la variable debe comenzar con una letra. No puede tener espacios ni caracteres especiales.

Nombres válidos son:

fechaNac
fecNac
f
iFechaNac

Nombres incorrectos son:

fecha nacimiento // no puede haber un espacio
fecha-nacimiento // el caracter " - " se utiliza para restar
12fecha // debe comenzar con una letra
fecha+nacimiento // el caracter " + " se utiliza para sumar

Comenzando a Programar

Con lo estudiado hasta aquí estamos en condiciones de resolver el siguiente problema.

Problema 1.0
Se requiere un programa que permita ingresar el nombre de una persona y que luego escriba la leyenda “Hola Mundo” seguida del nombre ingresado.

Análisis
Primero emitimos un mensaje indicando al usuario que debe ingresar su nombre (utilizamos la acción simple escritura). Para leer el nombre utilizamos la acción simple de lectura. El usuario ingresa por teclado su nombre, lo leemos y lo almacenamos en la variable nom. Luego utilizamos la acción simple de escritura para mostrar la cadena “Hola Mundo” seguida del valor que contiene la variable nom. Las letras C y F encerradas en un círculo indican donde comienza y donde finaliza el programa.

Codificación del Algoritmo

El gráfico que acabamos de analizar representa el algoritmo que resuelve el problema planteado.

Para que una computadora pueda interpretar y ejecutar este algoritmo debemos codificarlo en algún lenguaje de programación. En este apunte utilizaremos el lenguaje de programación Pascal.

Para programar en Pascal tenemos que escribir el código fuente (sentencias e instrucciones que veremos a continuación) en un archivo de texto con extensión .pas.

problema1.0.pas

   1:
   2:var nom:string[20];
   3:begin
   4:   // escribe este mensaje por pantalla
   5:   write('Ingrese su nombre: ');
   6:
   7:   // lee un valor y lo guarda en la variable nom
   8:   // (el usuario debe escribir su nombre por teclado)
   9:   readln(nom);
  10:
  11:   // escribe (en pantalla) la cadena 'Hola Mundo'
  12:   // seguida del valor que contiene la variable nom
  13:   writeln('Hola Mundo ',nom);
  14:end.
  15:

El código comienza con la definición de la variable nom. Pascal es un leguaje fuertemente tipado por lo que todos los recursos que vayamos a utilizar en el programa (variables, funciones, etc) deben ser previamente especificados, indicando explicitamente su tipo de datos. En el caso de la variable nom su tipo de datos es string (alfanumérico, cadena de caracteres). En particular lo definimos como string[20] (arbitrareamente) por lo tanto en la variable nom podremos almacenar cadenas de a lo sumo 20 caracteres.

Luego, podemos ver que el programa está encerrado entre las palabras begin y end. Se dice que begin-end encierran un bloque de código. Cada sentencia termina con “punto y coma” salvo el end final que termina con “punto”.

Dentro del código podemos escribir comentarios para ayudarnos a comprender mejor el programa. Los comentarios deben comenzar con “doble barra”.

No es una buena práctica utilizar caracteres especiales dentro de un archivo de código. Es decir: no debemos usar acentos ni "eñes" en los comentarios ni en ninguna parte del código fuente.

Nota: el código anterior es compatible con Free Pascal (http://www.freepascal.org/). Difiere en algunos detalles con Borland Turbo Pascal. En este apunte utilizaremos Free Pascal.

Para editar y compilar el programa vamos a necesitar utilizar una herramienta de desarrollo: Una IDE ("Entorno Integrado de Desarrollo"). Utilizaremos EditPad PRO + FreePascal.

Acción Condicional o Estructura de Decisión

La estructura de decisión permite decidir entre ejecutar un conjunto de acciones u otro en función una expresión lógica. Es decir: una expresión que tenga valor de verdad.

Representamos la acción condicional de la siguiente manera:

Cuando el algoritmo (o programa) llega a una acción condicional debe evaluar la expresión lógica (ubicada en la parte superior). Si esta tiene valor de verdad true (verdadero) entonces se ejecutan las acciones que se encuentran en la parte izquierda de la estructura. Si la expresión resulta false (falsa) entonces se ejecutan las acciones ubicadas a la derecha.

Problema 1.1
Leer un valor e indicar si el valor ingresado es mayor que 10.

Análisis
Leemos el valor en la variable v. Luego con una acción condicional evaluamos si el valor de v es mayor que 10. Si resulta verdadero (esto depende de lo que ingrese el usuario) entonces se ejecuta la parte izquierda de la estructura y se muestra un mensaje indicando que el valor ingresado es mayor que 10.

Si la condición resulta falsa entonces podemos asegurar que el valor NO es mayor que 10. Pero no sabemos si es menor o igual. Esto lo estudiaremos en el próximo problema.

problema1.1.pas

   1:
   2:var v:integer;
   3:begin
   4:   // leemos un valor por teclado
   5:   writeln('Ingrese un valor: ');
   6:   readln(v);
   7:
   8:   // si v (el valor leido) es mayor que 10 entonces
   9:   if( v>10 ) then begin
  10:      writeln('El valor mayor que 10');
  11:   end else begin // si v no es mayor que 10...
  12:      writeln('El valor NO es mayor que 10');
  13:   end;
  14:end.
  15:

La acción condicional se codifica con la sentencia if (ver línea 9). Esta sentencia evalúa la expresión lógica ubicada dentro de los paréntesis y decide (en función de que resulte true o false) que bloque de código ejecutar. Si la expresión v>10 resulta verdadera entonces se ejecuta la línea 10, si no (else) se ejecuta la línea 12.

Notemos que tanto la línea 10 como la línea 12 están encerradas en bloques begin-end. Por eso hablamos de "bloques de código". Dentro un bloque de código puede haber más de una instrucción como veremos en los próximos ejemplos.

Problema 1.2
Idem anterior pero indicar si el valor ingresado es mayor, menor o igual que 10.

Análisis
Para resolver este problema leemos v y preguntamos si es mayor que 10. Si resulta verdadero entonces podemos mostrar ese resultado. Si no es mayor entonces puede ser igual o menor. Tenemos que preguntar por alguna de estas posibilidades. Preguntamos si v=10. Si es verdadero entonces ya sabemos que se ingresó el valor 10. Si es falso entonces (como no es mayor ni es igual) resulta que v es menor que 10.

Utilizamos estructuras de desición anidadas (o "ifes" anidados).

problema1.2.pas

   1:
   2:var v:integer;
   3:begin
   4:   write('Ingrese un valor: ');
   5:   readln(v);
   6:   if( v>10 ) then begin // es mayor
   7:      writeln('El valor mayor que 10');
   8:   end else begin // es igual
   9:      if( v=10 ) then begin
  10:         writeln('Es igual a 10');
  11:      end else begin // es menor
  12:         writeln('Es menor que 10');
  13:      end;
  14:   end;
  15:end.
  16:

En este problema vemos estructuras de desición anidadas (o "ifes anidados") pero aún así los bloques de código encerrados en los if-else tienen una única acción. El if de la línea 6 encierra una única acción writeln. Su else encierra una única acción if que a su vez encierra una única acción, tanto por verdadero (línea 10) como por falso (línea 12).

Problema 1.3

Leer tres valores numéricos. Indicar cual es mayor, medio y menor.
Nota: se asume que los tres valores serán diferentes.

Análisis
Leemos los tres valores y comenzamos a comparar. Preguntamos si a>b. Si esto se verifica entonces preguntamos si a>c. Si esto también se verifica resulta que a>b y a>c. No hay dudas de que a es el mayor. Luego tenemos que comparar b y c para ver cual esta en segundo y en tercer lugar.

Si resulta que a>b pero no se verifica que a>c (o sea que c es mayor que a) será c el mayor, a el medio y b el menor.

Por otro lado, si no se verifica que a>b preguntamos si b>c. Si esto es así entonces el mayor será b (ya que b es mayor que a y b es mayor que c). Preguntamos si a>c y ya podremos deducir cual está en segundo y tercer lugar.

Para finalizar, si es falso que b>c entonces el mayor será c, medio b y menor a.

problema1.3.pas

   1:
   2:var a,b,c:integer;
   3:begin
   4:   write('Ingrese tres valores: ');
   5:
   6:   // lee los 3 valores numericos 
   7:   // separados por espacio en blanco
   8:   readln(a,b,c);
   9:
  10:   if( a>b ) then begin
  11:      if( a>c ) then begin
  12:         writeln('Mayor:',a);
  13:         if( b>c ) then begin
  14:            writeln('Medio:',b);
  15:            writeln('Menor:',c);
  16:         end else begin
  17:            writeln('Medio:',c);
  18:            writeln('Menor:',b);
  19:         end;
  20:      end else begin
  21:         writeln('Mayor:',c);
  22:         writeln('Medio:',a);
  23:         writeln('Menor:',b);
  24:      end;
  25:   end else begin
  26:      if( b>c ) then begin
  27:         writeln('Mayor:',b);
  28:         if( a>c ) then begin
  29:            writeln('Medio:',a);
  30:            writeln('Menor:',c);
  31:         end else begin
  32:            writeln('Medio:',c);
  33:            writeln('Menor:',a);
  34:         end;
  35:      end else begin
  36:         writeln('Mayor:',c);
  37:         writeln('Medio:',b);
  38:         writeln('Menor:',a);
  39:      end;
  40:   end;
  41:end.
  42:

En este código vemos bloques if-else con más de una instrucción. El if de la línea 10 tiene una única instrucción (un if que comienza en la línea 11 y finaliza en la línea 24). El if de la línea 11 tiene dos instrucciones: un writeln y un if que a su vez tiene dos instrucciones por verdadero (líneas 14 y 15) y otras dos por falso (líneas 17 y 18).

Operadores Lógicos

Una proposición es una expresión que tiene valor de verdad (true o false). Es decir: puede verificarse o no.

Los siguientes ejemplos son proposiciones y por lo tanto tienen valor de verdad.

“Una semana tiene 7 días” (true)
“7 es número primo” (true)
“2 es mayor que 5” (false)
“4 = 2+3” (false)

Podemos utilizar operadores lógicos para realizar operaciones entre proposiciones y así obtener nuevas proposiciones con sus correspondientes valores de verdad.

Los operadores lógicos son: AND, OR y NOT.

Las siguientes tablas muestran el valor de verdad de la proposición que resulta luego de operar dos proposiciones p y q con los diferentes operadores lógicos.

Veamos otra solución para el problema 1.3 (versión 2)

Análisis
La solución es similar: varios if anidados, pero en este caso utilizamos operadores lógicos para evaluar más de una condición en un mismo if.

Comenzamos preguntando si a>b AND a>c para asegurarnos de que a es el mayor valor. Teniendo esto seguro (entramos por la parte izquierda de la estructura) tenemos que ver cual es el valor medio y cual es el menor.

Si a no es el mayor (ingresamos por la parte derecha de la estructura) preguntamos si b es el mayor (b>a AND b>c). Si esto es así entonces comparamos a con c para ver quien está en segundo y tercer lugar. Si no (si b no es el mayor) entonces por descarte el mayor será c. Luego también comparamos a y b para ver quien es medio y menor.

Otra diferencia con la solución anterior es que en este caso estamos utilizando tres variables temporales: mayor, medio y menor para asignar los valores a medida que podemos deducir que posición tienen. Luego simplemente mostramos el valor de estas variables para informar los resultados.

problema1.3v2.pas

   1:
   2:var a,b,c,mayor,medio,menor:integer;
   3:begin
   4:   write('Ingrese tres valores: ');
   5:   readln(a,b,c);
   6:
   7:   // pregunto si a es el mayor
   8:   if( (a>b) AND (a>c) ) then begin
   9:      mayor:=a;
  10:      // como a es el mayor, comparo b con c
  11:      if( b>c ) then begin
  12:         medio:=b;
  13:         menor:=c;
  14:      end else begin
  15:         medio:=c;
  16:         menor:=b;
  17:      end;
  18:   end else begin
  19:      // a no es el mayor, pregunto si el mayor es b
  20:      if( (b>a) AND (b>c) ) then begin
  21:         mayor:=b;
  22:         // el mayor es b, comparo a con c
  23:         if( a>c ) then begin
  24:            medio:=a;
  25:            menor:=c;
  26:         end else begin
  27:            medio:=c;
  28:            menor:=a;
  29:         end;
  30:      end else begin
  31:         // el mayor no es a ni es b. Entonces es c
  32:         mayor:=c;
  33:         // solo queda comparar a con b
  34:         if( a>b ) then begin
  35:            medio:=a;
  36:            menor:=b;
  37:         end else begin
  38:            medio:=b;
  39:            menor:=a;
  40:         end;
  41:      end;
  42:   end;
  43:
  44:   // muestro los resultados obtenidos
  45:   writeln('Mayor: ', mayor);
  46:   writeln('Medio: ', medio);
  47:   writeln('Menor: ', menor);
  48:end.
  49:

Acción iterativa o Estructura de Repetición

La tercer y última estructura de control de flujo de datos es la estructura de repetición (o iterativa). Existen tres estructuras interativas: while, repeat-until y for.

El while, lo representamos de la siguiente manera:

Decimos que mientras se verifique la condición indicada en la parte superior de la estructura se repetirán las acciones que se encuentran dentro del cuerpo principal de la misma (secuencialmente).

Como existe la posibilidad de que la condición no se cumpla al momento de llegar al while y que no se ingrese al ciclo ni siquiera la primera vez se dice que el while es una estructura repetitiva de 0-n (cero a ene) ya que puede iterar desde cero hasta n veces.

Problema 1.4
Imprimir por pantalla los primeros n números positivos (el valor n se ingresa por teclado).

Análisis
La estrategia para solucionar este problema consiste utilizar una variable i con el valor inicial 1 (primer número positivo) e ir mostrando e incrementando su valor mientras este sea menor o igual al valor ingresado por el usuario (n).

Supongamos que el usuario ingresa un valor n=3. Al llegar al ciclo de repetición la condición "i es menor o igual a n" resultará verdadera ya que i vale 1 (dado que lo asignamos antes de ingresar al ciclo) y n vale 3 (es lo que estamos asumiendo). Entonces el programa ingresa al ciclo y muestra el valor de la variable i. A continuación vemos la asignación i <-- i+1. Esto debe leerse así: “a i le asigno el valor que i tenía más 1”. Es decir que si i valía 1 entonces ahora a i le asignamos 1 (lo que tenía) +1 dejando su valor en 2. Es decir: incrementamos el valor de i. Como no hay mas acciones para ejecutar dentro del ciclo, el próximo paso es volver a evaluar la condición para ver si se continúa verificando.

En la siguiente iteración i vale 2 y n vale 3. Todavía se verifica que "i es menor o igual a n". Se vuelve a ingresar al ciclo y se imprime el valor de i (2). Luego se incrementa i y así hasta que no se cumpla la condición.

problema1.4.pas

   1:
   2:var i,n: integer;
   3:begin
   4:   // leo un valor por teclado
   5:   write('Ingrese un valor: ');
   6:   readln(n);
   7:
   8:   // inicializo la variable i con el valor 1
   9:   i:=1;
  10:
  11:   // itero mientras que i sea menor o igual a n
  12:   while( i<=n ) do begin
  13:
  14:      // muestro el valor de i
  15:      writeln(i);
  16:
  17:      // incremento el valor de i
  18:      i:=i+1;
  19:   end;
  20:end.
  21:

Ciclo repeat-until

Lo representamos así:

El ciclo repeat-until es un ciclo de 1 a n. Para ingresar al ciclo no hay condición por lo tanto las acciones que se encuentran dentro del ciclo se realizarán al menos una vez. Luego de la última acción (en este caso acción3) se evalúa la condición que se encuentra en la parte posterior de la estructura.

El ciclo iterará hasta que se verifique la condición ("repeat-until" significa "repetir-hasta").

Tenemos que tener clara la diferencia entre el ciclo while y el ciclo repeat-until. El primero repite mientras, en cambio el segundo repite hasta que se cumpla la condición.

Veamos como podemos resolver el problema 1.4 utilizando un ciclo repeat-until en lugar de un ciclo while.

Basicamente la diferencia está en la condición del ciclo. Antes iteraba "mientras que i sea menor o igual que n". Ahora itera "hasta que i sea mayor que n".

problema1.4v2.pas

   1:
   2:var i,n: integer;
   3:begin
   4:   write('Ingrese un valor: ');
   5:   readln(n);
   6:   i:=1;
   7:
   8:   repeat
   9:      writeln(i);
  10:      i:=i+1;
  11:   until( i>n );
  12:end.
  13:

Ciclo for.

Este es otro ciclo iterativo de 0 a n iteraciones. Se representa así:

El ciclo for funciona con una variable de control (en el gráfico es la variable i) que toma un valor inicial (h) y un valor final (t). La variable de control se incrementa automaticamente en cada iteración tomando el valor h en la primer iteración, h+1 en la segunda y t en la última. Así, el ciclo dará exactamente t-h+1 iteraciones.

Como vemos en el gráfico tenemos dos opciones para representarlo. Podemos utilizar cualquiera de las dos.

Veamos como lo aplicamos en el problema 1.4

Vemos que en este caso el uso de un ciclo for simplifica la solución del problema. Simplemente leemos el valor n y luego entramos en un ciclo for con la variable i incrementándose desde 1 hasta n.

Dentro del ciclo solo tenemos que mostrar el valor de i. Ya no es necesario incrementarla porque el mismo ciclo la incrementa automaticamente.

problema1.4v3.pas

   1:
   2:var i,n: integer;
   3:begin
   4:   write('Ingrese un valor: ');
   5:   readln(n);
   6:   for i:=1 to n do begin
   7:      writeln(i);
   8:   end;
   9:end.
  10:

Contadores y Acumuladores

Para explicar estos temas analizaremos el siguiente problema.

Problema 1.5
Leer un conjunto de valores que corresponden a las edades de un grupo de personas, indicar:

a - Cuantas personas (sus edades) se ingresaron.
b - Cuantas son mayores de edad (21 años o más).
c - Edad promedio de las personas.

El conjunto de valores finaliza cuando se ingresa una edad menor que cero.

Análisis
La estructura principal de este algoritmo consiste en un ciclo repetitivo que itera mientras la edad leida (e) sea mayor o igual que cero (ya que se ingresará un valor negativo para indicar el fin de datos). Se lee la edad antes de ingresar al while y antes de cerrarlo.

Para calcular cuantas personas se ingresaron (punto a) utilizamos la variable cantPersonas. Esta variable se inicializa con cero (cantPersonas:=0) antes de ingresar al while, y dentro del while (por cada iteración) la incrementamos asignándole el valor que tenía más 1. (cantPersonas:=cantPersonas+1).

La variable cantPersonas incrementa su valor en 1 por cada iteración del while. A su vez, el while itera tantas veces como edades válidas de personas se ingresen. Decimos entonces que cantPersonas es un contador que cuenta (en este caso) la cantidad de personas cuyas edades se ingresaron. O bien: cantPersonas es el contador de personas.

Es muy importante notar que el contador debe inicializarse en cero ya que para incrementar su valor hacemos referencia al valor que tenía más 1. En el momento inicial (primera iteración) debe valer cero.

Para calcular cuantas personas son mayores de 21 años (punto b) utilizamos otro contador (mayores) solo que antes de incrementarlo preguntamos si la edad leida es mayor o igual que 21.

Para calcular el promedio de las edades grupo (punto c) necesitamos dos datos: la cantidad de edades ingresadas y la sumatoria de las edades. La cantidad de edades ingresadas ya la tenemos en la variable cantPersonas. Por lo tanto necesitamos obtener la sumatoria de las edades. Para esto utilizamos un acumulador.

A la variable sumEdades (que inicializamos en cero) le incrementamos su valor en cada iteración del while. Pero no lo incrementamos en 1. Le asignamos lo que tenía más el valor de la variable e (la edad).

Decimos entonces que sumEdades es un acumulador que acumula (en este caso) las edades leidas. O simplemente: sumEdades es el acumulador de edades.

Al finalizar el while tenemos en cantPersonas la cantidad de personas del conjunto, en mayores la cantidad de personas mayores de 21. Luego a edadProm le asignamos sumEdades/cantPersonas para calcular la edad promedio del conjunto.

problema1.5.pas

   1:
   2:var e,mayores,cantPersonas, sumEdades:integer;
   3:    edadProm:real;
   4:begin
   5:   mayores:=0;
   6:   cantPersonas:=0;
   7:   sumEdades:=0;
   8:
   9:   write('Ingrese Edad:');
  10:   readln(e);
  11:
  12:   while( e >= 0 ) do begin
  13:      // contador de edades ingresadas
  14:      cantPersonas:=cantPersonas+1;
  15:
  16:      // acumulador de edades
  17:      sumEdades:=sumEdades+e;
  18:
  19:      if( e >= 21 ) then begin
  20:         mayores:=mayores+1;
  21:      end;
  22:
  23:      write('Ingrese Edad:');
  24:      readln(e);
  25:   end;
  26:
  27:   edadProm:=sumEdades/cantPersonas;
  28:   writeln('Cantidad de Personas: ',cantPersonas);
  29:   writeln('Mayores de 21: ',mayores);
  30:   writeln('Edad Promedio: ',edadProm);
  31:end.
  32:

Resumiendo, decimos que una variable es un contador cuando incrementamos su valor en una unidad.

cont:=cont+1

Decimos que una variable es un acumulador cuando incrementamos su valor en una cantidad variable.

acum:=acum+n

donde n es una variable cuyo valor puede variar.

Nomenclatura

Pascal es un lenguaje de programación "insensible" a las mayúsculas y minúsculas por lo tanto podemos escribir código Pascal en mayúscula, en minúscula o con combinaciones de mayúsculas y minúsculas.

Las variables (o identificadores) también son "insensibles" por lo que la variable a es la misma que la variable A. La variable fechanacimiento es la misma que FECHANACIMIENTO y la misma que fechaNacimiento.

Sin embargo en este trabajo utilizaremos la siguiente convensión de nomenclatura:

Todas las palabras reservadas de Pascal (while, for, repeat-until, if, etc) las escribiremos en minúscula.

Todos los nombres de variables deben comenzar con minúscula. Si el nombre de la variable está compuesto por más de una palabra entonces la primer inicial irá en minúscula pero las iniciales siguientes deben ir en mayúscula.

Por ejemplo:

fechaNacimiento
fecNac
nomPersona
edad
legajo
legajoEmpleado

.
Algoritmos y Estructuras de Datos UTN - UBA.

TP - Compresor Huffman

2008-06-20T00:56:00.000-03:00

.
Algortimo de Huffman

El algoritmo de Huffman es un algoritmo que permite comprimir y encriptar datos basándose en la probabilidad de ocurrencia de cada uno de los caracteres contenidos en el mensaje (o archivo) a comprimir/encriptar.

El objetivo de este trabajo es aplicar el algoritmo de Huffman para desarrollar un programa que permita comprimir y descomprimir archivos.

Teoría de Huffman

El algotirmo de Huffman asigna a cada caracter del archivo un código (que llamaremos código Huffman) de longitud variable (medida en cantidad de bits). A los caracteres con mayor cantidad de ocurrencias se les asigna un código Huffman con menor longitud y a los que tienen menor cantidad de ocurrencias se les asigna un código con longitud mayor.

A continuación vamos a analizar un ejemplo completo para comprender como funciona el algoritmo que utilizaremos para comprimir y descomprimir archivos.

Ejemplo

Supongamos que tenemos que comprimir un archivo que contiene el siguiente texto:

COMO COME COCORITO COME COMO COSMONAUTA

Paso 1
Contar las ocurrencias de cada caracter.

Para contar las ocurrencias utilizamos una tabla (que luego implementaremos como un array de 0 a 255 registros) en la que almacenamos el caracter (en la posición del array que coincide con su código ASCII) y la cantidad de ocurrencias de este caracter en el archivo (que llamaremos n).

Paso 2
Creamos una lista ordenada ascendentemente por la cantidad de ocurrencias de cada caracter. Primero los menos ocurrentes y luego los más ocurrentes. Si dos caracteres ocurren con igual probabilidad entonces primero colocamos al que tiene menor valor ASCII. Por ejemplo: en la tabla vemos que los caractetes I, N, R, S, U ocurren una sola vez. Tienen la misma probabilidad de ocurrencia entre si por lo tanto en la lista ordenada que veremos a continuación los colocaremos por orden ascendente de su código ASCII (léase de izquierda a derecha y de arriba hacia abajo).

Paso 3
Tomamos los dos primeros nodos de la lista y creamos un pequeño árbol binario que tandrá un nodo raíz con un caracter ficticio que llamaremos *1 (asterisco uno) y una probabilidad de ocurrencia igual a la suma de las probabilidades de los dos nodos que estamos procesando. En la rama derecha colocamos el primer nodo y en la rama izquierda colocamos el segundo nodo.

Luego insertamos el nuevo nodo en la lista respetando el criterio de ordenamiento. Si en la lista existe un caracter con la misma probabilidad (en este caso 2) la inserción la haremos a continuación del caracter existente.

Ahora repetimos la operación tomando los nodos R(1) y S(1):

Continuamos con este proceso hasta obtener un único nodo cuya probabilidad (cantidad de ocurrencias) sea igual a la suma de las probabilidades de los caracteres del archivo.
El desarrollo completo del árbol puede verse en este link.

Paso 4
Con el árbol terminado, comenzamos a codificar los caracteres asignando 0 (cero) a cada nodo a la izquierda y 1 (uno) a cada nodo a la derecha.

Entonces para obtener la codificación Huffman de un caracter simplemente recorremos el árbol hasta llegar a la hoja que contiene el caracter que queremos codificar. Asignamos unos o ceros según nos indique camino que tomamos.

Así, el código Huffman para codificar el caracter R será: 10101, cuya longitud (que llamaremos nCod) es 5. En cambio para codificar el caracter M el código será: 001 y su nCod = 3. Y para codificar el caracter O (letra “O”) obtendremos el código: 01, con nCod = 2.

Podemos observar que el caracter que más se repite en el texto (o archivo) que estamos procesando (la letra O) obtuvo un código de longitud menor (nCod = 2), en cambio el caracter R (uno de los que menos veces aparece) obtuvo un código de longitud mayor (nCod = 5). Y un caracter intermedio como la M que aparece 5 veces obtuvo un código de longitud intermedia: nCod = 3.

Recordemos que cada carecter ocupa 1 byte (8 bits). Huffman permite reemplazar los 8 bits de (por ejemplo) el caracter M por los 3 bits del código que obtuvimos.

Paso 5
Volvamos a la tabla de ocurrencias para asignar el código Huffman (cod) y el nCod que le corresponde a cada caracter del texto que estamos procesando.

Paso 6
Para finalizar el proceso simplemente reemplazamos cada caracter por su código Huffman y luego agrupamos en paquetes de a 8 bits para obtener los bytes que serán el resultado del algoritmo.

Como resultado logramos comprimir un texto de 39 bytes (39 caracteres) en solo 16 bytes. El algoritmo permite comprimir este texto casi un 59%.

Capítulo 3

2008-05-23T16:07:00.025-03:00

.
Operadores Binarios

Con estos operadores podemos realizar operaciones a nivel de bit sobre variables de tipo entero: byte (1 byte), word (2 bytes), shortint (1 byte con bit de signo), integer (2 bytes con bit de signo) y longint (4 bytes con bit de signo).

Recordemos que un número entero, que nosotros vemos y expresamos en decimal, internamente tiene una representación binaria. Por ejemplo:

var a,b: integer;
begin
...a := 77; // en binario es: |00000000|01001101|
...b := -77; // en binario es: |10000000|01001101|
end.

Vemos que tanto a como b se representan en dos bytes (son de tipo integer). El bit más significativo (el más a la izquierda) se utiliza para representar el signo (ya que integer es un tipo signado): 1 indica que el número es negativo mientras 0 (cero) indica que el número es positivo.

Supongamos ahora que la variable a la definimos de tipo byte (no signado) y le asignamos el valor 77. Su representación binaria será:

Se lo representa en un único byte y sin bit de signo. El bit más a la izquierda ahora representa un valor numérico por lo tanto en una variable de tipo byte podemos almacenar valores entre 0 y 255.

Vemos también que cada bit representa una potencia de 2. El bit más a la derecha (el menos significativo) representa la potencia cero (2 a la cero), el siguiente (hacia la izquierda) representa la potencia uno (2 a la uno) y así sucesivamente. El valor 77 (decimal) se obtiene sumando las potencias de dos cuyos bits valen 1 (pintados en celeste).

Luego de esta introducción podemos analizar los operadores binarios.

Operadores OR y AND binarios

Sean las siguientes definiciones:

var x,y,z,t: byte;
begin
...x := 77; // en binario es: |01001101|
...y := 194; // en binario es: |11000010|
...z := x OR Y; // ver explicacion
...t := x AND y; // ver explicacion
end.

La variable z tendrá un 1 en cada posición en la que x o y (o ambos) tengan 1 ya que el operador OR unirá los unos de ambos operandos.

x := 01001101
y := 11000010
z := 11001111

Entonces el resultado de x OR y (que asignamos a z) será: 207.

La variable t (a la que le asignamos el resultado de x AND y) solo tendrá un 1 en aquellas posiciones en las que ambos operandos tengan 1.

x := 01001101
y := 11000010
t := 01000000

En este caso la variable t quedará con el valor 64.

Operador NOT

var x,y,z,t: byte;
begin
...x := 77; // en binario es: |01001101|
...y := NOT x; // ver explicacion
...z := 0; // en binario |00000000|
...t := NOT z; // ver explicacion
end.

El operador NOT "niega" cada posición del byte asignando 1 en aquellas posiciones en las que el byte tiene cero y cero en las posiciones en las que el byte tiene 1. Entonces:

a x le asignamos 77 y a y le asignamos NOT x:

x := 01001101
y := 10110010

y queda con 178. Luego a z le asignamos 0 y a t le asignamos NOT z:

z := 00000000
t := 11111111

t queda con 255.

Desplazamiento (shift) de Bits

Los operadores de dezplazamiento permiten correr hacia la izquierda o hacia la derecha los bits de un número no signado.

var x,y,z,t: byte;
begin
...x := 24; // en binario es: |00011000|
...y := x >> 2; // el resultado es: |00000110|
...z := x << 2; // el resultado es: |01100000|
...t := x << 3; // el resultado es: |11000000|
end.

Como vemos, la "doble flecha" indica la dirección (izquierda o derecha) en la que queremos desplazar los bits del número binario. En este ejemplo: y queda con el valor 6, z queda con 96 y t queda con 192.

Problema
Una empresa toma la desición de que las fechas dentro de sus sistemas queden representadas en 2 bytes con el siguiente formato: Los 7 bits "más a la izquierda" representarán el año, los siguientes 4 bits (hacia la derecha) representarán el mes y los restantes 5 bits (hacia la derecha) representarán el día.

Se pide

1 - Desarrollar tres funciones llamadas getAnio, getMes y getDia, que reciban una fecha expresada en un word (2 bytes sin signo) y retornen el año, el mes y el día (respectivamente) representados en la fecha pasada como parámetro.

2 - Desarrollar tres procedimientos llamados setAnio, setMes y setDia, que reciban un var word (que representa una fecha) y un valor que indicará el año, mes o día (respectivamente) que se desea asignar en la fecha recibida por referencia. Estas funciones permiten facilmente componer una fecha con el formato definido.

Nota: El año debe considerarse de la siguiente manera: sea a el valor expresado en los 7 bits correspondientes al año entonces:

año = 2000 - 50 + a

Es decir: Si a vale 50 representa al año 2000. Si a vale 51 representa al año 2001. Si a vale 52 representa al año 2002, si vale 49 representa al año 1999 y así sucesivamente.

Análisis

Desarrollaremos las seis funciones en una unit llamada untFechasBin.pas. Antes de comenzar analizaremos la sección interface de la unit para dejar en claro sus encabezados.

untFechasBin.pas

   1:
   2:unit untFechasBin;
   3:
   4:interface
   5:
   6:   const
   7:      MASK_ANIO = 65024; // |11111110|00000000|
   8:      MASK_MES  = 480;   // |00000001|11100000|
   9:      MASK_DIA  = 31;    // |00000000|00011111|
  10:
  11:   // funciones para setear la fecha
  12:   procedure setAnio(var fecha:word; a:word);
  13:   procedure setMes(var fecha:word; m:word);
  14:   procedure setDia(var fecha:word; d:word);
  15:
  16:   // funciones para leer una fecha
  17:   function getAnio(fecha:word):word;
  18:   function getMes(fecha:word):word;
  19:   function getDia(fecha:word):word;
  20:
  21:implementation
  22:
  23:// :
  24:// : desarrollado mas abajo
  25:// : 
  26:
  27:end.
  28:

Primero analizaremos un programa principal que invoque a las funciones para componer una fecha (en este caso la fecha 2 de octubre de 2008):

testFechasBin.pas

   1:
   2:uses untFechasBin;
   3:
   4:var f:word;
   5:begin
   6:   f:=0;
   7:
   8:   setDia(f,2);
   9:   setMes(f,10);
  10:   setAnio(f,2008);
  11:
  12:   writeln('Dia: ', getDia(f));
  13:   writeln('Mes: ', getMes(f));
  14:   writeln('Anio: ', getAnio(f));
  15:end.
  16:

El formato definido para las fechas asigna 5 bits para representar el día. En 5 bits podemos almacenar números comprendidos entre cero y "(2 a la n) -1", es decir: 31. Para representar el mes se asignaron 4 bits que permiten un rango numérico de entre cero y 15. Por último, para representar el año se asignan 7 bits con los que podemos representar valores de entre 0 y 127. Como este rango no es suficiente para representar un año de 4 dígitos se definió la regla indicada más arriba (50 representa al año 2000, etc).

función getDia

Esta función es la más fácil de resolver. Los bits que representan al día son los 5 bits más a la derecha de los dos bytes del word que contiene la fecha. Si pudiésemos asignar cero a todos los otros bits y dejar intactos estos 5 bits, el valor decimal resultante será el día que tenemos que retornar.

Para asignar cero a todos los otros bits y dejar intactos los 5 bits que representan el día tenemos que hacer un AND entre la fecha y un número que tenga unos en los primeros 5 bits y ceros en los bits restantes. Como estamos utilizando tipos word entonces "fabricamos" nuestro número en 2 bytes:

|00000000|00011111|

Este número binario representa al valor decimal: 31. Decimos que es una "máscara para día". Si hacemos un AND entre una fecha (un word) y 31 estaremos dejando intactos los primeros 5 bits y asignando ceros a los bits restantes.

1:
2:function getDia(fecha:word):word;
3:begin
4:   getDia:=fecha AND MASK_DIA;
5:end;
6:

En la sección interface definimos tres constantes: MASK_DIA, MASK_MES y MASK_ANIO con el objetivo de "blanquear" los bits que no interesan y dejar "limpios" los bits que representan al día, mes y año respectivamente.

función getMes

El análisis es el mismo: debemos "blanquear" (poner en cero) todos aquellos bits que no representan al mes y dejar intactos los 4 bits nos interesan. La máscara para el mes está definida en la sección interface y corresponde al valor decimal 480.

|00000001|11100000|

La diferencia con la función anterior es que en este caso los bits que representan al mes no están ubicados a la derecha del word, están por el medio. Por esto, luego de aplicar la máscara tenemos que correrlos hacia la derecha para que su valor decimal coincida con el mes representado en la fecha.

 6:
 7:function getMes(fecha:word):word;
 8:var aux:word;
 9:begin
10:   aux:=fecha AND MASK_MES;
11:   aux:=aux>>5;
12:   getMes:=aux;
13:end;
14:

función getAnio

El análisis es el mismo que para getMes solo que además hay que considerar lo que se definió: 50 representa al año 2000, y año<50 o año>50 entonces representa al año 2000-50+año.

14:
15:function getAnio(fecha:word):word;
16:var aux:word;
17:begin
18:   aux:=fecha AND MASK_ANIO;
19:   aux:=aux>>9;
20:   getAnio:=2000-50+aux;
21:end;
22:

procedimiento setDia

El procedimiento recibe la variable d que representa el día que tenemos que setear en la fecha. Entonces le aplicamos la máscara de día (por las dudas) y luego operamos la fecha y el día con el operador OR. Así asignaremos los bits indicados en d sin alterar los bits contenidos en fecha.

18:
19:procedure setDia(var fecha:word; d:word);
20:var aux:word;
21:begin
22:   aux:=d AND MASK_DIA;
23:   fecha:=fecha OR aux;
24:end;
25:

procedimiento setMes

El mismo análisis: primero corremos los bits 5 posiciones a la izquierda, luego le aplicamos la máscara de mes y por último aplicamos el OR.

10:
11:procedure setMes(var fecha:word; m:word);
12:var aux:word;
13:begin
14:   aux:=m<<5;
15:   aux:=aux AND MASK_MES;
16:   fecha:=fecha OR aux;
17:end;
18:

procedimiento setAnio

Idem anterior pero primero "decodificamos" el año aplicando la fórmula a-2000+50.

 1:
 2:procedure setAnio(var fecha:word; a:word);
 3:var aux:word;
 4:begin
 5:   aux:=a-2000+50;
 6:   aux:=aux<<9;
 7:   aux:=aux AND MASK_ANIO;
 8:   fecha:=fecha OR aux;
 9:end;
10:

TP - Compresor Huffman

2008-05-22T15:50:00.008-03:00

.
Análisis de untSz.pas

Por último analizaremos la unit común a szzip.pas y szunzip.pas en la que se define la sección type y las funciones de manipulación a nivel bit.

untSz.pas

  1:
  2:unit untSz;
  3:
  4:interface
  5:
  6:   // ----------
  7:   // CONSTANTES
  8:   // ----------
  9:
 10:   const
 11:      EXTENSION_COD='.szcod';
 12:      EXTENSION_DAT='.szzip';
 13:      EXTENSION_LEN='.szlen';
 14:
 15:
 16:   // -------------------
 17:   // DEFINICION DE TIPOS
 18:   // -------------------
 19:
 20:   type
 21:
 22:      PNodo = ^Nodo;
 23:      Nodo = record
 24:         c: byte;
 25:         n: comp;
 26:         izq: PNodo;
 27:         der: PNodo;
 28:         sig: PNodo;
 29:      end;
 30: 
 31:      // tipo para array de 16 bytes
 32:      T16b = array[0..15] of byte;
 33:
 34:      // registro para el array
 35:      RArray = record
 36:         n: comp;    // cantidad de ocurrencias
 37:         cod: T16b;  // codigo asignado (max 128 bits)
 38:         nCod: byte; // longitud del codigo (max 128)
 39:      end;
 40: 
 41:      // tipo para el array
 42:      TArray = array[0..255] of RArray;
 43: 
 44:      // tipo para el archivo
 45:      FByte = file of byte;
 46: 
 47:      // registro para el archivo len
 48:      RLen = record
 49:         c:byte;
 50:         n:comp;
 51:      end;
 52: 
 53:      // tipo para el archivo len
 54:      FLen = file of RLen;
 55:
 56:
 57:   // -----------------------
 58:   // DEFINICION DE FUNCIONES
 59:   // -----------------------
 60:
 61:   // retorna 2 a la n
 62:   // ejemplo: potencia2(3) = 8
 63:   function potencia2(n:byte):byte;
 64:
 65:   // dado un byte retorna un string con su 
 66:   // representacion binaria
 67:   // por ejemplo: si b es 36 => b es 00100100 =>
 68:   // byteToBin(b) retorna '00100100'
 69:   function byteToBin(b: byte): string[8];
 70:
 71:   // retorna 1 o 0 segun el bit de la posicion i 
 72:   // sea 1 o 0, contanto desde cero de izquierda a 
 73:   // derecha
 74:   // ejemplo: si b es 25 => b es 00011001 =>
 75:   // getBitAt(b,2) retorna 0
 76:   // getBitAt(b,3) retorna 1
 77:   function getBitAt(b: byte; i: byte): byte;
 78: 
 79:   // setea en 1 o en 0 el bit de la posicion pos en 
 80:   // el byte b, contando de cero a 7 de izquierda 
 81:   // a derecha
 82:   // ejemplo: si b es 0 => b es 00000000 =>
 83:   // setBitAt(b,0,1) retorna 10000000 => 128
 84:   procedure setBitAt(var b:byte; pos:byte; val:byte);
 85:
 86:   // copia en tgt los bites de src contenidos entre 
 87:   // las posiciones desde y hasta (no inclusive) 
 88:   // con un desplazamiento offset
 89:   procedure copiarBits(var tgt: byte;src:byte
 90:                       ;desde,hasta,offset:shortint);
 91:
 92:   // (sobrecarga)
 93:   // iden pero trabajando sobre un T16b. La salida
 94:   // contendra solo los primeros x bits comenzando 
 95:   // a contar desde la izquierda
 96:   function byteToBin(b: T16b; x:byte): string;
 97:
 98:   // (sobrecarga)
 99:   // idem pero trabaja sobre un T16b
100:   function getBitAt(b:T16b; i:byte): byte;
101:
102:   // (sobrecarga)
103:   // iden pero trabajando sobre un T16b
104:   procedure setBitAt(var b:T16b; pos:byte; val:byte);
105:
106:   // asigna ceros a un T16b
107:   procedure setCeros(var b:T16b);
108:
109:   // permite inicializar un T16b en funcion de los
110:   // unos y ceros contenidos en sBin
111:   // ejemplo: si sBin es: '100110011001100'
112:   // entonces asigna exactamente esos unos y ceros
113:   // a tgt (comenzando desde la izquierda y 
114:   // completando con ceros los bits restantes
115:   procedure setBits(var tgt:T16b; sBin:string);
116:
117:
118:   // FUNCIONES PARA DEBUG (se proveen resueltas)
119:
120:   // muestra por pantalla el "contenido" de un 
121:   // nodo ndo mostrando su campo c, n, y si
122:   // sig<>NIL entonces tambien muestra ndo^.sig^.n
123:   procedure mostrarNodo(ndo:PNodo);
124:
125:   // recorre la lista e invoca a mostrarNodo por 
126:   // cada nodo recorrido
127:   procedure mostrarLista(lst: PNodo);
128:
129:   // recorre el arbol en inOrden mostrando el 
130:   // contenido de sus nodos
131:   procedure mostrarArbol(p:PNodo);
132:
133:
134:implementation
135:
136:// :
137:// :
138:// :
139:
140:end.
141:

La función potencia2 (línea 63) recibe un valor n y debe retornar la potencia n-ésima de 2. Por ejemplo si n es 5 retorna 2 "elevado a la" 5 = 32.

En la línea 69 vemos la función byteToBin. Esta función se utiliza para debuggear. Recibe un byte y retorna un string de 8 caracteres "unos y ceros" tal que representen en binario al byte recibido. La función está sobrecargada (ver línea 96) de forma tal que pueda aplicarse tanto a un tipo byte como a un tipo T16b.

En las líneas 77 y 84 se define la funcion getBitAt y el procedimiento setBitAt. La primera recibe un byte y una posición (contando de izquierda a derecha comenzando desde cero) y retorna 1 o 0 según el byte que reciba como parámetro tenga 1 o 0 en dicha posición. La segunda recibe un byte, una posición y un valor 1 o 0 y asigna ese valor en el bit del byte cuya posición se indica en el parámetro (siempre contando desde cero y de izquierda a derecha).

Estas funciones también están sobrecargadas para trabajar con T16b (líneas 100 y 104).

En la línea 89 vemos el procedimiento copiarBits. Basicamente lo que debe hacer es copiar un conjunto de bits de un byte (src) a otro byte (tgt). El conjunto de bits a copiar se delimita por los parámetros desde y hasta. El parámetro offset marca el desplazamiento.

Veamos un ejemplo de como debe funcionar este procedimiento:

   1:
   2:uses untSz;
   3:
   4:var src,tgt:byte;
   5:begin
   6:   src:=231; // 11100111
   7:   tgt:=0;   // 00000000
   8:
   9:   // copio del bit 2 al 6 con offset 0       
  10:   copiarBits(tgt,src,2,6,0);
  11:   writeln( byteToBin(tgt) ); // imprime: 00100100
  12:
  13:   // copio del bit 2 al 6 con offset 2   
  14:   tgt:=0; // vuelvo todo a cero     
  15:   copiarBits(tgt,src,2,6,2);
  16:   writeln( byteToBin(tgt) ); // imprime: 00001001 
  17:
  18:   // copio del bit 2 al 6 con offset -2  
  19:   tgt:=0; // vuelvo todo a cero     
  20:   copiarBits(tgt,src,2,6,-2);
  21:   writeln( byteToBin(tgt) ); // imprime: 10010000    
  22:end.
  23:

En la línea 107 se define el procedimiento setCeros que recibe un T16b para inicializarlo en cero. Recordemos que un T16b no es más que un array de 16 bytes (numerados de 0 a 15) por lo tanto para resolver este procedimiento simplemente hay que recorrer el T16b asignando cero en cada posición.

El siguiente programa utiliza y prueba el funcionamiento de todas las funciones definidas en untSz.pas. El alumno puede utilizarlo como caso de prueba para asegurarse que las funciones están correctamente desarrolladas.

testUntSz.pas

   1:
   2:uses untSz;
   3:
   4:var a,b,pos:byte; h:T16b;
   5:begin
   6:   // ------------------------------
   7:   // testeo de la funcion potencia2
   8:   // ------------------------------
   9: 
  10:   // debe mostrar 64
  11:   a:=6;
  12:   writeln( 'potencia2(',a,') = ',potencia2(a) );
  13:
  14:   // debe mostrar 1
  15:   a:=0;
  16:   writeln( 'potencia2(',a,') = ',potencia2(a) );
  17: 
  18:   // debe mostrar 128
  19:   a:=7;
  20:   writeln( 'potencia2(',a,') = ',potencia2(a) );
  21: 
  22: 
  23:   // ------------------------------
  24:   // testeo de la funcion byteToBin
  25:   // ------------------------------
  26: 
  27:   // debe mostrar '11001001'
  28:   a:=201;
  29:   writeln( 'byteToBin(',a,') = ',byteToBin(a) );
  30:
  31:   // debe mostrar '11111111'
  32:   a:=255;
  33:   writeln( 'byteToBin(',a,') = ',byteToBin(a) );
  34: 
  35:   // debe mostrar '00000000'
  36:   a:=0;
  37:   writeln( 'byteToBin(',a,') = ',byteToBin(a) );
  38:
  39:   // -----------------------------  
  40:   // testeo de la funcion getBitAt
  41:   // -----------------------------
  42: 
  43:   a:=201;
  44: 
  45:   // debe retornar 0
  46:   pos:=3;
  47:   writeln('a=',byteToBin(a),', ',getBitAt(a,pos));
  48:
  49:   // debe retornar 1
  50:   pos:=4;
  51:   writeln('a=',byteToBin(a),', ',getBitAt(a,pos));
  52:
  53:   // debe retornar 1
  54:   pos:=0;
  55:   writeln('a=',byteToBin(a),', ',getBitAt(a,pos));
  56:
  57:   // debe retornar 1
  58:   pos:=7;
  59:   writeln('a=',byteToBin(a),', ',getBitAt(a,pos));
  60:
  61:   // -----------------------------
  62:   // testeo de la funcion setBitAt
  63:   // -----------------------------
  64: 
  65:   a:=0;
  66: 
  67:   // debe mostrar '10000000'
  68:   pos:=0;
  69:   setBitAt(a,pos,1);
  70:   writeln('a=',byteToBin(a));
  71: 
  72:   // debe mostrar '10001000'
  73:   pos:=4;
  74:   setBitAt(a,pos,1);
  75:   writeln('a=',byteToBin(a));
  76: 
  77:   // debe mostrar '00001000'
  78:   pos:=0;
  79:   setBitAt(a,pos,0);
  80:   writeln('a=',byteToBin(a));
  81:
  82:   // -------------------------------------
  83:   // testeo de la funcion byteToBin (T16b)
  84:   // -------------------------------------
  85: 
  86:   // debe mostrar 12 ceros '000000000000'
  87:   setCeros(h);
  88:   writeln('h=',byteToBin(h,12));
  89:
  90:   // -----------------------------------
  91:   // testeo de la funcion setBits (T16b)
  92:   // -----------------------------------
  93: 
  94:   // tiene que mostrar '11100111001110011010000'
  95:   setBits(h,'1110011100111001101');
  96:   writeln('h=',byteToBin(h,23));
  97: 
  98:   // ------------------------------------
  99:   // testeo de la funcion setBitAt (T16b)
 100:   // ------------------------------------
 101:   setCeros(h);
 102: 
 103:   // tiene que mostrar '1000000000'
 104:   setBitAt(h,0,1);
 105:   writeln('h=',byteToBin(h,10));
 106: 
 107:   // tiene que mostrar '1000100000'
 108:   setBitAt(h,4,1);
 109:   writeln('h=',byteToBin(h,10));
 110: 
 111:   // ------------------------------------
 112:   // testeo de la funcion getBitAt (T16b)
 113:   // ------------------------------------
 114: 
 115:   setBits(h,'110011001100');
 116: 
 117:   // debe mostar 1
 118:   pos:=0;
 119:   b:=getBitAt(h,pos);
 120:   writeln('h=',byteToBin(h,15),', ',b);
 121: 
 122:   // debe mostar 0
 123:   pos:=2;
 124:   b:=getBitAt(h,pos);
 125:   writeln('h=',byteToBin(h,15),', ',b);
 126:
 127:   // debe mostar 1
 128:   pos:=4;
 129:   b:=getBitAt(h,pos);
 130:   writeln('h=',byteToBin(h,15),', ',b);
 131:end.
 132:

Luego de desarrollar todas las funciones y compilar este programa la salida debe ser la siguiente:

TP - Compresor Huffman

2008-05-20T00:56:00.025-03:00

.
Análisis del Descompactador

Para descomprimir los archivos la estrategia será la siguiente:

Recomponer el árbol Huffman original.
Recorrer leyendo "bit por bit" el archivo codificado y por cada bit leido bajar un nivel (comenzando desde la raíz) del árbol, a izquierda o a derecha según el bit leido sea 0 o 1. Así hasta llegar a una hoja, lo cual nos indicará que llegamos al caracter que debemos restaurar.
Cada caracter "restaurado" escribirlo en el nuevo archivo de salida que será el mismo que el que se comprimió con el compresor.

Analicemos el código.

szunzip.pas

   1:
   2:uses untSz,untSzzip,untSzunzip;
   3:
   4:var
   5:   archDat:FByte; archCod:FByte;
   6:   b:byte;
   7:   arr:TArray;
   8:   p,aux:PNodo;
   9:   nBytesOri:comp;
  10:   nomArch:string;
  11:   i:integer;
  12:
  13:begin
  14:
  15:   if( paramCount()>0 ) then begin
  16:      nomArch:=paramStr(1);
  17:   end else begin
  18:      write('ERROR: Debe especificar el archivo ');
  19:      writeln('a descomprimir');
  20:      writeln('USAGE: szunzip nombreArchivo');
  21:      exit;
  22:   end;
  23:
  24:   inicializarArray(arr);
  25:
  26:   // levanto el archivo len
  27:   nBytesOri:=leerLen(arr,nomArch+EXTENSION_LEN);
  28:
  29:   // levanto el archivo .cod al array 
  30:   subirArchivoCod(nomArch+EXTENSION_COD,arr);
  31:
  32:   // armo la lista enlazada
  33:   p:=crearLista(arr);
  34:
  35:   // armo el arbol
  36:   listaToArbol(p);
  37:
  38:   grabarArchivo(p,nomArch,nomArch+EXTENSION_DAT
  39:                                      , nBytesOri);
  40:end.
  41:

El programa szunzip.pas recibe en línea de comandos el nombre del archivo original. Por ejemplo: dibujo.bmp. Con este nombre podrá obtener los nombres de los archivos dibujo.szlen, dibujo.szcod y dibujo.szzip.

En la línea 15 verificamos que se haya pasado el nombre del archivo como argumento en línea de comandos y (si no lo pasaron) mostramos un mensaje de error.

En la línea 27 leemos el archivo .szlen con la función leerLen que retorna el tamaño original del archivo. Recordemos que este archivo es un archivo de registros RLen y cada registro contiene la cantidad de ocurrencias de cada caracter que contenia el archivo original.

En la línea 30 "restauramos" el array leyendo el archivo .szcod. Recordemos que este es un archivo de bytes (de tipo FByte) donde el primer byte indica un caracter (valor de 0 a 255), el segundo byte indica el nCod para ese caracter y los siguientes m bytes representan el código Huffman (cod) con el que se codificó al caracter. Así con todos los caracteres codificados.

El procedimiento subirArchivoCod debe leer el archivo .szcod y completar los campos nCod y cod del array arr.

Teniendo el array cargado podemos crear la lista y el árbol Huffman con la función crearLista y el procedimiento listaToArbol que ya analizamos (y programamos) anteriormente (ver líneas 33 y 36).

Por último el procedimiento grabarArchivo (línea 38) lee el archivo .szzip y reescribe el archivo original procesando cada byte (y cada bit) leido.

Analicemos la unit untSzunzip.pas donde se definen e implementan las funciones y procedimientos que utiliza szunzip.pas.

untSzunzip.pas

   1:
   2:unit untSzunzip;
   3:
   4:interface
   5:   uses untSz;
   6:
   7:   // lee el archivo nomArchLen de tipo FLen y carga 
   8:   // el array con los datos que levanta del archivo. 
   9:   // Retorna la cantidad de caracteres que tenia 
  10:   // el archivo original
  11:   function leerLen(var arr:TArray
  12:                   ;nomArchLen:string):comp;
  13:
  14:   // lee el archivo nomArch de tipo FByte respetando 
  15:   // el criterio con el que se grabo: un byte indica 
  16:   // el caracter, luego un byte indica el nCod y 
  17:   // luego m bytes indican el cod, sube estos datos 
  18:   // al array arr
  19:   procedure subirArchivoCod(nomArch:string
  20:                            ;var arr: TArray);
  21:
  22:   // avanza por las ramas del arbol hasta llegar a 
  23:   // una hoja, asi obtiene el caracter original que 
  24:   // corresponde al codigo huffman leido (esta 
  25:   // funcion se provee, no es necesario programarla)
  26:   procedure procesarBits(var arch:FByte; p:PNodo
  27:                         ;var aux: PNodo
  28:                         ;buffer: byte
  29:                         ;var nBytesOri:comp);
  30:
  31:   // recorre el archivo nomArchDat de tipo FByte y
  32:   // por cada byte lo manda a procesar
  33:   // a procesarBits. Este procedimiento utiliza 
  34:   // el procedimiento procesarBits
  35:   procedure grabarArchivo(p: PNodo; nomArch
  36:                          ,nomArchDat: string
  37:                          ;nBytesOri:comp);
  38:
  39:implementation
  40:
  41:// :
  42:// :
  43:// :
  44:
  45:end.
  46:

La función leerLen y el procedimiento subirCod ya fueron explicados.

En la línea 26 aparece la definición del procedimiento procesarBits (cuya implementación se provee con el enunciado). Este procedimiento recibe un byte (leido desde el archivo .szzip) y procesa sus bits, bit por bit desplazándose correctamente por el árbol Huffman hasta llegar al caracter codificado en ese byte. Graba el el caracter en el (nuevo) archivo original y (si quedan bits por procesar en el byte) repite la operación hasta agotar los 8 bits.

El procedimiento grabarArchivo (línea 35) debe recorrer el archivo .szzip y por cada byte leido invocar a procesarBits para que recorra el árbol y recupere (y grabe) el caracter decodificado en el archivo original.

.............................................

TP - Compresor Huffman

2008-05-19T20:51:00.032-03:00

.
Metodología de Trabajo

La implementación del algoritmo puede resultar verdaderamente compleja. Excede por mucho el alcance definido para una materia como "Programación I" o "Algoritmos Y Estructuras de Datos I".

Sin embargo, considero que el alumno puede ser capáz de programar pequeñas funciones y procedimientos con un nivel creciente de complejidad de forma tal que las funciones más simples faciliten el desarrollo del código de las funciones más complejas, y así hasta lograr un programa principal simple, claro y prolijo.

Por esto, el trabajo práctico consiste en desarrollar una serie de funciones con las cuales se podrá compilar el programa principal que se provee como parte del enunciado.

Archivos que se Adjuntan (descargar)

szzip.pas - Programa principal del compresor
untSzzip.pas - Librería de funciones del compresor
szunzip.pas - Programa principal del descompresor
untSzunzip.pas - Librería de funciones del descompresor
untSz.pas - Librería de funciones y tipos de datos comunes
testUntSz.pas - Programa para testear la unit untSz.pas

Análisis del Compactador

El siguiente código corresponde al programa principal del compactador.

szzip.pas

   1:
   2:uses untSz,untSzzip;
   3:
   4:var
   5:   arch:FByte;
   6:   p:PNodo;
   7:   arr:TArray;
   8:   cod:T16b;
   9:   nCod:integer;
  10:   i:integer;
  11:   nomArch:string;
  12:   nSize:comp;
  13:
  14:begin
  15:   if( paramCount()>0 ) then begin
  16:      nomArch:=paramStr(1);
  17:   end else begin
  18:      write('ERROR: Debe especificar el archivo ');
  19:      writeln('a comprimir');
  20:      writeln('USAGE: szzip nombreArchivo');
  21:      exit;
  22:   end;
  23:
  24:   // abro el archivo que vamos a comprimir
  25:   assign(arch,nomArch);
  26:   reset(arch);
  27:
  28:   // inicializo el array
  29:   inicializarArray(arr);
  30:
  31:   // cuento las ocurrencias
  32:   nSize:=contarOcurrencias(arch,arr);
  33:
  34:   // grabo el archivo len
  35:   grabarArchivoLen(arr,nomArch+EXTENSION_LEN);
  36:
  37:   // creo la lista ordenada
  38:   p:=crearLista(arr);
  39:   //mostrarLista(p);
  40:   // crea el arbol a partir de la lista
  41:   listaToArbol(p);
  42:
  43:   // recorre el arbol generando los 
  44:   // codigos a asignar a cada caracter
  45:   setCeros(cod);
  46:   nCod:=0;
  47:   generarCodigos(arr, p, cod, nCod);
  48:
  49:   // graba el archivo de codigos, es el array 
  50:   // en un archivo...
  51:   grabarArchivoCod(arr,nomArch+EXTENSION_COD);
  52:
  53:   // reseteo el archivo para volver a leerlo
  54:   reset(arch);
  55:   grabarArchivoDat(arr,arch,nomArch+EXTENSION_DAT);
  56:
  57:   close(arch);
  58:end.
  59:

Lo primero que hacemos (línea 15) es verificar si nos están pasando como argumento en línea de comandos el nombre del archivo que tenemos que comprimir. Si no nos pasan este valor entonces mostramos un mensaje de error y una sugerencia sobre como se debe utilizar el programa.

En línea de comandos nos pasan el nombre del archivo a comprimir. Recordemos que tenemos que recorrerlo una vez para contar la cantidad de ocurrencias de cada caracter y luego recorrerlo por segunda vez para reemplazar cada caracter por su códificación Huffman correspondiente.

Tenemos un array (arr) de registros RArray en el que vamos a contar las ocurrencias de los diferentes caracteres del archivo. El array es de 0 a 255 posiciones y utilizaremos el mismo código ASCII del caracter como índice de acceso al array. En la línea 29 invocamos a la función inicializarArray para asignar cero al campo n de cada RArray y setear ceros en el campo cod (recordemos que es de tipo T16b).

La función contarOcurrencias (línea 32) recorre el archivo para contar cuantas veces aparece cada caracter, incrementa el campo n de los registros del array y retorna la cantidad total de caracteres leidos. Es decir: retorna el size (en bytes) del archivo que estamos procesando.

El objetivo de este trabajo práctico es entender e implementar una solución que permita comprimir y descomprimir archivos en base a la codificación Huffman. Para evitar que el alumno tenga que entrar en cuestiones y detalles ajenos a esto optamos por generar tres archivos de salida que contendrán la tabla de ocurrencias, los códigos Huffman y la información (codificada) contenida en el archivo original.

Por ejemplo: si el archivo que vamos a comprimir es dibujo.bmp entonces, luego de correr el compresor (szzip.exe) tendremos los siguientes archivos:

dibujo.bmp.szlen - Contiene registros RLen con la cantidad de ocurrencias de cada caracter.
dibujo.bmp.szcod - Contiene la codificación Huffman asignada a cada caracter.
dibujo.bmp.szzip - Contiene la información de dibujo.bmp codificada.

En la línea 35 invocamos al procedimiento grabarArchivoLen que recibe el array y el nombre del archivo que va a generar. Recordemos que en nomArch tenemos el nombre del archivo original (en nuestro ejemplo es "dibujo.bmp") entonces la expresión:

nomArch+EXTENSION_LEN

será la concatenación de "dibujo.bmp" más ".szlen" (veremos más adelante que EXTENSION_LEN es una constante definida en untSz.pas que contiene el string ".szlen").

El procedimiento grabarArchivoLen recibe el array y el nombre del archivo a generar. Simplemente debe recorrer el array y para cada caracter que tenga al menos una ocurrencia en el archivo generamos un registro RLen y lo grabamos en el archivo de salida.

El archivo .szlen contendrá la cantidad de ocurrencias de cada caracter contenido en el archivo original.

En la línea 38 invocamos a la función crearLista que recibe el array y retorna un puntero al primer nodo de una lista enlazada cuyos nodos serán del tipo Nodo. La lista resultante estará ordenada ascendentemente por cantidad de ocurrencias y por código ASCII del caracter.

En la línea 41, el procedimiento listaToArbol "convierte" la lista en un árbol según se explicó anteriormente de forma tal que (ahora) p apunta a la raíz del árbol Huffman.

En la línea 47 el procedimiento generarCodigos (se provee con el enunciado en untSzzip.pas) recorre el árbol apuntado por p y asigna en los campos cod del array los códigos Huffman correspondientes.

Con los códigos Huffman generados solo queda grabarlos en un archivo con extensión .szcod (línea 51) y luego codificar y la información y grabarla codificada en un archivo con extensión .szzip (línea 55).

Todas las funciones y procedimientos que utilizamos en szzip.pas están definidas e implementadas en la unit untSzzip.pas que analizaremos a continuación.

untSzzip.pas

   1:
   2:unit untSzzip;
   3:
   4:
   5:interface
   6:   uses math, untSz;
   7:
   8:   // -----------------------
   9:   // DEFINICION DE FUNCIONES
  10:   // -----------------------
  11:
  12:   // asigna cero a cada elemento del array 
  13:   procedure inicializarArray(var arr:TArray);
  14:
  15:   // recorre el archivo byte por byte, utilizando 
  16:   // el byte leido para acceder directo a la 
  17:   // posicion que corresponda en el array e 
  18:   // incrementar el contador (ubicado en dicha 
  19:   // posicion) 
  20:   // retorna la cantidad de bytes leidos del archivo
  21:   function contarOcurrencias(var arch:FByte
  22:                              ;var arr:TArray):comp;
  23:
  24:   // graba un archivo de tipo FLen que contiene un 
  25:   // registro RLen por cada caracter contenido en 
  26:   // el array cuyo n sea mayor que cero
  27:   procedure grabarArchivoLen(arr:TArray
  28:                             ;nomArchLen:string);
  29:
  30:   // inserta un nodo en una lista respetando un 
  31:   // orden ascendente por el campo n y (si hay 
  32:   // nodos con igual n) por codigo ASCII
  33:   procedure insertarOrdEnLista(var lst, ndo: PNodo);
  34:
  35:   // recorre el array y para cada posicion con n 
  36:   // mayor que cero crea un nodo asignando en su 
  37:   // campo c el valor del byte representado por la 
  38:   // posicion del array y en su campo n el valor 
  39:   // contenido en el array en dicha posicion. 
  40:   // Crea una lista de nodos ordenada por el campo 
  41:   // n de menor a mayor y retorna un puntero al 
  42:   // primer nodo de la lista 
  43:   // (utilizar el procedimiento insertarOrdEnLista)
  44:   function crearLista(arr:TArray):PNodo;
  45:
  46:   // retorna un puntero al (hasta ahora) primer 
  47:   // nodo de la lista e incrementa el puntero lst
  48:   // haciendo que apunte al segundo nodo.
  49:   // si la lista tiene un unico nodo entonces 
  50:   // retorna un puntero a este
  51:   // nodo y hace que lst apunte a NIL
  52:   function sacarPrimerNodo(var lst:PNodo):PNodo;
  53:
  54:   // recorre la lista (que esta ordenada de menor a 
  55:   // mayor por el campo n) toma los dos primeros 
  56:   // nodos, y crea un nuevo nodo 
  57:   // con n = n1^.1+n2^.n y c = 255. Como hijo der. 
  58:   // del nuevo nodo asigna a n1 y como hijo izq
  59:   // asigna a n2. Luego inserta ordenado el nuevo 
  60:   // nodo en la lista.
  61:   // (utiliza la funcion sacarPrimerNodo y el 
  62:   // procedimiento insertarOrdEnLista)
  63:   procedure listaToArbol(var p:PNodo);
  64:
  65:   // recorre el arbol generando el codigo que le 
  66:   // corresponde a cada hoja y cuando llega a una 
  67:   //hoja asigna el codigo y su longitud en el array
  68:   // este procedimiento se provee completo, no es 
  69:   // necesario desarrollarlo
  70:   procedure generarCodigos(var arr:TArray
  71:                           ;var p:PNodo
  72:                           ;var cod:T16b; nCod:byte);
  73:
  74:   // genera un archivo FByte con la informacion 
  75:   // contenida en el array,de la siguiente manera: 
  76:   // por cada posicion del array con n>0 graba en 
  77:   // el archivo: 1 byte con el codigo ASCII del 
  78:   // caracter 1 byte con el nCod del caracter
  79:   // n bytes con los primeros bytes significativos 
  80:   // del cod por ejemplo: si el nCod es de 5 
  81:   // entonces el cod tiene un unico byte 
  82:   // significativo, pero si nCod es 12 entonces cod 
  83:   // tiene 2 bytes significativos
  84:   procedure grabarArchivoCod(arr:TArray
  85:                             ;nomArchCod:string);
  86:
  87:   // este procedimiento se provee completo, no es 
  88:   // necesario desarrollarlo
  89:   procedure grabarBits(var archDat:FByte; cod:T16b
  90:                       ;nCod:byte; var buffer:byte
  91:                       ;var tamBuff:byte);
  92:
  93:   // recorre el archivo arch (que ya viene 
  94:   // reseteado), abre el archivo cuyo nombre es 
  95:   // nomArchDat de tipo FByte y recorrer arch. 
  96:   // Por cada caracter leido busca en el array su 
  97:   // cod y e invoca al procedimiento grabarBits 
  98:   // para que se ocupe de grabar el codigo 
  99:   // bufferizando
 100:   // (utiliza el procedimiento grabarBits)
 101:   procedure grabarArchivoDat(arr: TArray
 102:                             ;var arch:FByte
 103:                             ;nomArchDat:string);
 104:
 105:
 106:implementation
 107:
 108:// :
 109:// :
 110:// :
 111:
 112:end.
 113:

El procedimiento inicializarArray (línea 13) simplemente debe recorrer el array arr y asignar cero al campo n ya que luego, cuando contemos las ocurrencias de los caracteres, solo consideraremos aquellas posiciones del array cuyo campo n sea mayor que cero.

La función contarOcurrencias (línea 21) debe recorrer el archivo arch y por cada byte leido acceder al array arr para incrementar su campo n. Esta función debe retornar la cantidad de bytes leidos del archivo que, como leerá el archivo completo, coincide con el tamaño del archivo expresado en bytes.

Como ya mencionamos, para realizar la codificación y (sobre todo) para poderla decodificar será necesario almacenar además la cantidad de ocurrencias de cada caracter. Esto lo haremos en un archivo separado cuya extensión será ".szlen" (se definió arbitrareamente).

El archivo .szlen debe ser un archivo de registros RLen y debe contener un registro por cada caracter diferente contenido en el archivo que estamos procesando (o comprimiendo). Según lo analizado más arriba esto lo podemos distinguir facilmente porque serán aquellos caracteres cuyo campo n en el array arr será igual a cero. Este trabajo lo realiza el procedimiento grabarArchivoLen (línea 27).

En las líneas 33 y 44 definimos los procedimientos insertarOrdenadoEnLista y crearLista con los cuales crearemos una lista enlazada de nodos tipo Nodo con la información contenida en el array arr. La idea es: en crearLista recorrer el array arr y por cada caracter cuyo n sea mayor que cero invocar a insertarOrdenadoEnLista para que inserte en la lista un nodo en representación de ese caracter.

En la línea 52 la función sacarPrimerNodo "desenlaza" y retorna un puntero al primer nodo de la lista que, como es una lista ordenada ascendentemente por cantidad de ocurrencias y por código ASCII, será el nodo correspondiente al caracter menos ocurrente. La función desenlaza el nodo pero no lo libera (no le hace dispose) ya que ese mismo nodo pasará a ser una hoja del árbol Huffman que crearemos con el siguiente procedimiento.

El procedimiento listaToArbol (línea 63) debe recorrer la lista mientras p (primer nodo de la lista) no tenga siguiente elemento. Por cada iteración sacamos el primer nodo de la lista, y luego volvemos a sacar el primer nodo de la lista (tenemos los dos menos ocurrentes). Creamos un nuevo nodo con n = a la suma de los n de los dos nodos que sacamos, asignamos cualquier valor a c y colocamos los dos nodos que sacamos de la lista como hijos derecho y izquierdo. Luego invocamos al procedimiento insertarOrdenado para que inserte el nuevo nodo (que ya es un pequeño árbol binario) en la lista.

En la línea 70 se define el procedimiento generarCodigos. Este procedimiento se provee completo y, dada su complejidad, no se espera que lo desarrolle el alumno.

Basicamente se trata de un recorrido en orden inverso sobre el árbol "acumulando" unos o ceros en cada llamada recursiva, según se esté accediendo al hijo derecho o izquierdo respectivamente.

En la línea 84 se define el procedimiento generarArchivoCod. Este procedimiento debe generar el archivo que contiene los códigos Huffman que (a través del árbol) asignamos a cada caracter. El archivo tendrá extensión ".szcod" y será un archivo de bytes (tipo FByte) con la siguiente estructura: por cada caracter con n mayor que cero grabaremos 1 byte con el caracter, 1 byte con su nCod y m bytes para grabar el código Huffman asociado al caracter. Recordemos que este código puede tener (en el peor de los casos) hasta 16 bytes. El valor m lo calculamos dividiendo el nCod del código del caracter por 8.

m = nCod div 8 + 1

Es decir: si nCod es 6 (seis bits) entonces nCod div 8 será cero, más 1 será 1: utilizamos solo un byte para almacenar ese cod. Pero si nCod es 14 entonces nCod div 8 será 1, más 1 es 2. Para almacenar un código de longitud 14 necesitaremos utilizar 2 bytes.

.............................................

TP - Compresor Huffman

2008-05-19T19:46:00.019-03:00

.
Implementación Del Algoritmo

Entrategia

La estrategia que proponemos para implementar un compresor (y luego un descompresor) de archivos basado en el algoritmo de Huffman es la siguiente.

1 - Recorrer el archivo que vamos a comprimir y contar cuantas veces aparece cada caracter. Utilizaremos un array de 0 a 255 posiciones ya que cada caracter (o mejor dicho cada byte) que leamos seguro estará dentro de ese rango.

2 - Crearemos (a partir del array del paso 1) una lista enlazada, ordenada por la cantidad de ocurrencias y (si es necesario) por el código ASCII del caracter (en caso de que existan caracteres con la misma probabilidad de ocurrencia).

3 - Procesaremos la lista para obtener el árbol Hufman.

4 - Procesamos el árbol para obtener los códigos Hufman y los nCod de los caracteres que componen el archivo que queremos comprimir. Los asignamos en el array.

5 - Volvemos a recorrer el archivo y escribimos en un nuevo archivo el código Hufman que reemplaza a cada caracter leido.

En si, la estrategia parece simple. De hecho es bastante lógica, pero lamentablemente nos encontraremos con algunas dificultades que le darán condimento a la resolución de este trabajo práctico.

Estructuras de Datos y Sección type

   1:
   2:   // array de 16 bytes, lo usaremos para
   3:   // almacenar un codigo huffman de hasta 128 bits
   4:   T16b = array[0..15] of byte;
   5:
   6:   RArray = record
   7:      n: comp;    // cantidad de ocurrencias
   8:      cod: T16b;  // codigo huffman (max 128 bits)
   9:      nCod: byte; // longitud del codigo (max 128)
  10:   end;
  11:
  12:   // tipo para el array
  13:   TArray = array[0..255] of RArray;
  14:

En este fragmento de la sección type vemos el registro RArray y el tipo TArray. Este es el tipo que define el array que utilizaremos como tabla para contar las ocurrencias de cada caracter y (luego) asignar el código Huffman y su longitud asociado a cada caracter.

Notemos que no necesitamos un campo para almacenar el caracter en si ya que utilizaremos la posición del array como código ASCII del caracter. Es decir: si tenemos que codificar una "A" utilizaremos la posición 65 del array. Si tenemos que codificar una "C" utilizaremos la posición 67, y así.

Aquí aparece el primer problema:

El árbol Huffman puede tener a lo sumo: (n+1)/2 niveles siendo n la cantidad de símbolos que pueden aparecer en el archivo. Como estamos considerando todos los caracteres (desde 0 hasta 255) resulta que (en el peor de los casos) el árbol Huffman podrá llegar a tener 128 niveles. Es decir: podremos llegar a tener un código de hasta 128 bits (o 16 bytes).

Si el código más largo fuese de (por ejemplo) 8 bits entonces podríamos utilizar un tipo de datos byte para almacenarlo. Si fuese de 16 bits podríamos utilizar un tipo word. Pero no existe ningún tipo entero de 16 bytes así que lo tendremos que "inventar". Lo llamamos T16b (tipo de 16 bytes) y lo implementamos sobre un array de 16 bytes (numerados de 0 a 15).

Veamos ahora el tipo para definir el nodo con el que implementaremos la lista enlazada y luego el árbol de Huffman.

   1:
   2:   // puntero a nodo
   3:   PNodo = ^Nodo;
   4:
   5:   // nodo con el que implementaremos la lista
   6:   // enlazada y (luego) el arbol huffman
   7:   Nodo = record
   8:      c: byte;       // caracter
   9:      n: comp;       // cantidad de ocurrencias
  10:      izq: PNodo;    // hijo izquierdo del nodo
  11:      der: PNodo;    // hijo derecho del nodo
  12:      sig: PNodo;    // puntero al siguiente
  13:   end;
  14:

Como vemos el mismo nodo nos servirá para las dos estructuras. Por eso tiene los campos izq y der (para implementar el árbol binario) y el campo sig (para implementar la lista enlazada).

Notemos que el campo n lo definimos de tipo comp. Esto se debe a que (como ya vimos) el nodo raíz del árbol tendrá una probabilidad de ocurrencia igual a la cantidad de caracteres del archivo que estemos procesando por lo tanto, si el archivo fuese muy grande (por ejemplo 100 MB) el campo n deberá soportar un valor de 1*1024*1024*100 = 1024 a la 2 por 100 = 104.857.600.

Solo queda por definir los tipos para los archivos que utilizaremos:

   1:
   2:   // registro para el archivo len (lo analizaremos
   3:   // mas adelante)
   4:   RLen = record
   5:      c:byte;
   6:      n:comp;
   7:   end;
   8:
   9:   // tipo para el archivo len
  10:   FLen = file of RLen;
  11:
  12:   // tipo para el archivo a comprimir y para el
  13:   // archivo comprimido: simplemente un archivo
  14:   // de bytes
  15:   FByte = file of byte;
  16:

Los tipos RLen y FLen los analizaremos más adelante, cuando sea necesario. El tipo FByte representa un archivo de bytes y nos permitirá leer cualquier tipo de archivo ya que, en definitiva, cualquier archivo no es más que una sucesión de bytes.

.........................,...................

TP - Compresor Huffman

2008-05-19T18:12:00.025-03:00

.
Ejemplo Completo de Codificación Huffman

Recordemos la frase que vamos a codificar:

COMO COME COCORITO COME COMO COSMONAUTA

Luego de contar la cantidad de ocurrencias de cada caracter creamos una lista ordenada de menor a mayor por cantidad de ocurrencias y por código ASCII como vemos a continuación:

En la lista vemos que si bien los caracteres I, N, R, S y U tiene una probabilidad de ocurrencia igual a 1, el orden en que fueron insertados respeta su código ASCII (que además coincide con el orden alfabético)

Con la lista armada, procesamos (e insertamos) los nodos I(1) y N(1):

Procesamos (e insertamos) los nodos R(1) y S(1):

Ahora procesamos U(1) y A(2):

Ahora E(2) y T(2):

Ahora *1(2) y *2(2):

Ahora *3(3) y *4(4):

Procesamos *5(4) y ESP(5):

Ahora será: M(5) y C(7):

Procesamos *6(7) y *7(9):

Ahora será O(11) y *8(12):

Por último procesamos *9(16) y *10(23):

Problema 8.3

2008-05-01T11:20:00.016-03:00

.
Enunciado
Una empresa con estructura "piramidal" requiere un programa que le permita procesar la liquidación de comisiones originadas por las ventas que realizaron los diferentes socios. Para esto cuenta con los siguientes archivos.

SOCIOS.dat (ordenado por fechaIngreso)

idSocio - 8 dígitos
nombre - string[30]
idSocioRef - 8 dígitos
fechaIngreso - ddmmaaaa
ultLiq - single (importe de la última liquidación)
acumLiq - double (acumulado de liquidaciones)

Este archivo contiene la información de los socios (vendedores) de la empresa. Cada socio fue referido (o reclutado) por otro socio. Esto lo refleja el campo idSocioRef. El "primer" socio (el presidente de la empresa) tendrá un idSocioRef con valor -1.

VENTAS.dat (sin orden)

idSocio
importe

Este archivo contiene el importe acumulado en el mes por las ventas de cada socio.

La política de liquidación por ventas que aplica la empresa es la siguiente: a cada socio le corresponde el 70% de sus ventas. Del 30% restante, el 70% le corresponde al socio que lo refirió y el 30% le corresponde al que refirió al que lo refirió, y así sucesivamente.

Se pide desarrollar un programa que:

1 - Imprima un listado ordenado por idSocio indicando su nombre, fecha de ingreso, liquidación anterior, última liquidación (la actual), porcentaje de incremento/decremento y total acumulado desde su ingreso.

2 - Actualice el archivo SOCIOS.dat actualizando los valores de los campos ultLiq y acumLiq.

Análisis
Antes de comenzar vamos a plantear un ejemplo de como se deben liquidar las comisiones por ventas.

El siguiente gráfico representa un ejemplo de la estructura piramidal de la empresa.

En este ejemplo vemos que Pablo, Marcos y Ana son referidos de Juan. Pedro y Martín son referidos de Pablo y José es referido de Ana. Marcos, Pedro, Martín y José no refirieron a ningún socio (no trajeron nuevos vendedores a la empresa).

Ahora supongamos que las ventas del mes fueron las siguientes:

Pedro: $300
Martín: $500
José: $250
Pablo: $600
Marcos: $100
Ana: $250
Juan: $200

Entonces:

De los $300 de Pedro $210 (el 70%) le corresponden a él. De los $90 restantes $63 (el 70%) le correspondes a Pablo y los $27 restantes le corresponden a Juan.

De los $500 de Martín $350 serán para él. De los $150 restantesn $105 serán para Pablo y $45 para Juan.

De los $250 de José solo te tocan a él $175. De los $75 restantes $52.5 serán para Ana y $22.5 serán para Juan.

De las ventas de Pablo, Marcos y Ana el 70% les corresponde a cada uno de ellos y el 30% le corresponden a Juan.

A Juan le corresponde el 100% de sus ventas ya que no es referido de nadie. Es "el presidente" de la empresa y, como dice el refrán: "Del pasado hasta el presente la plata es para el presidente".

Es decir: los ingresos de cada socio (ventas más comisiones) se calculan como el 70% de sus ventas más el 30% de los ingresos de sus referidos directos.

Luego de este análisis podemos plantear la estrategia y las estructuras de datos para resolver el problema de manera óptima.

La estrategia con la que resolveremos el problema será la siguiente:

1 - Indexar el archivo SOCIOS.dat en un árbol binario de búsqueda (ABB) ordenado por idSocio donde cada nodo tendrá la posición del registro en el archivo, un acumulador, el idSocioRef (idSocio del "padre" o socio que lo refirió y el puntero al los dos hijos (es un árbol binario).

2 - Recorrer el archivo VENTAS.dat y por cada registro "hacer la liquidación". Este proceso será recursivo ya que implica buscar en el ABB el nodo que corresponde al socio cuyas ventas estamos procesando, asignarle el 70% del importe y luego "hacer la liquidación" con su idSocioRef (idSocio de su padre) y el 30% restante del importe.

3 - Luego de procesar las ventas (punto 2) recorrer el ABB con un recorrido de Orden Inverso para "ver" los registros ordenados por idSocio, acceder directamente a cada registro del archivo de socios y (por cada socio) imprimir una línea del listado ya que (luego de acceder al archivo) tendremos todos los datos que necesitamos mostrar:

Nombre, Fecha de Ingreso y Liq. Anterior los obtenemos luego del acceso directo al archivo de socios.
Ultima Liquidación lo tenemos en el campo acumulador del nodo del árbol.
Porcentaje de Incremento/Decremento es una relación entre la última liquidación y la liquidación actual, y
Total Acumulado desde su Ingreso es el campo acumLiq del archivo de socios más la última liquidación.

Luego de imprimir actualizamos el archivo de socios.

Con esto podemos plantear la sección type y el programa principal.

   1:
   2:type
   3:   // registro del archivo de socios
   4:   RSocio = record
   5:      idSocio: longint;
   6:      nombre: string[30];
   7:      idSocioRef: longint;
   8:      fechaIngreso: longint;
   9:      ultLiq: single;
  10:      acumLiq: double;
  11:   end;
  12:
  13:   // archivo de socios
  14:   FSocios = file of RSocio;
  15:
  16:   // registro del archivo de ventas
  17:   RVenta = record
  18:      idSocio: longint;
  19:      importe: single;
  20:   end;
  21:
  22:   // archivo de ventas
  23:   FVentas = file of RVenta;
  24:
  25:   // nodo y puntero del ABB
  26:   PArbol = ^NArbol;
  27:   NArbol = record
  28:      idSocio: longint;
  29:      pos: longint;
  30:      idSocioRef: longint;
  31:      acum: single;
  32:      izq: PArbol;
  33:      der: PArbol;
  34:   end;
  35:

El programa principal refleja la estrategia planteada y lo vemos a continuación.

Como vemos, el programa principal es suficientemente claro. Abrimos los archivos y luego indexamos el archivo de socios con la función indexarSocios que devuelve un puntero a la raíz del ABB. Luego recorremos el archivo de ventas y por cada venta mandamos a "procesar la liquidación".

Luego el procedimiento listarYActualizar debe recorrer el ABB con un recorrido de orden inverso y por cada nodo acceder directamente al archivo de socios para listar y luego actualizar los importes de la última liquidación y el acumulado.

El procedimiento liquidar recibe el puntero al ABB, el idSocio que estamos liquidando y el importe de sus ventas. Basicamente lo que debe hacer es buscar al socio en el ABB, acumular el 70% de su importe e invocarse recursivamente con el 30% restante y el idSocioRef. Así hasta llegar al socio cuyo idSocioRef es -1.

El procedimiento buscarSocio busca el idSocio en el ABB. Lo analizaremos más adelante.

Siguiendo con el programa principal analizaremos el procedimiento listarYActualizar.

Como vemos, este procedimiento simplemente hace un recorrido de orden inverso sobre el ABB y por cada nodo invoca al procedimiento procesar quien imprime una línea del listado y luego actualizar el registro del archivo de socios.

Veamos ahora la función indexarSocios.

En esta función recorremos el archivo de socios y agregamos los datos de cada registro del archivo a un nodo en un ABB. Para agregar el nodo utilizamos el procedimiento que desarrollamos a continuación. Este procedimiento recibe la raíz del ABB, el registro con los datos que utilizaremos para completar la información el nodo y la posición (pos) del registro dentro del archivo.

Por último, tenemos que desarrollar la función buscarSocio que utilizamos en el procedimiento liquidar.

La función buscarSocio recibe el puntero al ABB y la clave (idSocio) por la cual buscar. Recordemos que un ABB (árbol binario de búsqueda) el criterio con el que se almacena la información es el siguiente:

si es menor está a la izquierda
si es mayor está a la derecha

Con esta premisa entonces primero preguntamos si el valor que buscamos (idSocio) es menor que el valor del nodo actual (p^.idSocio). Si es así entonces tenemos que repetir la operación considerando al hijo izquierdo del nodo p ya que (por definición) si es menor estará ubicado a la izquierda. Si no es menor entonces preguntamos si es mayor. Si es así entonces repetimos la operación pero considerando al hijo derecho de p. Si no entonces será igual y lo que retornamos es el mismo p.

Algoritmos y Estructuras de Datos UTN - UBA

.