나는 그것으로부터 배웠다이 기사역추적을 구현하는 정규식 엔진의 경우 경우에 따라 ripgrep매우 느릴 수 있지만 그 이유를 잘 모르겠습니다. 다음 Python 코드 조각(링크된 기사의 예)이 매우 느린 이유를 간략하게 설명할 수 있습니까?
>>> import re
>>> re.search('(a*)*c', 'a' * 30)
답변1
기본적으로 문제는 a패턴의 이중 반복입니다. 이 섹션에서는 주변 a*의 여러 가지를 허용합니다.a(·)* 반품패턴은 얼마든지 허용됩니다.
a이를 통해 패턴을 문자열과 일치시키는 다양한 방법을 사용할 수 있습니다 . (Five's)와 같은 문자열은 b, , , , ...로 일치될 수 있다는 점을 지금은 무시하십시오. 문자열을 일치시키는 방법은 기하급수적으로 많습니다.aaaaaa(aaaaa)(aaaa)(a)(aaa)(aa)(aaa)(a)(a)(aa)(aaa)(aa)(aa)(a)
결국 b, 역추적 엔진은 일치하는 방법을 시도 a하고 찾을 수 없음을 깨닫고 b한 단계 뒤로 돌아가서 다른 방법을 시도하고 찾을 수 없음을 깨닫고 b... 모든 것을 소진하는 데 너무 오래 걸리는 방법을 사용하게 됩니다. 가능한 조치를 취한 다음 실패했습니다.
이 주제에 관해 내가 쓸 수 있는 것보다 온라인에 훨씬 더 좋은 기사가 있습니다. 가서 다음 내용을 읽어보세요:
폭주 정규 표현식: 재앙적인 역추적저자 Jan Goyvaerts는 이 문제와 이를 방지하는 몇 가지 방법을 설명합니다.
정규식 일치는 간단하고 빠를 수 있습니다(하지만...)Russ Cox도 이 문제에 대해 설명하고 역추적을 사용하지 않고 정규식을 유한 오토마타로 구현하는 것이 이 문제의 영향을 받지 않는 방법을 설명합니다. 사진도 있습니다.
실제로는 가능하다면 문자열을 일치시키는 다양한 방법을 허용하는 패턴을 피하세요. 여기의 예는 중첩된 반복이 없기 (a*)*c때문에 분명히 어리석은 것입니다 a*c.