¿Cuántas expresiones regulares puedo encadenar usando alternancia?

Question

Tengo algunos archivos grandes (cientos de MB) que necesito para buscar varias cadenas únicas de miles ~ 20 caracteres.

que he encontrado que el uso de la alternancia metacarácter tubería para hacer coincidir expresiones regulares como (string1|string2|string3) acelera el proceso de búsqueda mucho (frente a la búsqueda de una cuerda a la vez).

¿Cuál es el límite de qué tan bien se escalará? ¿Cuántas expresiones puedo encadenar juntas así? ¿Causará algún tipo de desbordamiento en algún momento? ¿Hay una mejor manera de hacer esto?

EDITAR

En un esfuerzo por mantener mi pregunta breve, no enfatizar el hecho de que ya haya implementado código usando este enfoque alternancia y me pareció que para ser útiles: En un caso de prueba con un conjunto de datos típico, el tiempo de ejecución se redujo de 87 minutos a 18 segundos, una aceleración de 290x, aparentemente con O (n) en lugar de O (n * m).

Mi pregunta se refiere a cómo se puede esperar que este enfoque funcione cuando otros usuarios ejecuten este código en el futuro utilizando conjuntos de datos mucho más grandes con archivos más grandes y más términos de búsqueda. El código O (n * m) original era un código existente que se usaba desde hacía 13 años, y su lentitud fue señalada recientemente ya que los conjuntos de datos relacionados con el genoma en los que opera han aumentado recientemente.

Answer 1

Si usted tiene una expresión regular simple como (palabra1 | palabra2 | ... | wordn), el motor de expresiones regulares construirá una máquina de estados que simplemente puede pasar por encima de la entrada una vez para encontrar si la cadena coincide.

Nota al margen: en la ciencia de la computación teórica, las "expresiones regulares" se definen de tal manera que una sola pasada siempre es suficiente. Sin embargo, la implementación práctica de la expresión regular agrega características que permiten la construcción de patrones regex que no se pueden implementar siempre como una sola pasada (see this example).

De nuevo, para su patrón de expresiones regulares, el motor casi seguramente utilizará una sola pasada. Es probable que sea más rápido que leer los datos de la memoria varias veces ... y casi definitivamente mucho más rápido que leer los datos varias veces desde el disco.

Answer 2

Si solo va a tener una expresión regular de la forma (word1 | word2 | .... | wordn), ¿por qué no simplemente crear una matriz asociada de booleanos? Eso debería ser muy rápido.

EDITAR

# before the loop, set up the hash 

%words = (
    cat => 1, 
    dog => 1, 
    apple => 1, 
    .... etc 
); 

# A the loop to check a sentence 

foreach $aword (split(/ /, $sentence)) 
    if ($words{$aword}) print "Found $aword\n"; 

Answer 3

No existe un límite teórico para la extensión de una expresión regular, pero prácticamente debe encajar dentro de los límites de una plataforma y una instalación específicas. Debe averiguar empíricamente si su plan funcionará y, por mi parte, estaría encantado de ver sus resultados.

Una cosa que diría es que debe compilar la expresión por separado antes de continuar usándola. O eso o aplicar la opción /o para compilar solo una vez (es decir, prometer que el contenido de la expresión no cambiará). Algo como esto

my $re = join '|', @strings; 

foreach my $file (@files) { 
    my $fh = IO::File->new($file, '<') or die "Can't open $file: $!"; 
    while (<$fh>) { 
    next unless /\b(?:$re)\b/io; 
    chomp; 
    print "$_ found in $file\n"; 
    last; 
    } 
}