Hace unos días se convocó al reto de hallar cuántas palabras diferentes tenía el Quijote, la obra de Cervantes, además de hallar la frecuencia de cada una de estas palabras. El reto, para un programador novicio puede parecer muy complicado, porque además se pide realizarlo en el menor tiempo posible. ¿Cómo se programa pues algo así?
Aquí la problemática se centra en la estructura de datos a usar. Por ejemplo, imaginemos que queremos usar un arreglo de palabras para irlas acomodando en la medida que las voy leyendo. El primero problema con esto es que no sabemos el total de palabras que hay por lo cual ¿De qué tamaño voy a hacer mi arreglo? Bueno, si el Quijote (como esá en el
Proyecto Gutenberg) tiene unas 2 millones de letras, es razonable pensar que un 20% máximo serán palabras, más o menos 400 mil palabras.
Podemos crear un arreglo de 400,000 palabras y esperemos que esto sea suficiente, aunque en principio, sino sabemos cuantas palabras hay, estamos "adivinando" considerando que el promedio de letras de las palabras del español es menos de 10 letras por palabra. Pero esto último es una grosera aproximación a la cual estamos obligados si queremos usar la estructura de datos llamada
arreglo.
Pero hay otra opción:
usar estructuras de datos dinámicas. En este tipo de estructuras, lo que intentamos hacer es ir creando, en la medida de las necesidades, las estructuras necesarias, las cuales pueden crecer en la medida que lo vamos requiriendo. Dicho de otra manera, si necesitamos una nueva variable para alojar un dato, creamos esa variable en tiempo de ejecución, en el momento, de forma dinámica pues.
Una estructura de datos dinámica, muy poderosa, es la de los áerboles binarios. En una estructura de esta naturaleza tenemos un nodo y dos ramas. En el nodo tenemos la información y en las ramas tenemos apuntadores a otros nodos o bien a NIL, el vacío (es una manera en cómputo de no apuntar hacia la nada).
La técnica para ir creando un árbol binario es así: Consideremos que tenemos una lista de números desordenada: 60, 41, 74, 16, 53, 65, 25, 46, 55, 63, 70, etcétera. Tomemos el valor y pongámoslo en el nodo raíz. Ahora tomemos el siguiente valor, en este caso el 41. Si el valor es menor al que está en el nodo raíz, entonces lo colocamos en la rama izquierda, si es mayor, lo colocamos en la rama derecha., Así, ponemos el 41 en la rama izquierda. Acto seguido tenemos el 74. ¿Dónde lo pondremos? En la rama derecha del nodo raíz. Muy bien hasta aquí, pero de pronto tenemos un número más, el 16. ¿Dónde habremos de ponerlo? Tomamos el nodo raíz y vemos que es 60, así que debe ir en la rama izquierda, pero ésta ya tiene el nodo 41. De nuevo entonces vemos que el 16 es menor que el 41 y lo colocamos en la rama izquierda de éste. Con este procedimiento podemos llegar a llenar el árbol binario (porque solamente tiene dos ramas en cada nodo).
Nótese que un árbol de esta naturaleza además nos da una manera intrínseca de ordenar información. Si queremos desplegar los números que están en este árbol de manera que queden ordenados de menor a mayor, lo que hacemos es muy simple: Partimos del nodo raíz y nos movemos hasta la última rama izquierda posible. Esto nos dará, de acuerdo a la imagen que hemos puesto, en el número 16. Entonces vemos si este nodo tiene rama derecha. Sí, la tiene, y es el 25. Entonces ponemos como primer nímero el 16 y después el 25. Nos hacemos un nodo atrás y hallamos el 41. Lo ponemos. vemos si tiene rama derecha. Sí, la tiene, es el 53, pero éste tiene una rama izquierda, que es el 46 y este nodo a su vez tiene la rama izquierda cone l valor 42. Entonces ponemos el 42, 46, 53 y ahora revisamos la rama derecha y hallamos que hay un 55. Por lo tanto la lista va quedando así: 16, 25, 41, 42, 46, 53, 55... Y ahora ya no hay más ramas izquierdas que revisar. Pasamos a la rama derecha del nodo raíz y hallamos que hay un 74. Pero éste tiene un nodo izquierdo, el 65, que a su vez tiene otro, el 63, que a su vez tiene otro más, el 62, por lo que pondremos, 62, 63 y ahora vemos si hay nodo derecho. Y sí, lo hay, el 64. Ponemos ahora el 65 y como tiene rama derecha, ponemos el 70 y finalmente el 74.
Si queremos ordenar el árbol de los números mayores a los menores, lo que tenemos que hacer es recorrer el árbol al revés, primero empezar por la rama derecha. Esto es increíble. La misma estructura nos permite ya dejar ordenados literalmente los datos sin necesidad de otras estructuras.
Pues bien, una vez que tenemos esto aclarado, podemos crear un árbol binario con las palabras del Quijote. Si es una nueva palabra, creamos el primer nodo. Si es una palabra que es menor que la palabra que está en el nodo raíz, la ponemos en un nuevo nodo, que cuelga de la rama de la izquierda, en caso contrario, de la rama derecha.
Pero ¿cómo puedo crear una estuctura de un árbol binario? La manera más simple es crear una estructura dinámica, que crece en la medida que lo necesitamos. Por ejemplo, en Delphi, (Pascal) primero definiremos la estructura arbórea:
nodoptr = ^nodo; //el apuntador del nodo apunta a un nodo
nodo = record //esta es la definición del nodo
algúndato: string; //palabra a guardar
izquierda, derecha: nodoptr;
end;
Esta definición siempre parece costar trabajo leerla, y la razón es que es la única vez que Pascal permite usar algo que aún no hemos definido. Así,
nodoptr = ^nodo; pero nodo no ha sido aún definido. De hecho, se define inmediatamente después.
Una vez teniendo la estructura dinámica, Delphi (Pascal), nos permite crear una nueva instancia de la misma si la necesitamos.
Por ejemplo, definamos
var
arbol : nodoptr;
Esto es precisamente el árbol en donde iremos colocando las palabras que vayamos leyendo del Quijote. Necesitamos para ello, un procedimiento para insertar nuevos nodos y poner los valores en los mismos. Esto lo podemos hacer así:
procedure insertaarbol(astr: string; var tree: nodoptr);
{ este procedimiento crea el árbol binario en memoria,
insertando un nodo en la posición correcta }
begin
if tree = nil then //si el árbol esta vacío...
begin
new(tree);
tree^.algundato := astr;
tree^.left := nil;
tree^.right := nil;
end
else
begin
if astr > tree^.algundato then
insertaarbol(astr, tree^.right);
if astr < tree^.algundato then
insertaarbol(astr, tree^.left);
end;
end;
Con esto ya tenemos con qué trabajar. Es la rutina imprescindible para ir creando loas nodos (con sus respectivas ramas izquierda y derecha). Ahora hagamos la tarea: leamos el archivo del quijote, que está separado por líneas. Cada línea puede contener un número finito de palabras. He aquí el código (que se echa a andar cuando damos click al botón):
procedure TForm1.Button1Click(Sender: TObject);
var
Linea : ansistring;
Palabra : ansistring;
j : integer;
begin
arbol := nil;
assignfile(afile, Path+'palabras.txt');
//donde vamos a guardar las palabras halladas
rewrite(afile);
assignfile(infile, Path+'quijote-sin.txt');
//que archivo vamos a leer
reset(infile);
j := 0;
repeat
Readln(infile,Linea); //leo línea del texto
for i := 1 to WordCnt(Linea) do
begin
Palabra := ExtractWords(i,1,Linea);
Palabra := Lower(Palabra);
inc(j);
insertararbol(Palabra, arbol);
end;
until eof(infile); //hasta que leamos todo el texto
writeouttree(tree); //escribimos a disco el árbol
//writeln;
closefile(afile);
closefile(infile);
deletetree(tree); //borramos la estructufra binaria
ShowMessage('Hay' + inttostr(j)+ ' palabras diferentes en el Quijote');
end;
Esto nos indica que el Quijote tiene 384,123 palabras en total (¿diferentes? unas 30 mil). El programa crea un archivo con todas las palabras (una por línea) y las despliega en orden alfabético, de menor a mayor, de la A a la Z, pues.
La rutina que crea este archivo es la siguiente:
procedure writeouttree(tree: nodoptr);
{Copia a disco el árbol binario ya ordenado }
begin
if tree <> nil then
begin
writeouttree(tree^.left);
writeln(afile, tree^.algundato) //escribe en archivo
writeouttree(tree^.right);
end;
end;
Nótese que esta es una rutina recursiva (se llama a sí misma), que permite imprimir todas las palabras diferentes del Quijote en un archivo.
¿Cuánto creen que tarda en esta labor? ¡Alrededor de un segundo!
El reto propuesto es más interesante. No basta con saber cuáles son las palabras diferentes en total que tiene el Quijote, sino también su frencuencia. Aquí necesitamos entonces hacer dos cosas. La primera es que el nodo contenga no sólo la palabra del texto, sino las veces que la vamos encontrando, algo así como una variable que vaya incrementándose cada vez que encontremos dicha palabra. Por ello, requerimos de un procedimiento más: uno que busque un nodo y pueda modificar los valores del mismo.
No lo voy a hacer aquí. Si el amable lector me ha seguido hasta este punto, seguro puede hacer fácilmente esta rutina ¿verdad?
