2.7.1 La estructura de enlace

La parte central de esta estrategia la constituye la estructura de datos, con forma de árbol, que se utilizará para establecer los enlaces entre el texto y los componentes léxicos. Desde el punto de vista lógico, dicha estructura se caracteriza por:

• Cada nodo del árbol representa a la vez:
  • un conjunto de texto lógicamente relacionado
  • el conjuto de componentes léxicos resultado del análisis de dicho texto.
• La raíz del árbol representa todo el texto contenido en el editor de componentes léxicos y por tanto también todos los componentes léxicos resultado de su análisis.
• Las hojas del árbol representan la asociación de un único componente léxico con su texto correspondiente.

Pasando ya a aspectos más prácticos, desde el punto de vista de la eficiencia computacional, debe poseer la suficiente flexibilidad como para permitir la realización de operaciones de inserción, modificación y borrado de nuevos componentes léxicos sin que ello suponga la realización de una costosa reorganización sobre una parte significativa del árbol.

Utilización de B árboles

Una estrcutura de datos que se adapta muy bien a estas características es la correspondiente a un árbol o a un B árbol. Se puede encontrar una descripción de las características de ambos tipos de árboles en [Korth y Silberschatz 87].

Las ventajas que presenta la utilización de un árbol son las siguientes:

• Todos los nodos del árbol tienen la misma estructura, lo cual facilita la escritura de la función de búsqueda.
• Todas las ramas tiene la misma longitud, por lo que el tiempo de acceso a las hojas es igual para todas ellas.

Los B árboles, por su parte, presentan como ventajas más significativas:

• Eliminan el almacenamiento redundante de claves de búsqueda.
• No todas las ramas son de la misma longitud, sino que, en función de la distribución de los valores de las claves de búsqueda, ciertos elementos pueden ser accedidos directamente desde niveles superiores del árbol.

Genéricamente, estas ventajas de los B árboles se ven ensombrecidas por los siguientes inconvenientes:

• La gestión y el mantenimiento del índice se complica, pues es necesario manejar dos tipos de nodos distintos.
• Las operaciones de eliminación en un B árbol son más complejas, puesto que los valores eliminados no residen necesariamente en las hojas.

Se podría asumir la mayor complejidad asociada a la gestión de B árboles con el fin de diseñar una estructura de almacenamiento más compacta, aunque la utilización dual de los nodos intermedios suponga una disminición de la simplicidad y claridad que proporciona la estructura árbol

Utilización de claves segmentadas

La utilización de B o árboles impone la necesidad de utilizar la clave completa para etiquetar los nodos, de modo que la función de búsqueda siempre utiliza la totalidad de la clave en todos los niveles del árbol.

En este trabajo se propone la utilización de claves segmentadas para optimizar el proceso de búsqueda y la organización de la estructura arborescente. En cada nodo se utilizará el siguiente segmento de la clave como criterio de decisión para determinar el camino a seguir.

Como ya se expuso en la discusión de las otras estrategias, la interación del usuario con el editor de componentes léxicos se realiza directamente mediante pulsaciones sobre el texto, puesto que éste es el método más intuitivo y práctico para el usuario. Esto conlleva la necesidad de utilizar la posición de un carácter significativo del texto de cada componente léxico, generalmente el primero, como clave de acceso a la estructura de asociación con los componentes léxicos. Por consiguiente, el único método natural de segmentar la clave consiste en descomponerla en los valores de las coordenadas componentes, esto es, considerar cada clave como la composición del valor de la coordenada horizontal con el valor de la coordenada vertical.

El proceso de búsqueda utilizará la coordenada horizontal (el número de línea) para indexar el nodo raíz y obtener el nodo que representa los componentes léxicos de dicha línea, para a su vez indexar dicho nodo con el valor de coordenada vertical y obtener así el componente léxico cuyo texto comienza en esa posición.

Por consiguiente se utilizará una estructura de dos niveles de indexación, en la que el primer nivel permite discrimar el conjunto relevante de entradas del segundo nivel, las cuales apuntan directamente a los datos.