Экспоненциальная задача регулярных выражений

Question

Может ли кто-нибудь помочь мне переписать это регулярное выражение как неэкспоненциальное?

Я использую Perl для анализа данных электронной почты. Я хочу извлечь адреса электронной почты из данных. Вот сокращенная версия регулярного выражения, которое я использовал:

my $email_address = qr/(?:[^\s@<>,":;\[\]\(\)\\]+?|"[^\"]+?")@/i

Для простоты я удалил более позднюю часть домена в регулярном выражении. (Это не вызывает никаких проблем.)

При этом будет найден адрес электронной почты, совместимый с RFC, который содержит мета-символы, не относящиеся к электронной почте, или строку «в кавычках», за которой следует @. Используя OR '|' Часть регулярного выражения с двумя различными шаблонами с несколькими символами создает экспоненциальную проблему.

Проблема в том, что когда я раскрываю это в строке данных длиной в несколько тысяч символов.

$ wc line7.txt 
1    221 497819 line7.txt

(извините, но я не могу предоставить входные данные в настоящее время, возможно, я смогу позже их смоделировать.)

Очень похоже на переписывание (a * b *) * в (a | b) *, мне нужно переписать это регулярное выражение.

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

Возможный целевой компьютер находится в кластере Hadoop. Поэтому я бы хотел избежать модулей CPAN, которые не поставляются с версией Hadoop для Perl (Я должен проверить, можно ли вообще использовать Email :: Find.) Это проблема, с которой я столкнулся на работе.

Answer 1

Рассматривали ли вы модули CPAN Электронная почта :: Действительный и Электронная почта :: Найти ?

Если это не для вашего собственного удовольствия или образования, вы почти наверняка не должны пытаться написать свой собственный адрес электронной почты, соответствующий регулярному выражению. Посмотрите «Освоение регулярных выражений» Джеффри Фридла, если вы хотите узнать, как на самом деле выглядит такая вещь. (Подсказка: длина 6,598 байт.)

Answer 2

qr/(?:(?>[^\s@<>,":;\[\]\(\)\\])+|"[^\"]{0,62}")@/i

Часть (?>expression) предотвращает возврат.Это должно быть безопасно, потому что не может быть совпадений между частью без кавычек и частью с кавычками.

Я удалил ленивые повторы +?, потому что части чередования уже ищут @ и " соответственно.Фразы могут быть большим источником отката, поэтому я посмотрел статью в Википедии, в которой говорится, что локальная часть (до @) может быть длиной всего 64 символа (вычитая две кавычки, получаем {0,62} (если ""@ недопустимо,затем измените его на {1,62} .... Я не собираюсь, чтобы это был полностью функциональный парсер электронной почты. Это ваша работа. Я просто предоставляю помощь для катастрофического возврата.) Удачи!

Answer 3

Если во многих строках нет адреса электронной почты, как насчет быстрой предварительной проверки перед применением RE:

if ( my $ix = index( $line, '@' ) > 0 )
{   #test E-mail address here
    . . .
    #and another wild idea you could try to cut down lengths of strings actually parsed:
    my $maxLength = 100;     #maximum supported E-mail address length (up to the @)
    if ( substr( $line, MAX( $ix - $maxLength, 0), $maxLength ) =~ /YourRE/ )
}

(да,> любая строка, начинающаяся с@ не может быть адресом электронной почты)

Answer 4

Просто измените +? на +; ? говорит, что предпочитает сопоставлять как можно меньше раз, что совсем не то, что вы хотите.

Либо я что-то неправильно вижу, либо ваша проблема в той части регулярного выражения, которую вы нам не показываете. Или есть какая-то разница между тем, что вы показываете, и тем, что вы на самом деле пытаетесь. В любом случае вы можете попытаться изменить +? на ++ или включить целое (?:...)@ в (?> ... ).

Есть ли + перед @ в вашем действительном регулярном выражении? Если это так, то просто изменить (?: на (?> и сделать , чтобы + было ++, было бы очень хорошей идеей.

Answer 5

Нежадные спички дороги, насколько я понимаю, если вы не будете осторожны.Это может сделать много-много возврата.http://blog.stevenlevithan.com/archives/greedy-lazy-performance

Один из приемов, которые я часто использую, состоит в том, чтобы деструктивно извлекать биты данных, как только я выясняю, что они не могут содержать никаких данных.Другой трюк состоит в том, чтобы выполнить сопоставление без возврата (\ @ {1} + и т. П.), Если есть что-то, что может сигнализировать вам, что существует абсолютно адрес электронной почты, который вам нужно проанализировать.

В вашем конкретном примере, возможно, вы можете ограничить количество символов, которые могут быть в адресе электронной почты?Вместо + в левой части символа @ используйте {1,80}