Regex для соответствия большому узору

Question

Я новичок в regex, я пытаюсь сопоставить некоторый узор, но он работает для меньшего шаблона len, но он застревает для большого шаблона (выглядит как проблема Catastrophic Backtracking).

Ниже моя строка,

world0 world1 world2 world3 world4 world5 world6 world7 world8 world9 world10 
world11 world12 world13 world14 world15 world16 world17 world18 world19 world20 
world21 world22 world23 world24 world25 world26 world27 world28 world29 world30 
world31 world32 world33 world34 world35 world36 world37 world38 world39 world40 
world41 world42 world43 world44 world45 world46 world47 world48 world49 world50 
world51 world52 world53 world54 world55 world56 world57 world58 world59 world60 
world61 world62 world63 world64 world65 world66 world67 world68 
world69 world70 world71 world72 world73 world74 world75 world76 world77 world78 
world79 world80 world81 world82 world83 world84 world85 world86 world87 world88 
world89 world90 world91 world92 world93 world94 world95 world96 world97 world98 
world99 world0 world1 world2 world3 world4 world5 world6 world7 world8 world9 
world10 world11 world12 world13 world14 world15 world16 world17 world18 world19 
world20 world21 world22 world23 world24 world25 world26 world27 world28 world29 
world30 world31 world32 world33 world34 world35 world36 world37 world38 world39 
world40 world41 world42 world43 world44 world45 world46 world47 world48 world49 
world50 world51 world52 world53 world54 world55 world56 world57 world58 world59 
world60 world61 world62 world63 world64 world65 world66 world67 world68 world69 
world70 world71 world72 world73 world74 world75 world76 world77 world78 world79 
world80 world81 world82 world83 world84 world85 world86 world87 world88 world89 
world90 world91 world92 world93 world94 world95 world96 world97 world98 

Теперь мой шаблон матча список строки позволяет сказать match_list, мой ожидаются выход, он должен соответствовать подстроке сверху, который имеет все строки, определенные в match_list строки

Small list = ["world0","world1", "world2"] 

Я попытался следующий образец

(?=((\b(?:world0|world1|world2)\b[\w\s]*?){3})) 

выше один отлично работает и соответствует выход правилен, который я ожидал,

[0-20] `world0 world1 world2` 

[7-796] `world1 world2 world3 world4 world5 world6 world7 world8 world9 world10 
world11 world12 world13 world14 world15 world16 world17 world18 world19 world20 
world21 world22 world23 world24 world25 world26 world27 world28 world29 world30 
world31 world32 world33 world34 world35 world36 world37 world38 world39 world40 
world41 world42 world43 world44 world45 world46 world47 world48 world49 world50 
world51 world52 world53 world54 world55 world56 world57 world58 world59 world60 
world61 world62 world63 world64 world65 world66 world67 world68 world69 world70 
world71 world72 world73 world74 world75 world76 world77 world78 world79 world80 
world81 world82 world83 world84 world85 world86 world87 world88 world89 
world90 world91 world92 world93 world94 world95 world96 world97 world98 world99 world0` 

[14-803] `world2 world3 world4 world5 world6 world7 world8 world9 world10 world11 
world12 world13 world14 world15 world16 world17 world18 world19 world20 world21 
world22 world23 world24 world25 world26 world27 world28 world29 world30 world31 
world32 world33 world34 world35 world36 world37 world38 world39 world40 world41 
world42 world43 world44 world45 world46 world47 world48 world49 world50 world51 
world52 world53 world54 world55 world56 world57 world58 world59 world60 world61 
world62 world63 world64 world65 world66 world67 world68 world69 world70 world71 
world72 world73 world74 world75 world76 world77 world78 world79 world80 world81 
world82 world83 world84 world85 world86 world87 world88 world89 world90 world91 
world92 world93 world94 world95 world96 world97 world98 world99 world0 world1` 

[790-810] `world0 world1 world2` 

Но для большого списка = [ 'world0', 'мира1', 'world2', 'world3', 'world4', 'world5', «world6 «world7», «world8», «world9», «world10», «world11», «world12», «world13», «world14», «world15», «world16», «world17», «world18», 'world19', 'world20', 'world21', 'world22', 'world23', 'world24', 'world25', 'world26', 'world27', 'world28', 'world29', 'world30', 'world31 «world32», «world33», «world34», «world35», «world36», «world37», «world38», «world39», «world40», «world41», «world42», «world43», 'world44', 'world45', 'world46', 'world47', 'world48', 'world49']

Пробовал следующий шаблон

(?=((\b(?:world0|world1|world2|world3|world4|world5|world6|world7|world8|world9|wor ld10|world11|world12|world13|world14|world15|world16|world17|world18|world19|world20|world21|world22|world23|world24|world25|world26|world27|world28|world29|world30|world31|world32|world33|world34|world35|world36|world37|world38|world39|world40|world40|world41|world42|world43|world44|world45|world46|world47|world48|world49|world50)\b[\w\s]*?){49})) 

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

Answer 1

Кажется, за последний шаблон, который вы хотите, чтобы соответствовать всем мирам с числовым индексом, чем 50. Таким образом, вместо

(?=((\b(?:world0|world1|world2|world3|world4|world5|world6|world7|world8|world9|wor ld10|world11|world12|world13|world14|world15|world16|world17|world18|world19|world20|world21|world22|world23|world24|world25|world26|world27|world28|world29|world30|world31|world32|world33|world34|world35|world36|world37|world38|world39|world40|world40|world41|world42|world43|world44|world45|world46|world47|world48|world49|world50)\b[\w\s]*?){49})) 

Почему не следующий (сопрягать все значения от 0-49 или 50):

(?=((\b(?:world([0-4][0-9]?|50))\b[\w\s]*?){3})) 

А вот моя попытка очистить ваше регулярное выражение основано на описании

он должен соответствовать подстроку из Abov е, который имеет все строки, определенные в match_list строке

regex = r'\bworld([0-4][0-9]?|50)\b' 
matches = re.findall(regex, "world1 world2 world50 world60") 
print matches # ['world1', 'world2', 'world50'] 

Answer 2

Первая вещь, ваша модель не так, поскольку он соответствует world0 world0 world0.

Эта проблема не может быть решена только с помощью регулярных выражений. Если я пишу шаблон (для regex module), как:

word_list = ['world0', 'world1', 'world2'] 
p = regex.compile(r''' 
    \m (\L<words>) 
    \W++ (?>\w+\W+)*? (?!\g{-1}) 
    (\L<words>) 
    \W++ (*SKIP) (?>\w+\W+)*? (?!\g{-1}|\g{-2}) 
    (\L<words>) \M 
    ''', regex.VERBOSE, words=word_list) 

for m in p.finditer(text, overlapped=True): 
    print(m.group(0)) 

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

Другой возможный подход состоит только поиск слова из списка и создать текстовые фрагменты в генераторе, когда все слова были найдены:

import regex 
from collections import deque 

data = '''He moved on as he spoke, and the Dormouse followed him: the March Hare moved into the Dormouse’s place, and Alice rather unwillingly took the place of the March Hare. The Hatter was the only one who got any advantage from the change: and Alice was a good deal worse off than before, as the March Hare had just upset the milk-jug into his plate. 
Alice did not wish to offend the Dormouse again, so she began very cautiously: `But I don’t understand. Where did they draw the treacle from?’ 
`You can draw water out of a water-well,’ said the Hatter; `so I should think you could draw treacle out of a treacle-well–eh, stupid?’ 
`But they were IN the well,’ Alice said to the Dormouse, not choosing to notice this last remark. 
`Of course they were’, said the Dormouse; `–well in.’ 
This answer so confused poor Alice, that she let the Dormouse go on for some time without interrupting it. 
`They were learning to draw,’ the Dormouse went on, yawning and rubbing its eyes, for it was getting very sleepy; `and they drew all manner of things–everything that begins with an M–‘ 
`Why with an M?’ said Alice. 
`Why not?’ said the March Hare. 
Alice was silent. 
The Dormouse had closed its eyes by this time, and was going off into a doze; but, on being pinched by the Hatter, it woke up again with a little shriek, and went on: `–that begins with an M, such as mouse-traps, and the moon, and memory, and muchness– you know you say things are “much of a muchness”–did you ever see such a thing as a drawing of a muchness?’ 
`Really, now you ask me,’ said Alice, very much confused, `I don’t think–‘ 
`Then you shouldn’t talk,’ said the Hatter.''' 

word_list = ('Dormouse', 'Hatter', 'Alice') 

def match_gen(word_list, text): 
    p = regex.compile(r'\m\L<words>\M', words=word_list) 
    d = deque() 
    occlist = [0]*len(word_list) 

    for m in p.finditer(text): 
     windex = word_list.index(m.group(0)) 
     d.append((windex, m.start())) 
     occlist[windex] += 1 

     while not(0 in occlist): 
      elt = d.popleft() 
      occlist[elt[0]] -= 1 
      yield [elt[1],m.end()],text[elt[1]:m.end()] 

for x in match_gen(word_list, data): 
    print(x) 

Преимущества, что нет больше никаких рисков катастрофических возвратов и немного использования памяти.

Примечание: Я выбираю использовать модуль регулярных выражений вместо модуля повторно, поскольку он имеет более удобные функции, как в названном списке, overlapped флаг или границы слов \m и \M, но вы можете сделать то же самое с модулем повторного (но вам нужно использовать (?=(...)) для совпадающих совпадений, \b вместо \m и \M и '|'.join(word_list) для создания чередования).

Примечание 2: Если список слов слишком долго, вы можете использовать один и тот же путь, но вместо того, чтобы использовать чередование в качестве шаблона (т.е. \L<words>), используйте только \w+ и проверить для каждого матча, если он находится в списке. Вы можете заменить начало предыдущего кода следующим образом:

def match_gen(word_list, text): 
    p = regex.compile(r'\w+') 
    d = deque() 
    occlist = [0]*len(word_list) 

    for m in filter(lambda x: x.group(0) in word_list, p.finditer(text)):