Блог

Главная - Вопросы по программированию - Совпадение регулярных выражений (w ) для захвата отдельных слов, разделенных |||

Совпадение регулярных выражений (w ) для захвата отдельных слов, разделенных |||

#python #regex #loops #freeze

#python #регулярное выражение #циклы #заморозить

Вопрос:

Я пытаюсь сопоставить, если за ним следует одно слово s|||s , а затем еще одно слово, за которым следует, s|||s поэтому я использую это регулярное выражение:

 single_word_regex = r'(w ) s|||s(w )s|||s.*'

И когда я попытался сопоставить эту строку, сопоставление регулярных выражений зависает или занимает минуты (возможно, переходит в какой-то «глубокий цикл»)

 >>> import re
>>> import time
>>> single_word_regex = r'(w ) s|||s(w )s|||s.*'        
>>> x = u'amornratchatchawansawangwong ||| amornratchatchawansawangwong . ||| 0.594819 0.5 0.594819 0.25 ||| 0-0 0-1 ||| 1 1 1 ||| |||'
>>> z = u'amor 我 ||| amor . i ||| 0.594819 0.0585231 0.594819 0.0489472 ||| 0-0 0-1 1-2 ||| 2 2 2 ||| |||'
>>> y = u'amor ||| amor ||| 0.396546 0.0833347 0.29741 0.08 ||| 0-0 0-1 ||| 3 4 2 ||| |||'
>>> re.match(single_word_regex, z, re.U)                                              
>>> re.match(single_word_regex, y, re.U)                                          
<_sre.SRE_Match object at 0x105b879c0>
>>> start = time.time(); re.match(single_word_regex, y, re.U); print time.time() - start
9.60826873779e-05
>>> start = time.time(); re.match(single_word_regex, x, re.U); print time.time() - start # It hangs...

Почему это занимает так много времени?

Есть ли лучшее / более простое регулярное выражение для захвата этого условия len(x.split(' ||| ')[0].split()) == 1 == len(x.split(' ||| ').split()) ?

Комментарии:

1. (w ) это зло, удалите последнее .

2. Действительно зло. Теперь он работает с (w ) . @SebastianProske не хотите объяснить, почему?

3. Ну, если w означает char*x , то (w ) означает char*x*y . Когда механизм регулярных выражений обрабатывает второе, может быть несколько комбинаций x и y , которые работают, поэтому он может зависнуть, пытаясь найти единственное решение. Я не знаю деталей движка, но на самом деле это не совсем корректная / четко определенная вещь для анализа.

4. (w ) захватит все символы слова, (w) повторно захватит один символ слова. В первом случае вы получаете захват одной строки, во втором — каждый символ захватывается индивидуально как его собственная группа захвата.

5. regular-expressions.info/catastrophic.html может быть полезной ссылкой, позволяющей избежать зависания регулярных выражений. tl;dr будьте осторожны с группировкой регулярных выражений, потому что она может вести себя неожиданным образом

Ответ №1:

Обратите внимание, что сам по себе r'(w ) ' шаблон не приведет к катастрофическому возврату, он будет только «злым» внутри более длинного выражения, и особенно когда он помещен рядом с началом шаблона, поскольку в случае сбоя последующих подшаблонов движок возвращается к этому, и поскольку квантификатор 1 внутри сновав количественном выражении это создает огромное количество возможных вариантов, которые нужно попробовать перед сбоем. Вы можете взглянуть на демонстрацию регулярных выражений и щелкнуть отладчик регулярных выражений слева, чтобы увидеть пример поведения механизма регулярных выражений.

Текущее регулярное выражение может быть записано как 

 r'^(w )s|{3}s(w )s|{3}s(.*)'

Смотрите демонстрацию регулярных выражений, где будет совпадение, если вы удалите пробел и . во втором поле.

Подробные сведения:

  • ^ — начало строки (не обязательно с re.match )
  • (w ) — (Группа 1) 1 буквы / цифры / подчеркивания
  • s — пробел
  • |{3} — 3 символа канала
  • s(w )s|{3}s — см. Выше ( (w ) создает группу 2)
  • (.*) — (Группа 3) любые символы 0 , отличные от символов разрыва строки.