Generador automático de expresiones regulares
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