El árbol de enlace componente léxico-texto

La estructura utilizada para representar la asociación entre el texto y los componentes léxicos, que seguiremos denominando TTLT como en el caso de la asociación indirecta, va a tener la forma de un árbol de tres niveles:

• El primer nivel del árbol estará constituido por un solo nodo que almacenará una estructura de datos capaz de dirigir la búsqueda hacia el nodo adecuado del segundo nivel, utilizando como elemento de decisión el número de línea del texto cuyo componente léxico se trata de encontrar.
• El segundo nivel del árbol tendrá asociado un nodo por cada una de las líneas presentes en el texto. Una vez que el proceso de búsqueda ha llegado a uno de los nodos del segundo nivel, debe ser capaz de determinar, a partir únicamente de la columna en la cual comienza el texto, cuál es la estructura de representación del componente léxico asociada al texto.
• El tercer nivel del árbol estará constituido por nodos hoja. Existirá uno de estos nodos por cada componente léxico reconocido en el proceso de análisis del texto. Cada nodo almacenará el TTR correspondiente a un componente léxico.

Una vez definida la estructura general del árbol, queda por analizar la constucción de cada uno de los diferentes tipos de nodos.

El nodo raíz

Conseguir una implementación eficiente del nodo raíz es fundamentel si queremos conseguir que el editor de componentes léxicos sea capaz de realizar las funciones de búsqueda de componentes léxicos de manera eficiente y a la vez con la mayor economía posible de recursos computacionales.

El nodo raíz es importante por las siguientes causas:

• Puesto que su misión es la de actuar de enlace entre el primer y el segundo nivel del árbol, debe poseer estructuras de asociación que permitan ligar cada número de línea (el segmento de clave utilizado en el primer nivel) con el nodo de segundo nivel correspondiente. Para textos grandes, el tamaño del nodo raíz puede ser muy grande. Contruir el nodo raíz de forma que utilice eficientemente la memoria es un factor importante de diseño.
• Como consecuencia de un tamaño potencialmente elevado, es importante que la estructura de datos mediante la cual se implemente este nodo permita un acceso efectivo igual de rápido para todos los elementos. No se pueden consentir retardos elevados en el acceso a ninguno de los niveles del árbol puesto que ello implicaría una disminución del rendimiento global de la función de búsqueda.
• El problema de rendimiento que surgía en las diferentes estrategias de asociación indirecta con aquellas modificaciones de los componentes léxicos que suponían la eliminación o incorporación de caracteres de ruptura de líneas, puede ser evitado en gran parte en la estrategia multinivel mediante la implementación del nodo raíz utilizando una estructura que permita realizar facilmente actualizaciones sin necesidad de copiar realmente todo el contenido de los subárboles afectados.

Como siempre, a la hora de elegir la estructra de datos mediante la cual se implementa el nodo raíz, podemos optar entre un cierto número de alternativas. Entre ellas tenemos:

• Listas, que no son adecuadas debido a que el tiempo de acceso a los elementos no es constante, si no que varía en función de su posición en la lista.
• Conjuntos, en principio más adecuados debido a la unicidad de las claves utilizadas, presentan los mismos inconvenientes que las listas.
• Vectores, inadecuados debido al carácter estático de su tamaño.
• Tablas hash, ya utilizadas anteriormente en las estrategias de asociación indirecta, se vuelven a presentar como la opción preferida ya que presentan las siguientes ventajas:
  • Proporcionan un tiempo de acceso constante para todos los elementos, independientemente del valor de la clave.
  • Permiten realizar fácilmente inserciones y borrados.
  • Permiten una rápida reorganización en caso de que sea necesario desplazar las entradas de la clave como consecuencia de la modificación de los caracteres de rupturas de líneas en el texto de alguno de los componentes léxicos.
  • Independizan el nodo raíz de los nodos intermedios. Esto se debe a que las tablas hash almacenan punteros, no valores en sí, por lo que puede modificarse la estructura apuntada con total libertad.

Por tanto, se utilizarán tablas hash para construir el nodo raíz del árbol de enlace.

Los nodos internos

Una vez que se ha diseñado la estructura del nodo raíz se debe pasar a tratar los aspectos relacionados con los nodos de la siguiente capa del árbol, los nodos internos.

Estos nodos tienen como misión proporcionar un enlace eficiente entre el segundo y el tercer nivel del árbol mediante la asociación del siguiente segmento de la clave (el número de columna) al elemento de representación del componente léxico correspondiente al texto cuyo primer carácter tiene por coordenada vertical el primer segmento de la clave y por coordenada horizontal el segundo segmento.

Las consideraciones que se barajan en el caso de estos nodo son diferentes a las que se utilizaban en el caso del nodo raíz, puesto que ahora el tamaño no es una característica dominante. Además, ahora no se trata de establecer la mejor estructura para un único nodo, como en el caso del raíz, sino que se debe buscar una estructura eficiente de la que existirán múltiples instancias, una por cada nodo intermedio, esto es, una por cada línea presente en el texto, teniendo en mente que su número puede puede ser potencialmente elevado.

Una vez más examinamos las diferentes alternativas:

• La utilización de tablas hash no parece ser en este caso la opción más favorable, por dos razones principalmente:
  • El pequeño tamaño de cada una de las líneas no hace necesario la utilización de una estructura de almecenamiento compleja. El reducido número de componentes léxicos por línea puede hacer que la el tiempo medio de búsqueda por clave sea más lento que una simple exploración secuencial.
  • Al existir una tabla por cada línea sería necesario reservar almacenamiento para cada una de ellas. La gestión de este almacenamiento por parte del garbage collector encarece el uso de este tipo de estructuras.
• Las listas se presentan como alternativa más viable, una vez descartados los vectores por su conocida limitación del tamaño fijo. Las listas de pequeño tamaño se muestran realmente como estructuras muy eficientes, sobre todo si se utilizan las funciones que modifican físicamente los elementos de las listas. Puesto que los elementos de la lista deberán ser pares (posición,componente léxico), parece adecuado utilizar una lista de asociación para cada nodo intermedio, de modo que dicha lista contenga las asociaciones entre el segundo segmento de la clave de un componente léxico y la estructura de representación del componente léxico propiamente dicho.

Por tanto, se utilizarán listas de asociación para construir los nodos intermedios del árbol de enlace.

Los nodos hoja

Los nodos hoja son aquellos nodos del árbol de enlace que en se encuentran al final de los caminos de búsqueda, o lo que es lo mismo, al final de las distintas ramas del árbol.

La misión de un nodo hoja es almacenar la información de análisis relativa a un componente léxico que pueda resultar de interés para la interacción con el usuario o que pueda resultar necesaria para realizar las operaciones de edición del texto de los componentes léxicos. Es fácil observar la similitud entre las funciones realizadas por los nodos hoja y las correspondientes a los TTR de la estragia indirecta. Ciertamente tal similitud no es casual, pues las diferentes variantes de la asociación indirecta pueden verse como casos simplificados de la asociación multinivel en las que tan sólo existe un nivel de indirección. Según esto, las distintas variantes se centrarían en encontrar una forma adecuada de representar su pequeño árbol de anlace.

En lo que difiere la asociación multinivel es en la introducción de múltiples niveles de indirección, con lo que se aumenta la distancia entre la raíz del árbol y las hojas. Por eso es lógico que las TTR no presenten más que pequeñas variaciones. Puede ser incluso significativo comprobar como en el nodo raíz se sigue manteniendo una tabla hash como estructura de representación.