Código Fuente

Hola, esta vez no voy a colgar el código fuente. Con el único fin de ver cuanta gente lo consulta, lo enviaré a aquellos que me dejen algún comentario. Por hacer el blog un poco más ameno.

Ya funciona el algoritmo AFD Mínimo

Con paciencia he localizado los errores en el código. Se quedaba bloqueado en un ciclo al calcular los estados distinguibles.

Esta ha sido la evolución con las ER corregidas:

AFNDLT tiempo de carga: 0' 18'' estados: 33455 tiempo de consulta: 10''

AFD primera versión, tiempo de carga: más de 4 horas.

AFD segunda versión, tiempo de carga: más de 1 hora, estados: 17540 compresión: 44,79% tiempo de consulta: inmediato.

AFD tercera versión, tiempo de carga: 40' 21'' estados: 9679 compresión: 71,07% tiempo de consulta: inmediato.

AFD Mínimo, tiempo de carga: 2' 15'' estados: 3407 compresión: 89,82% tiempo de consulta: inmediato.

Me encantan los resultados. De las mejoras que anuncié, he aplicado la primera. Sin embargo la segunda está orientada a la estructura general. Recordar que la estructura general es un AFNDLT que enlaza AFD Mínimos. Cuando se comprima el AFNDLT aplicaré la segunda mejora.
Ahora puedo seguir insertando nuevas ER.

Casi tengo programado al completo el AFD mínimo...

Esta mañana he dejado casi al completo el algoritmo que pasa de un AFD a AFD mínimo. La fase de prueba no la ha superado. Funciona perfectamente para las ER de dígito, natural, entero positivo, entero negativo y entero, cuando agrego la ER de real positivo... ya algo falla. Alguna tontería. Nada, sentarse y buscar el fallo.

He querido hacer una comparativa entre lo que ya funciona. Para las expresiones antes citadas el ANDL genera 398 estados, el AFD 190 siendo una compresión del 52.26% y el AFD mínimo genera 43 estados siendo una compresión del 89,19%. Son unos resultados muy prometedores, pero hasta que no esté completamente probado no puedo hacer la comparativa general con todas las ER insertadas y comprobar los tiempos de procesado y estados generados.

Para cuando esté resuelto, se me han ocurrido ciertas mejoras que podrían agiliar el procesado:

• No realizar el AFD mínimo de aquella AFD cuya expresión ER tenga menos de 3 caracteres, ya será mínimo.
• Para acelerar el proceso de AFD a AFD mínimo he pensado el repartir el peso del AFNDL en otros tres. Uno que sólo contenga las ER que correspondan a números, es decir cuyo alfabeto sea 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, +, - y el punto. Otro con las letras del abecedario, minúsculas, mayúsculas y acentuadas y por último aquellas ER que sean un pupurrí de números, letras y otros símbolos. Como para calcular los AFD mínimos para cada estado se compueba todas las letras de su alfabeto, al separarlos en estos tres grupos se evitará estar comprobando los números en una ER que sean de sólo letras, ahorrando muchos pasos del proceso, memoría y tiempo. Esto debe de ser transparente al usuario.

Corregido el fallo

Primero observé que habían expresiones regulares mal formuladas, por ejemplo natural estaba expresado como (dígito)* eso significa 0 o infinito dígitos uno tras otro. No puede ser 0. La nueva ER queda (dígito)(dígito)* esto obliga a que por lo menos exista un dígito.

Tras las modificaciones de las ER el ANDLT final pasaba a tener 33516 estados.

Con la corrección en el algoritmo para pasar a AFD a pasado a tener 9679 estados y el cálculo lo ha terminado en 33 minutos, siendo el 71,12% menos.

Estoy muy contento. Ahora toca obtener el AFD Mínimo.

Detectado fallo al pasar a AFD

El programa funciona bien, reconoce las ER. El problema es que cuando genera la tabla de transiciones del AFD inserta muchas transiciones a -1 que es el estado error. Inserta el estado final en un paso recursivo tarde. El resultado es que por ejemplo un AFD de 3 estados se convierta en uno de 15 con más de 100 transiciones.

Es necesario corregir este fallo antes de implementar el AFDMinimo.

¡He conseguido que el programa consiga pasar a AFD! o casi...

La solución que tome al final fue la de ir pasando a AFD según inserta una nueva expresión regular.

Ahora en lugar de almacenar en los arboles de ER y de Nombres su ANDLT, los comprime a AFD. Pero las distintas ER son unidas mediante un ANDLT, como estructura general.

Por ejemplo, tenemos el AFD de un dígito y el AFD de un natural, pues estas estructuras son unidas entre sí mediante un ANDLT, es decir, las une mediante estados Landa.

He dotado al programa para que mediante un parámetro trabaje con ANDLT o con AFD para el cálculo del ANDLT principal.

Lancé el programa y tardó aproximadamente 1 hora en realizar todos los cálculos con las ER que se indicaron en el post anterior. Pasó de 17540 estados a 9679, reduciendo así en 44,79%.

Pero aún no estoy contento. Observando las tablas de transiones he notado que se pueden comprimir mucho más, así que voy a implementar otra capa más, el AFD mínimo.

Y aún  queda por pasar el ANDLT general a todo un AFD y mínimo.

Eso sí, los tiempos para realizar un reconocimiento de una ER son buenísimos. Apenas tiene que hacer transiciones, y eso que no es un AFD mínimo completo.

Estoy planteandome el que cuando se lance el programa, en lugar de generar toda esta estructura, lo interesante sería recuperarla de disco, habiendo almacenado previamente todas las tablas de transiciones de los AFDminimos ya calculados de las ER, para evitar su nuevo cálculo y agilizar el inicio.

Bueno, paso a paso, por lo menos ¡¡¡ TERMINA EL CÁLCULO!!!.

Hay que apretar un poco más las tuercas al programa...

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.

Autómata no determinista, Landa transiciones

Programé la funcionalidad de reconocer una expresión a través de su expresión regular sobre un autómata no determinista Landa transiciones, con la ayuda de Landa clausura.

Va recorriendo la tabla de transiciones y al llegar al o los estados finales, nos muestra por pantalla el nombre de la expresión regular reconocida.

Por ejemplo, si insertamos 13.9 mostrará en pantalla: real

Estas son algunas expresiones que se han añadido:

- 0+1+2+3+4+5+6+7+8+9 dígito
- (dígito)* natural
- (natural)+('+(natural)) entero positivo
- (-(natural)) entero negativo
- (entero positivo)+(entero negativo) entero
- Etc.

Por lo que al insertar 9, nos dice que se trata de un dígito, un natural, un entero positivo y un entero

Reconocimiento de expresiones regulares

Después de tanto tiempo sin dar señales de vida he vuelto con ideas renovadas.

Lo de reestructurar de nuevo el proyecto como se comentó en la entrada anterior no ha resultado como esperaba. Pero las ideas han seguido fluyendo. ¿Cómo reconocer los números reales? Un real puede ser 1. o .1 o 1.1 la última forma es la más común. Es imposible programar todos los números. Una expresión regular nos permite reconocerlos.

La estructura de datos se basa en los autómatas no determinista Landa transiciones para expresiones recientes y autómata determinante mínimo para las expresiones procesadas en sesiones anteriores.

En este momento la primera estructura está programada casi en su totalidad:

- Genera la tabla de transiciones.
- Gestiona los símbolos.
- Gestiona los estados finales.
- Reconoce ER procesados anteriormente y evita volver a trabajar con ellos.
- Reconoce ER por Nombre.
- Genera Landa_clausura.

Y ahora estoy en el procedimiento que reconoce una palabra.