Estoy muy contento con la funcionalidad que ofrece el Autómata No Determinante Landa Transiciones, en adelante ANDLT. Me reconoce las expresiones regulares perfectamente. En la actualidad, con las expresiones que tiene insertadas tiene 17540 estados, con lo que al realizar un reconocimiento tarda entre 4 y 5 segundos en mi portátil. Observando que cada vez que introduzco una nueva expresión regular, como media, duplica el número de estados, era fácil pensar que pasaría a tardar como mínimo a 10 segundos por consulta rápidamente. Ello me hizo plantearme seriamente la opción de implementar el Autómata Finito Determinante.
Lo implementé. Para generar un AFD coge el ANDLT y se basa en su tabla de transiciones. Lógicamente, para empezar, vacié el ANDLT y comencé con una expresión regular sencilla. Los resultados eran muy prometedores. Comparando el número de estados entre el ANDLT original y el AFD resultante, como medía se producía una reducción entre el 60 % y 80 %.
Con las expresiones regulares insertadas: dígito, natural, entero positivo, entero negativo, entero, real positivo, real negativo y real, su ANDLT tiene 950 estados y su AFD 120.
Pero no todo es tan bonito, resulta que no trabaja bien los estados finales. He comprobado que la tabla de transiciones está perfecta, pero sin embargo, lo que debería de ser lo más fácil, el cálculo de los estados finales, es en lo que falla.
Esto no tiene más que sentarse y buscar el fallo. El verdadero problema es que conforme el ANDLT es más grande, el tiempo de cálculo del nuevo AFD va aumentando exponencialmente. Para el ejemplo anterior tarda uno dos minutos.
Quise hacer la siguiente prueba, el ANDLT con las siguientes expresiones insertadas: dígito, natural, entero positivo, entero negativo, entero, real positivo, real negativo, real, fraccionario entero, fraccionario real, fraccionario, dígito numeral, numeral natural, numeral entero positivo, numeral entero negativo, numeral entero, numeral real positivo, numeral real negativo, numeral real, numeral fraccionario entero entero, numeral fraccionario entero real, numeral fraccionario real entero, numeral fraccionario real real, numeral fraccionario en 17540 estados. Dejé la máquina trabajando como unas 4 horas y no terminó el cálculo. Me dio pena el portátil ya que estaba ardiendo y finalicé el proceso.
Pensando y pensando, lo que se me ocurre es que en lugar de pasar el ANDLT al completo a AFD sería obtener el AFD de cada ER por separado, unirlas por un ANDLT y por último obtener su AFD final.
Otra opción sería ir generando el AFD al mismo tiempo que genera su ANDLT de esta manera el número de estados Landa sería mínimo.
Y la última opción sería generar directamente el AFD, esto ya lo veo más complicado.
Tengo la mañana de hoy para ir pensando y ver por qué opción tiro.
Mola!!!
ResponderEliminar