Reconocimiento de patrones en bosques compartidos

Abstract

El uso de árboles como formalismo de representación es una técnica empleada comúnmente en multitud de campos de la informática. Podemos encontrar ejemplos de su uso como estructuras de datos básicas en los compiladores y optimizadores de código, tanto para lenguajes procedimentales, como para lenguaje lógicos o funcionales. También se emplean árboles en la representación de estructuras moleculares, en sistemas de gestión de documentos estructurados o en la representación de sentencias de lenguajes naturales. Por esta razón, un problema de especial relevancia, es el del reconocimiento de patrones en estructuras arborescentes. El objetivo de estas técnicas es el de localizar una estructura de interés, expresada en forma de patrón, dentro de un conjunto de estructuras mayores. El trabajo que presentamos en esta tesis pretende extender las técnicas clásicas de reconocimiento de patrones sobre árboles, basadas en el concepto de distancia de edición, al caso de los bosques compartidos. Nuestro trabajo se embarca en el campo de la aplicación de técnicas avanzadas de reconocimiento de patrones en sistemas de recuperación y extracción de información. En concreto, en el estudio del uso de estructuras sintácticas como elementos clave para la descripción y el acceso a documentos relevantes para los usuarios. En el caso del análisis del lenguaje natural, debemos enfrentamos al problema de la ambigüedad inherente a este tipo de lenguajes. Dicha ambigüedad origina que una misma sentencia pueda tener más de una estructura sintáctica asociada. En nuestro trabajo hemos empleado el generdor de analizadores ICE, que proporciona una representación compacta de los múltiples análisis de una sentencia en forma de bosque de análisis compartido. Por lo tanto, nos hemos centrado en la adaptación de los algoritmos clásicos de reconocimiento de patrones sobre árboles al caso de los bosques de análisis compartidos generado