¿Se puede convertir un Earley Parser en un analizador difuso similar al Levenshtein Automata Algo para DFA?

10

Hay una manera de realizar un análisis difuso (acepta cadenas incluso con errores tipográficos a una cierta distancia de edición), con un DFA y un Autómata Levenshtein construido en tiempo de ejecución de la palabra de entrada. ¿Se puede hacer algo similar con un analizador Earley? Me resulta difícil entender el algoritmo, y mucho menos responder esta pregunta.

EnjoysMath
fuente
1
Bueno, los PDA están cerrados contra muchas operaciones con NFA, por lo que esto debería ser posible en principio. Adaptar Earley parece ser un ejercicio de memoria, ya que se nos permite usar contadores en los artículos. ¿Me estoy perdiendo de algo?
Raphael
@Raphael Sí, esta es la idea general. Mi respuesta es más larga, ya que es difícil evaluar lo que los usuarios saben o no saben.
babou
cite una referencia de ref / sketch para "Levenshtein Automata". sabe de uno que podría calificar, pero ¿a cuál se refiere?
vzn

Respuestas:

8

La respuesta es sí. Sin embargo, no haría eso con un analizador Earley porque hay otros más simples con las mismas capacidades.

Básicamente, el analizador Earley pertenece a una familia de analizadores generales sin contexto, que produce todos los análisis posibles para una cadena dada, cuando la gramática es ambigua.

Hay dos formas (al menos) de entender estos analizadores:

  • como interpretación de programación dinámica de un autómata pushdown correspondiente a la gramática en la cadena de entrada;

  • como la construcción de la intersección de la gramática con un autómata de estado finito.

Al analizar una sola cadena, el autómata de estado finito a considerar es un autómata lineal que reconoce solo la cadena a analizar, un símbolo a la vez (el número de estado es | w | + 1 ). Si aplica la construcción de productos cruzados de un FA A y una gramática CF G (Bar Hillel, Perlis, Shamir 1961), obtendrá una nueva gramática CF que es una nueva gramática F que genera L ( A ) L ( G ) . El punto interesante que generalmente se pasa por alto es que F conserva los árboles de análisis utilizados por GwEl |wEl |+1UNsolFL(UN)L(sol)Fsol, hasta el cambio de nombre de no terminales (debido a productos cruzados).

Por lo tanto, si la FA genera solo su cadena de entrada, la gramática F generará solo esa cadena (si está en L ( G ) , de lo contrario genera el lenguaje vacío ). Además, lo genera con todos los árboles de análisis que G podría usar para generarlo.UNFL(sol)sol

Esta gramática es lo que generalmente se llama un bosque de análisis compartido , y todos los algoritmos generales de análisis de CF son una versión más o menos optimizada de la construcción de productos cruzados, ya sea CYK, Earley, LR generalizado o LL, u otros. Entonces, todo lo que digo se aplica a ellos también.F

Pero, como puede ver, esto se generaliza al análisis de un conjunto regular completo, si alguien está interesado en hacerlo.

ww

solF

Si es deseable, esto se puede usar para mantener solo las cadenas con una distancia mínima.

Sin embargo, esto puede mejorarse un poco ya que la composición con máquinas de estados finitos es asociativa.

solwΣ

Sería fácil podar esa construcción para obtener el mismo resultado que antes, pero la mejor manera es una construcción de intersección más controlada, como la organización de programación dinámica utilizada por la mayoría de los analizadores en la literatura, incluida Earley, y usarla para evitar generar regla inútil calculando distancias y abortando cualquier ruta computacional cuando excede el umbral deseado. La programación dinámica también se puede utilizar para calcular directamente el bosque de análisis (o árbol de análisis) para la cadena que tiene la distancia más corta a la entrada.

babou
fuente
piensa que esto es útil, pero también tal vez "leer demasiado" en la pregunta, por lo que decir algo como "esta es precisamente su pregunta" no puede ser realmente exacto. ha tomado una pregunta bastante vaga, no formalizada estrictamente, y (¿intentó?) formalizarla usted mismo. Probablemente haya más de una forma de formalizar la idea algo vaga original. cree que podría ser útil definir primero cuidadosamente lo que hacen las construcciones de DFA Levenshtein (hay algunas conocidas / investigadas, pero ¿de cuáles estamos hablando?) y luego explicar cómo este concepto podría generalizarse a las CFL.
vzn
1
Realmente doy diferentes formalizaciones, que se complementan entre sí. Hay sutilezas en las que no me metí, como el uso exacto de pesas en el proceso, que depende del resultado preciso que desea obtener. Mi propósito no es solo dar una respuesta que tiene poco interés en mi propia opinión, sino dar una comprensión más amplia del problema. La elección de la distancia de edición utilizada es irrelevante, funciona para cualquier cosa que pueda expresarse con un transductor de estado finito ponderado.
babou