Сколько регулярных выражений можно объединить с помощью чередования?

У меня есть несколько больших файлов (сотни МБ), которые мне нужны для поиска уникальных строк в несколько тысяч 20 символов.

Я обнаружил, что использование метасимвола чередования каналов для сопоставления регулярных выражений типа (string1|string2|string3) значительно ускоряет процесс поиска (по сравнению с поиском по одной строке за раз).

Каков предел того, насколько это будет масштабироваться? Сколько выражений можно объединить вместе? В какой-то момент это вызовет какое-то переполнение? Есть ли лучший способ сделать это?

ИЗМЕНИТЬ

В попытке сохранить мой вопрос кратко, я не подчеркивал тот факт, что я уже реализовал код с использованием этого метода чередования, и я нашел его полезным: на тестовом примере с типичным набором данных, временем выполнения был уменьшен с 87 минут до 18 секунд - 290-кратное ускорение, по-видимому, с O (n) вместо O (n * m).

Мой вопрос связан с тем, как можно ожидать, что этот подход будет работать, когда другие пользователи будут запускать этот код в будущем, используя гораздо большие наборы данных с большими файлами и более поисковыми терминами. Исходный код O (n * m) был существующим кодом, который использовался в течение 13 лет, и его медлительность была отмечена недавно, поскольку связанные с геномом данные, с которыми он работает, недавно получили намного больше.

Ответ 1

Если у вас есть простое регулярное выражение (word1 | word2 |... | wordn), механизм regex будет строить конечный автомат, который может просто пройти через вход один раз, чтобы определить, соответствует ли строка.

Примечание: в теоретической информатике "регулярные выражения" определяются таким образом, что всегда достаточно одного прохода. Тем не менее, практическая реализация регулярных выражений добавляет функции, которые позволяют создавать шаблоны регулярных выражений, которые не могут быть всегда реализованы за один проход (см. Этот пример).

Опять же, для вашего шаблона регулярных выражений, двигатель почти наверняка будет использовать один проход. Скорее всего, это будет быстрее, чем чтение данных из памяти несколько раз... и почти определенно намного быстрее, чем чтение данных несколько раз с диска.

Ответ 2

Если вы просто собираетесь иметь регулярное выражение формы (word1 | word2 |.... | wordn), почему бы просто не создать связанный массив логических элементов. Это должно быть очень быстро.

ИЗМЕНИТЬ

# 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";

Ответ 3

Теоретический предел в объеме регулярного выражения отсутствует, но практически он должен соответствовать рамкам конкретной платформы и установки. Вы должны узнать эмпирически, будет ли ваш план работать, и я бы с радостью увидел ваши результаты.

Одна вещь, которую я бы сказал, заключается в том, что вы должны скомпилировать выражение отдельно, прежде чем продолжать использовать его. Либо это, либо применить параметр /o для компиляции только один раз (т.е. Обещать, что содержимое выражения не изменится). Что-то вроде этого

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