Algoritmos eficientes de estados finitos para la aplicación de gramáticas locales

• Autores: Javier Miguel Sastre Martínez
• Directores de la Tesis: Éric Laporte (dir. tes.) , Mikel L. Forcada Zubizarreta (dir. tes.)
• Lectura: En la Universitat d'Alacant / Universidad de Alicante ( España ) en 2011
• Idioma: español
• Tribunal Calificador de la Tesis: Olivier Carton (presid.) , Joan Andreu Sánchez Peiró (secret.) , Mikel L. Forcada Zubizarreta (voc.) , Éric Laporte (voc.)
• Texto completo no disponible (Saber más ...)
• Resumen

  • Este trabajo se centra en la investigación y el desarrollo de algoritmos eficientes de aplicación de gramáticas locales, tomando como referencia aquellos que están siendo usados en sistemas open-source, a saber: el analizador sintáctico top-down de Unitex y el analizador sintáctico à la Earley de Outilex.

    Las gramáticas locales son un formalismo basado en autómatas finitos para la representación de la sintaxis de los lenguajes naturales. Las gramáticas locales son un modelo de construcción de descripciones precisas y a gran escala de la sintaxis de los lenguajes naturales mediante la observación sistemática y la acumulación metodológica de información. La idoneidad de las gramáticas locales para esta tarea ha sido demostrada por múltiples trabajos.

    Debido a la naturaleza ambigua de la lengua, y a las propiedades de las gramáticas locales, los analizadores sintácticos clásicos tales como LR, el de CYK y el de Tomita no son viables en el contexto de este trabajo o requieren adaptaciones no triviales. Los analizadores sintácticos top-down y de Earley son posibles alternativas, aunque tienen un coste asintótico exponencial en el caso de las gramáticas locales.

    En primer lugar, hemos desarrollado un algoritmo de aplicación de gramáticas locales con un coste asintótico polinomial. A continuación, hemos desarrollado estructuras de datos eficientes para la gestión de conjuntos de elementos y de secuencias. Estas estructuras han permitido mejorar la eficiencia de nuestro algoritmo en condiciones generales. Hemos implementado dicho algoritmo y los algoritmos de Unitex y Outilex con las mismas herramientas con el fin de compararlos bajo las mismas condiciones. Hemos implementado distintas versiones de cada algoritmo usando nuestras estructuras de datos de tipo conjunto y aquellas incluidas en la implementación de GNU de la librería estándar de plantillas (Standard Template Library o STL). Hemos comparado el rendimiento de los distintos algoritmos y de sus distintas versiones en el contexto de una aplicación industrial propuesta por la empresa Telefónica I+D: aumentar la capacidad de comprensión de un robot conversacional capaz de suministrar servicios en línea, tales como el envío de SMS a teléfonos móviles así como de juegos y de otros contenidos digitales. La comunicación con el robot se realiza en español a través de Windows Live Messenger de Microsoft. A pesar del dominio restringido y de la simplicidad de las gramáticas aplicadas, los tiempos de ejecución fueron menores para nuestro algoritmo y nuestras estructuras de datos de tipo conjunto. Gracias al coste asintótico mejorado de nuestro algoritmo, son de esperar tiempos de ejecución significativamente inferiores a los de los algoritmos empleados por los sistemas Unitex y Outilex para el caso de gramáticas complejas y de gran cobertura.