Tengo N cadenas. Además, hay K expresiones regulares, desconocidas para mí. Cada cadena coincide con una de las expresiones regulares o es basura. Hay un total de cadenas de basura L en el conjunto. Tanto K como L son desconocidas.

Me gustaría deducir las expresiones regulares. Obviamente, este problema tiene un número infinito de soluciones. Necesito encontrar una "solución razonablemente buena", que

1) minimiza K

2) minimiza L

3) maximiza los "detalles" de las expresiones regulares. No sé cuál es el término correcto para esta calidad. Por ejemplo, la cadena "ab123" se puede describir como / ab \ d + / o /\w+.+/, pero la primera expresión regular es más "específica".

odos los 3 requisitos deben tomarse como un criterio compuesto, con ciertos pesos razonables.

Una solución para un caso particular: si L = 0 y K = 1 (solo una expresión regular, y no basura), entonces podemos encontrar LCS (subsecuencia común más larga) para las cadenas y obtener una expresión regular correspondiente a partir de ahí. Sin embargo, cuando tenemos "ruido" (L> 0), este enfoque no funciona.

odas las ideas (o indicadores del trabajo existente) son muy apreciada