¿Cómo encontrar un "conjunto mínimo de expansión" para una colección de expresiones regulares?

Question

CONTEXTO:

Tengo una colección pequeña (actualmente menos de 100) pero creciente de expresiones regulares, y quiero optimizar el proceso de determinar una cadena de texto dada cuáles de las reses en mi colección coinciden con la cadena de texto.

Algunas de las RES tienen una relación de pedido, por ejemplo, si sé que la cadena $ T coincide /Windows /I también sé que $ T coincide /Windows.*2000/i. Entonces, cuando pruebe $ T con el RES en mi colección, puedo omitir las pruebas /Windows /I si ya he probado $ T contra /windows.*2000/i y encontré una coincidencia (aunque if /windows.*2000/i lo hace no Partido entonces, por supuesto que yo no poder Omita la prueba contra /Windows /i).

Tenga en cuenta que ninguno de los RES en mi colección es completamente equivalente (para cualquier par de RES, hay al menos una cadena de texto que coincide con una y lo hace no coincide con el otro).

ESTRATEGIA:

Quiero construir un gráfico dirigido g con un nodo para cada RE en mi colección y un borde dirigido para cada par de RES con una relación de pedido (A -> B significa "coincidir con A implica coincidencia contra B"), y encuentre una "Conjunto de expansión mínima" de nodos para el gráfico (conjunto mínimo de nodos s de tal manera que cada nodo en G se encuentra en una ruta dirigida que se origina en S).

La parte fácil:

Hay muchos algoritmos disponibles gratuitamente para trabajar con gráficos acíclicos dirigidos. Entonces, una vez que el gráfico G está construido para mi colección de RES (que es distinto debe garantizar que G sea acíclico), no espero tener muchas dificultades para encontrar un algoritmo apropiado para encontrar un conjunto mínimo de expansión para G.

Donde necesito ayuda:

Me gustaría encontrar una forma eficiente de encontrar todas las relaciones de pedido entre las reses en mi colección, y tal vez también asegurar que no hay dos RES en la colección equivalentes (necesitaré una forma de verificar esto automáticamente como los nuevos RES son. adicional).

Por lo tanto, mis búsquedas web (esencialmente aleatorias) han presentado al menos una afirmación plausible de que una forma razonable de calcular la relación (si alguna) de pedido existe entre dos reses, pero aún no ha presentado ninguna descripción de un algoritmo completo.

¿Alguien sabe de una implementación existente (para comparar Res) que es razonablemente eficiente, disponible gratuitamente e (idealmente) implementada en uno de los lenguajes de secuencias de comandos populares o C/C ++?

Answer 1

No estoy seguro de si tiene flexibilidad en términos de la biblioteca de expresión regular que necesita usar, pero puede ver RE2 cuyo Establecer La interfaz puede coincidir con múltiples reglas simultáneamente. Tenga en cuenta que RE2 utiliza principalmente un enfoque DFA, y no admite todas las características de regex que las otras implementaciones, en su mayoría retroceso, las implementaciones sí.