Ile wyrażeń regularnych mogę połączyć za pomocą naprzemiennej metody?

Question

Mam kilka dużych plików (setki MB), które muszę wyszukać dla kilku tysięcy ~ 20-znakowych unikatowych ciągów.

Odkryłam, że za pomocą rury naprzemiennej metaznaku do dopasowywania wyrażeń regularnych jak (string1|string2|string3) przyspiesza proces wyszukiwania dużo (versus szukając jednej strunie naraz).

Jaki jest limit rozmiaru skali? Ile wyrażeń mogę połączyć w ten sposób? Czy spowoduje to pewnego rodzaju przepełnienie? Czy jest lepszy sposób to zrobić?

EDIT

W celu utrzymania moje pytanie krótkie, nie podkreślić fakt, że już wdrożone kod za pomocą tego podejścia naprzemiennej i znalazłem to być pomocne: W przypadku testowego przy typowym zbiorze danych czas działania został skrócony z 87 minut do 18 sekund - przyspieszenie 290x, najwyraźniej z O (n) zamiast O (n * m).

Moje pytanie dotyczy tego, w jaki sposób można oczekiwać, że to podejście będzie działać, gdy inni użytkownicy uruchomią ten kod w przyszłości, używając znacznie większych zbiorów danych z większymi plikami i innymi wyszukiwanymi terminami. Oryginalny kod O (n * m) był istniejącym kodem, który był używany przez 13 lat, a jego powolność została ostatnio wskazana, ponieważ zestawy danych związane z genomem, na których działa, ostatnio stały się znacznie większe.

Answer 1

Jeśli masz prostego wyrażenia regularnego jak (word1 | słowo2 | ... | wordn), silnik regex będzie skonstruować maszynę stanów, które można po prostu przejść nad wejściem raz aby sprawdzić, czy ciąg pasuje.

Nota boczna: w informatyce teoretycznej "wyrażenia regularne" są zdefiniowane w taki sposób, że pojedyncze przejście jest zawsze wystarczające. Jednak praktyczna implementacja regex dodaje funkcje, które umożliwiają konstruowanie wzorców regex, które nie mogą być zawsze implementowane jako pojedyncze przejście (see this example).

Ponownie, ze względu na swój wzór wyrażeń regularnych, silnik prawie na pewno użyje pojedynczego przejścia. Prawdopodobnie będzie to szybsze niż wielokrotne czytanie danych z pamięci ... i prawie na pewno dużo szybciej niż wielokrotne czytanie danych z dysku.

Answer 2

Jeśli masz zamiar mieć regularne wyrażenie formy (word1 | word2 | .... | wordn), dlaczego nie wystarczy utworzyć skojarzoną tablicę zmiennych logicznych. To powinno być bardzo szybkie.

EDIT

# 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

Nie ma teoretycznego ograniczenia zakresu wyrażenia regularnego, ale praktycznie musi on mieścić się w granicach określonej platformy i instalacji. Musisz dowiedzieć się empirycznie, czy twój plan zadziała, a ja z radością przyjrzę się twoim wynikom.

Jedną rzeczą, którą chciałbym powiedzieć jest to, że powinieneś osobno skompilować wyrażenie, zanim zaczniesz go używać. Albo to albo zastosuj opcję /o, aby skompilować tylko raz (to znaczy obietnicę, że zawartość wyrażenia się nie zmieni). Coś w tym stylu:

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; 
    } 
}