wyrażenie regularne przechodzi w nieskończonej pętli

Question

ja parsowania (species) Nazwy postaci:

Parus Ater 
H. sapiens 
T. rex 
Tyr. rex 

które normalnie mają dwie kadencje (dwumianowego), ale czasami mają 3 lub więcej.

Troglodytes troglodytes troglodytes 
E. rubecula sensu stricto 

pisałem

[A-Z][a-z]*\.?\s+[a-z][a-z]+(\s*[a-z]+)* 

który pracował przez większość czasu, ale od czasu do czasu poszedł do nieskończonej pętli. Zajęło to trochę czasu, aby wyśledzić, że to było w dopasowywaniu regex i wtedy zdałem sobie sprawę, że to literówka i powinno Pisałem

[A-Z][a-z]*\.?\s+[a-z][a-z]+(\s+[a-z]+)* 

która wykonuje poprawnie.

Moje pytania są następujące:

• dlaczego ta pętla się stało?
• Czy istnieje sposób, w jaki mogę sprawdzić podobne błędy regex przed uruchomieniem programu? W przeciwnym razie może być trudne przechwycenie ich przed dystrybucją prgram i spowodowanie problemów.

[Uwaga: nie potrzebuję bardziej ogólnego wyrażenia dla gatunków - istnieje formalna ponad 100 liniowa specyfikacja dla nazw gatunków - to był tylko filtr początkowy].

UWAGA: Problem pojawił się, ponieważ chociaż większość nazw została wyodrębniona dokładnie na 2 lub czasami 3/4 terminów (tak, jak pisano kursywą), było kilka fałszywych alarmów (np. "Homo sapiens lives in big cities like London"), a mecz zakończył się niepowodzeniem na "L". ]

UWAGA: Podczas debugowania tego stwierdziłem, że regex często kończył się, ale był bardzo powolny (np. W krótszych ciągach docelowych). Jest cenne, że znalazłem ten błąd przez przypadek patologiczny. Nauczyłem się ważnej lekcji!

Answer 1

Aby odpowiedzieć na pierwszą część pytania, należy przeczytać na stronie catastrophic backtracking. Zasadniczo, to, co się dzieje, to zbyt wiele sposobów dopasowania wyrażenia regularnego do łańcucha znaków, a analizator składni nieustannie śledzi go, aby spróbować go uruchomić.

W twoim przypadku była to prawdopodobnie zagnieżdżona repitalizacja: (\s*[a-z]+)* Co prawdopodobnie spowodowało kilka bardzo dziwnych pętli. Jak zauważył Qtax, trudno powiedzieć bez większej ilości informacji.

Druga część pytania jest, niestety, niemożliwa do udzielenia odpowiedzi. Jest to w zasadzie Halting problem. Ponieważ Wyrażenia regularne są w istocie skończoną maszyną stanu, której dane wejściowe są ciągiem, nie można utworzyć ogólnego rozwiązania, które przewiduje, które wyrazy regularne przejdą katastrofalnie, a które nie.

Co do wskazówek, jak przyspieszyć działanie wyrażeń regularnych? To wielka puszka robaków. Spędziłem dużo czasu na studiowanie wyrażeń regularnych na własną rękę, a jakiś czas ich optymalizacji, i oto co znalazłem na ogół pomaga:

1. skompilować wyrażenia regularne poza swoimi pętlami, jeśli obsługiwana językowych to.
2. Jeśli to możliwe, dodaj anchors, gdy wiesz, że są przydatne.Zwłaszcza ^ dla początku napisu. Zobacz także: Word Boundaries
3. Unikaj zagnieżdżonych powtórzeń, takich jak dżuma. Jeśli musisz to zrobić (co zrobisz), zrób wszystko, co w twojej mocy, aby podać wskazówki do silnika, aby sparować wszelkie niezamierzone cofnięcia.
4. Skorzystaj z konstrukcji smakowych, aby przyspieszyć działanie. Jestem stronniczy od Non-Capturing groups i possessive quantifiers. Nie pojawiają się w każdym smaku, ale kiedy to robią, powinieneś ich używać. Sprawdź również: Atomic Groups
5. Zawsze uważam, że to prawda: Im dłużej pojawia się wyrażenie regularne, tym więcej kłopotów sprawi, że będzie on skuteczny. Wyrażenia regularne są świetnym i potężnym narzędziem, są niczym super elegancki młotek. Don't fall into the trap of seeing everything as a nail. Czasami funkcja struny, której szukasz, znajduje się tuż pod twoim nosem.

Mam nadzieję, że to pomoże. Powodzenia.

Answer 2

Dla pierwszego regex:

[A-Z][a-z]*\.?\s+[a-z][a-z]+(\s*[a-z]+)* 

Katastrofalna wycofywania się dzieje z powodu (\s*[a-z]+)* Jak podkreślono w komentarzu. Jednak jest to prawdą tylko wtedy, gdy sprawdzasz poprawność ciągu znaków za pomocą String.matches(), ponieważ jest to jedyny przypadek, w którym napotkanie nieprawidłowego znaku powoduje, że silnik próbuje wykonać pętlę zwrotną, zamiast zwracać zapętlenie (pętla Matcher).

Pozwól nam dopasować nieprawidłowy ciąg przeciwko (\s*[a-z]+)*:

inputstringinputstring; 

(Repetition 1) 
\s*=(empty) 
[a-z]+=inputstringinputstring 
FAILED 

Backtrack [a-z]+=inputstringinputstrin 
(Repetition 2) 
\s*=(empty) 
[a-z]+=g 
FAILED 

(End repetition 2 since all choices are exhausted) 
Backtrack [a-z]+=inputstringinputstri 
(Repetition 2) 
\s*=(empty) 
[a-z]+=ng 
FAILED 

Backtrack [a-z]+=n 
(Repetition 3) 
\s*(empty) 
[a-z]+=g 
FAILED 

(End repetition 3 since all choices are exhausted) 
(End repetition 2 since all choices are exhausted) 
Backtrack [a-z]+=inputstringinputstr 

Do tej pory powinieneś mieć zauważyć problem. Zdefiniujmy T(n), ponieważ ilość pracy do sprawdzenia ciągu o długości n nie pasuje do wzorca. Od metody backtrackingu wiemy, T(n) = Sum [i = 0..(n-1)] T(i). Z tego możemy wywnioskować T(n + 1) = 2T(n), co oznacza, że ​​proces wycofywania jest wykładniczy w złożoności czasu!

Zmiana * do +unika problemu całkowicie, ponieważ wystąpienie powtórzeń można rozpocząć jedynie na granicy między znakiem spacji oraz znaków alfabetu angielskiego. W przeciwieństwie do tego, pierwsze wyrażenie regularne umożliwia wystąpienie powtórzenia rozpoczynającego się pomiędzy dwoma znakami alfabetu.

Aby to zademonstrować, (\s+[a-z]+\s*)* da ci piekło wycofania, gdy nieprawidłowy ciąg wejściowy zawiera wiele słów, które są rozdzielone wieloma kolejnymi spacjami, ponieważ pozwala na uruchomienie wielu instancji powtarzania. Jest to zgodne ze wzorem: , gdzie b jest maksymalną liczbą kolejnych spacji (minus 1), a d jest liczbą sekwencji spacji. Jest mniej surowy niż pierwsze wyrażenie, które masz (wymaga co najmniej jednego alfabetu Englsh i jednej spacji na jedno powtórzenie, w przeciwieństwie do jednego alfabetu angielskiego na powtórzenie w pierwszym wyraŜeniu regularnym), ale nadal stanowi problem.