regex - solo - probar expresiones regulares

¿Inferencia gramatical de expresiones regulares para una lista finita dada de cadenas representativas? (2)

Lo único que puedo sugerir es jugar un poco con Nltk (Natural Language Toolkit for Python) y ver si al menos puede reconocer patrones recurrentes.

Otra cosa que puede considerar es MALLET (paquete basado en Java para procesamiento estadístico de lenguaje natural, clasificación de documentos, agrupación en clústeres, modelado de temas, extracción de información, etc.)

Perl tiene algo que se llama LinkParser pero parece requerir que proporcione una representación de la gramática real (por otro lado, viene con un gran conjunto de modelos diferentes, por lo que tal vez podría ser un calzador para ayudarlo a clasificar sus muestras).

Gate puede permitirle crear ejemplos a partir de un subconjunto de registros en su cuerpo y posiblemente aplicar ingeniería inversa a la gramática de esos.

Finalmente, eche un vistazo al repositorio de CRAN para paquetes específicos de texto .

Estoy trabajando en analizar un gran conjunto de datos públicos con un montón de cadenas verbosas legibles por humanos que fueron claramente generadas por alguna gramática regular (en el sentido de la teoría del lenguaje formal).

No es demasiado difícil ver los conjuntos de estas cadenas una por una para ver los patrones; desafortunadamente, hay alrededor de 24,000 de estas cadenas únicas divididas en 33 categorías y 1714 subcategorías, por lo que es algo doloroso hacerlo manualmente.

Básicamente, estoy buscando un algoritmo existente (preferiblemente con una implementación de referencia existente ) para tomar una lista arbitraria de cadenas e intentar inferir un conjunto de expresiones regulares que se pueden usar para generar un mínimo (para una definición razonable de mínimo) que abarca ellos (es decir, inferir una gramática regular de un conjunto finito de cadenas del lenguaje generado por esa gramática).

He considerado realizar la eliminación codiciosa repetida más prolongada y codiciosa, pero eso solo va hasta ahora porque no colapsará nada más que coincidencias exactas, por lo que no detectará, digamos, un patrón común de cadenas numéricas variables en una posición particular en el gramática.

Brutar forzar cualquier cosa que no quede fuera de la eliminación de subcadenas comunes es posible, pero probablemente computacionalmente inviable. (Además, lo he pensado y podría haber un problema de "ordenación de fases" y / o "mínimo local" con la eliminación de subcadenas, ya que podría hacer una coincidencia de subcadenas codiciosa que termine forzando la gramática final a estar menos comprimida / mínimo aunque parece ser la mejor reducción inicialmente).

Sí, resulta que esto sí existe; lo que se requiere es lo que se conoce académicamente como un algoritmo de aprendizaje de DFA , cuyos ejemplos incluyen:

L de Angluin *
L * (añadiendo ejemplos contrarios a las columnas)
Kearns / Vazirani
Rivest / Schapire
NL *
Inferencia positiva positiva regular (RPNI)
DeLeTe2
El algoritmo de Biermann y Feldman
Algoritmo de Biermann y Feldman (utilizando la resolución SAT)

La fuente de lo anterior es libalf , un marco de algoritmo de aprendizaje de autómatas de código abierto en C ++; Las descripciones de al menos algunos de estos algoritmos se pueden encontrar en este libro de texto , entre otros. También hay implementaciones de algoritmos de inferencia gramatical (incluido el aprendizaje de DFA) en gitoolbox para MATLAB.

Dado que esta pregunta surgió antes y no se ha respondido satisfactoriamente en el pasado, estoy en el proceso de evaluar estos algoritmos y actualizaré más información sobre cuán útiles son, a menos que alguien con más experiencia en el área lo haga primero (lo cual es preferible).

_{NOTA: Estoy aceptando mi propia respuesta por ahora pero con mucho gusto aceptaré una mejor si alguien puede proporcionarla.}

_{NOTA ADICIONAL: He decidido seguir la ruta de usar código personalizado, ya que el uso de un algoritmo genérico resulta ser un poco excesivo para los datos con los que estoy trabajando.} _{Dejo esta respuesta aquí por si alguien más la necesita, y la actualizaré si alguna vez la evalúo.}