Departamento de Lenguajes y Sistemas Informáticos

Comunicación

Título:ATENCIÓ CANVI DE SALA: Algoritmos eficientes de estados finitos para la aplicación de gramáticas locales Incorpóralo a tu calendario:
Tipo:Conferència
Por:Javier M. Sastre-Martínez
Lugar:Seminari de 3r cicle
Día/hora:26/09/2011 12:30
Duración aproximada:1:30 horas
Persona de contacto:Forcada Zubizarreta, Mikel L. (mlf[Perdone'm]dlsi.ua.es)
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. Estas gramáticas constituyen 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 o requieren
modificaciones no triviales para ser usados en el
contexto de este trabajo. 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. Partiendo del algoritmo de Earley,
hemos desarrollado un nuevo algoritmo de aplicación de
gramáticas locales con un coste polinomial en el peor de
los casos. A continuación, hemos desarrollado estructuras
de datos más eficientes que aquellas propuestas por
la Standard Template Library (STL) para la gestión de
conjuntos de elementos y de secuencias; estas estructuras
han permitido mejorar la eficiencia de nuestro algoritmo en
condiciones generales. Finalmente hemos comparado nuestro
algoritmo con aquellos de los sistemas Unitex y Outilex
(y nuestras estructuras de datos con aquellas de la STL)
en el contexto de una aplicación industrial propuesta
por Telefónica I+D: aumentar la capacidad de comprensión
del agente conversacional MovistarBot mediante el uso de
gramáticas locales. A pesar del dominio restringido de las
gramáticas aplicadas (oraciones de solicitud de servicios
en línea), obtuvimos tiempos de ejecución menores con
nuestros algoritmos y estructuras de datos. Gracias al
coste asintótico reducido de nuestro algoritmo, tiempos
de ejecución significativamente inferiores son de esperar
para el caso de gramáticas de gran cobertura.
[ Tancar ]