ESTRUCTURA Y ESQUEMAS DE BÚSQUEDA POR SIMILITUD DE CADENAS DE CARACTERES. UNA APLICACIÓN PARA PETICIONES COMPLEJAS DE LOCALIZACIÓN DE PALABRAS EN ARCHIVOS DOCUMENTALES

Autora: Margarita Díaz Roca.

Director: Octavio Santana Suárez.

RESUMEN:
     Este trabajo trata aspectos teóricos y experimentales en torno al problema de la búsqueda de las cadenas más similares a una dada. El concepto de similitud es en el sentido de la distancia de Levenshtein, DL. El objetivo que se persigue es la optimización de los recursos de tiempo y espacio de los esquemas de búsqueda y de la estructura de datos que los soporta.
     Se define una nueva distancia que se ha denominado distancia invariante trasposicional, DIT, debido al hecho de que su valor no depende de las operaciones de trasposición a que pueda ser sometida una cadena. Si bien DIT no puede usarse por si sola para la determinación de las cadenas más similares, su importancia deviene de la circunstancia de que su valor entre dos cadenas es siempre inferior o igual a la DL entre estas dos mismas cadenas, siendo su coste computacional sensiblemente inferior; lo cual puede ser aplicado para la construcción de un filtro adaptivo DIT/DL que tenga por misión reducir el número de cadenas de la base de datos a las que se les calcula la DL con la cadena de búsqueda.
     Se diseña una estructura, S-D, al objeto de compartir las componentes de DIT y no tener que calcular completamente la DIT de la cadena de búsqueda a todas y cada una de las cadenas del diccionario. El esquema de búsqueda de las cadenas más similares que se apoya en esta estructura, recorriéndola a través de las componentes de DIT, y que usa este valor
como criterio de poda se denomina esquema decreciente. Se estudian nuevas estrategias para un esquema de búsqueda creciente, donde el radio de búsqueda, en oposición a la evolución clásica decreciente, sigue una línea de modificación creciente. Asimismo, se propone un esquema decreciente con radio ascendente tal que en función del incremento del radio de búsqueda define una familia de esquemas intermedios que conectan a los esquemas creciente y decreciente.
     Prolongando la línea de optimización de las realizaciones de los esquemas de búsqueda decreciente y creciente, se define un nuevo umbral DS, cuyo valor se encuentra entre DIT y DL; y debido a que tiene un menor costo que DL es útil para descartar un número de cadenas a las que no es necesario evaluar DL. También se introduce un refinamiento en la poda del índice que acorta su recorrido.
     Si el tamaño de la estructura es tal que no es posible ubicarla en memoria interna, se plantea el problema de su paginación con el fin de minimizar el número de accesos a disco. Un primer intento para resolver el problema consiste en llenar las páginas con los nodos al recorrer la estructura en preorden o en postorden. También se propone una nueva forma de paginar la estructura de tal modo que se respete el siguiente principio: durante la búsqueda, una vez que se abandone una página no se vuelve a acceder a ella por otro camino.
     Finalmente se concreta en una aplicación a la localización de palabras en texto libre, que constituye una parte fundamental de un problema práctico de gran importancia: la organización y utilización de información procedente de fuentes heterogéneas. Existen dos aproximaciones a este problema, efectuar la búsqueda directamente sobre el documento sin ningún tipo de preparación previa o someter los escritos a un tratamiento anterior y generar un índice que haga viable los accesos posteriores al ejemplar. Siguiendo este último enfoque, se utiliza como índice la estructura S-D construida a partir del conjunto de las palabras diferentes que se obtienen del documento al descartar las cadenas consideradas vacías. Sobre la estructura así construida se permiten los siguientes tipos de búsquedas: exacta, más similares, con operadores booleanos, máscaras, truncamientos, cercanía, antecedencia, párrafos, sentencias, frases y complejas.
     Se construye asimismo un analizador sintáctico que cumple un doble cometido, ya que ha de identificar cada tipo de petición -diferenciando las componentes y los conectores lógicos en el caso de las complejas- y, a la vez, determinar la correctitud sintáctica. Como complemento al analizador se realiza un optimizador para solucionar las búsquedas complejas en el menor tiempo posible; se pretende calcular una petición equivalente a la solicitada por el usuario de forma que se resuelva más rápidamente, minimizando así el tiempo de respuesta del sistema.


Descargar la tesis en formato pdf 1 (215Kb)
Descargar la tesis en formato pdf 2 (436Kb)
Descargar la tesis en formato pdf 3 (225Kb)
Descargar la tesis en formato pdf 4 (483Kb)
Descargar la tesis en formato pdf 5 (347Kb)



Documento convertido con WPAHTML