.NET 정규식 엔진의 검색 성능 최적화

Question

내가 주변에 35,000 문자열

와리스트 컬렉션이

일반 문자열은 다음과 같습니다

이

"<i>füüs</i>ampri tähis;lüh ld-st<i>anno</i>, aastal;<i>maj</i> lüh pr-st<i>argent</i>, raha (kursisedelitel)" 

기본적으로이 문자열이 에스토니아어 단어의 무리를 포함 :

사용자가 35,000 개의 문자열에서 RegExp 검색을 수행 할 수 있도록 허용해야합니다.

/ab.*/ 표현식을 사용하여 검색을 수행하면 검색 결과가 어떻게 빨리 (미만 1.5 초) 검색 두번째 만들 수 있습니다 econd

내가 /.*ab/ 표현식을 사용하여 검색을 수행 할 경우, 다음 검색은 10 초

내 질문은 주위에 소요? 이 링크에 문제 렌더링이 같은

이

사본이 전체 URL을 붙여 성능 향상을 위해 당신에게

http://en.csharp-online.net/CSharp_Regular_Expression_Recipes -Compiling_Regular_Expressions을

Answer 1

사용 compiled regular expressions 대단히 감사합니다, 보인다.

Answer 2

나는 문자열을 역순으로 저장하고/ba를 사용하여 해당 문자열을 검색 할 수 있다는 미친 생각이 있습니다. */사용자가 /를 입력 한 경우. * ab /.

Answer 3

두 번째 표현식은 'ab'와 그 앞에있는 모든 문자 (새 줄 제외)와 일치합니다./ab/만 검색하면 일치 항목의 색인을 가져 와서 결과와 일치하는 문자열보다 앞선 문자열의 일부를 연결시킬 수 있습니다.

Answer 4

정규식이 어떻게 다르게 처리되는지를 보여줍니다. 귀하의 예에 따라 그 설명하려면

• /.*ab/이 표현은 두 개의 하위 표현의 .*과 문자 ab에 구성되어 있습니다. 이것은 다음과 같이 처리됩니다 : 일반적인 욕심쟁이 모드에서는 모든 퀀텀과 일치가 최대로 확장되는 경우 .*이 먼저 전체 문자열과 일치합니다. 그런 다음 다음과 일치하도록 시도합니다 ab. 그러나 그것이 가능하지 않기 때문에 (우리는 이미 문자열의 끝 부분에 있습니다.) 역 추적은 두 하위 표현식이 일치하는 마지막 지점을 찾는 데 사용됩니다. 따라서 .*의 일치가 한 문자 씩 줄어들고 다시 ab이 테스트됩니다. 전체 표현식을 일치시킬 수없는 경우 전체 표현식이 일치 할 때까지 .*의 일치가 다시 한 문자 씩 줄어 듭니다. 최악의 경우 문자열에 ab이 없으며 일치가 불가능하다고 판단 할 때까지 n +1 백 트랙과 ab에 대한 추가 테스트를 수행합니다.

• /ab.*/이 표현식도 두 가지 하위 표현식으로 구성됩니다. 하지만 여기서 주문은 변경됩니다. 처음에는 문자가 ab이고 .*이 아닙니다. 이 알고리즘은 다음과 같이 처리됩니다. 알고리즘은 먼저 한 문자를 다른 문자와 비교하여 문자 ab을 찾습니다.일치하는 항목이 있으면 .*과 일치하는 항목을 찾기 쉽습니다.

두 정규 표현식의 주요 차이점은 두 번째 정규식은 처음에는 정적 인 부분을, 마지막에는 가변 부분을 가지고 있다는 점입니다. 이렇게하면 뒤로 추적 할 필요가 없습니다.

시각적으로 차이를 확인하려면 RegexBuddy과 같은 정규식 분석 도구를 사용해보십시오.

Answer 5

느린 .*ab 표현에 대해 제안 할 수있는 두 가지 가능한 수정 사항이 있습니다.

이 테스트 문자열 "1234567890 ab 1234567890"을 사용하여 Regex Hero의 벤치마킹 기능을 사용하여 테스트를 수행했습니다.

. 배 빠르게 원래보다

^.*ab 
RegexOptions.None 

또는

B. 원래보다 8 배 빠름

.*ab 
RegexOptions.RightToLeft 

가끔씩 실험비가 지불됩니다. RightToLeft 옵션이 내 '아 하!'였습니다. 순간. 그것은 본질적으로 거대한 백 트랙킹을 방지하여 다른 ab.* 표현과 동일한 성능을 본질적으로 반환합니다.