Simplificación de patrones O regex O

Question

Me preguntaron hoy si había una biblioteca para tomar una lista de cadenas y calcular la expresión regular más eficiente para que coincida solo con esas cadenas. Creo que es un NP Complete problem por sí mismo, pero creo que podemos refinar el alcance un poco.

¿Cómo iba a generar y simplificar una expresión regular para que coincida con un subconjunto de los ejércitos de un conjunto más amplio de todos los nodos de la red? (Sabiendo que podría no obtener la expresión regular más eficiente.)

El primer paso es fácil. De la siguiente lista;

• appserver1.domain.tld
• appserver2.domain.tld
• appserver3.domain.tld

puedo concatenar y escapar de ellos en

appserver1\.domain\.tld|appserver2\.domain\.tld|appserver3\.domain\.tld 

Y sé cómo simplificar manualmente la expresión regular en

appserver[123]\.domain\.tld 

Desde allí puedo probar ese patrón con la lista completa de hosts y verificar que solo coincida con los 3 hosts seleccionados. Lo que no sé es cómo automatizar el proceso de simplificación. ¿Hay alguna biblioteca (en Perl, Javascript o C#) o prácticas comunes?

Gracias

actualización Tengo algunos módulos de Perl impresionante, pero me encantaría una solución extremo frontal también. Eso significa Javascript. He buscado pero nadie ha portado los módulos perl a JS y no he encontrado el idioma para buscar este tipo de biblioteca.

Answer 1

Regexp::Assemble::Compressed/Regexp::Assemble saben mucho más trucos que PreSuf. R::A viene con la herramienta de línea de comandos assemble (no instalada de manera predeterminada) lo que hace que generar expresiones regulares sea aún más fácil.

Answer 2

El módulo Regex::PreSuf está diseñado para hacer exactamente esto.

citar el Sinopsis:

use Regex::PreSuf; 

my $re = presuf(qw(foobar fooxar foozap)); 

# $re should be now 'foo(?:zap|[bx]ar)' 

Answer 3

El compilador de expresiones regulares de Perl construye una estructura de datos trie ramificación de patrones con las partes en común a través de las alternativas:

$ perl -Mre=debug -ce '"whatever" =~ /appserver1\.domain\.tld|appserver2\.domain\.tld|appserver3\.domain\.tld/' 
Compiling REx "appserver1\.domain\.tld|appserver2\.domain\.tld|appserver3\."... 
Final program: 
    1: EXACT <appserver> (5) 
    5: TRIEC-EXACT[123] (25) 
     <1.domain.tld> 
     <2.domain.tld> 
     <3.domain.tld> 
    25: END (0) 
anchored "appserver" at 0 (checking anchored) minlen 21 
-e syntax OK 
Freeing REx: "appserver1\.domain\.tld|appserver2\.domain\.tld|appserver3\."...