정규 표현식의 성능이 좋지 않습니까?

게시자: Eyal Schneider, 2009년 5월 21일 java.util.regex 패키지는 Java 버전 1.4에 추가되었습니다. 그것은 매우 강력한 도구이며 올바르게 사용하려면 마스터가 되어야 합니다. 정규 표현식이 true 인 경우에도지능적으로 작성하지 않으면 속도가 매우 느려질 수 있습니다. 문제의 원인을 이해하고 싶다면 계속 읽으세요. 아니면 페이지 끝으로 스크롤하여 Java의 정규식 성능을 향상시키는 데 유용한 10가지 팁을 찾을 수 있습니다.

정말 그렇게 느린가요?

문자 "a"와 "b"가 포함된 행만 선택한다고 가정해 보겠습니다. 올바른 해결 방법은 다음과 같습니다. (a*b*)* 그러나 예를 들어 "aaaaaaaaaaaaaaaaaaaaaaaaaaaax" 문자열을 사용하여 표현식을 실행하면 완료되기까지 몇 분 정도 걸리며 일치하는 항목이 없다고 보고됩니다. 물론 이 경우 가장 좋은 정규식은 다음과 같습니다. (a|b)* 동일한 문자열을 사용하는 내 컴퓨터에서는 1밀리초도 채 걸리지 않습니다. 여기에는 분명히 성능 문제가 있습니다.

왜 이런 일이 발생합니까?

대부분의 정규 표현식 엔진과 마찬가지로 Java는 NFA(Non-Deterministic Finite Automata) 접근 방식을 사용합니다. 엔진은 정규식 구성 요소를 하나씩 검색하고 그에 따라 입력 문자열을 진행합니다. 그리고 그는 "막다른 골목"에 도달하면 적절한 대안을 찾기 위해 처음으로 돌아갈 수 있습니다. 수량자( *, +, ? ) 및 교대(예: a|b|c|d ) 와 같은 정규 구조를 사용하여 대체 결과를 얻을 수 있습니다 . 이 연구 기법을 역추적이라고 합니다. 위의 끔찍한 예에서 엔진은 일치하는 항목이 없다는 것을 깨달을 때까지 기호 "a"의 모든 계열 분해를 더 작은 계열로 실제로 살펴봅니다. 이 예에서는 역추적 알고리즘이 입력 문자열의 길이에 따라 기하급수적인 시간 추정 결과를 얻을 수 있는 방법을 보여줍니다. 이는 또한 NFA의 중요한 속성을 보여줍니다. 패턴과 거의 일치하는 최악의 경우가 항상 존재한다는 것입니다. 일치하는 항목이 발견되면 검색이 중지됩니다. 정규식에 사용되는 또 다른 주요 접근 방식은 DFA(Deterministic Finite Automaton)입니다. 이 접근 방식에서 정규식은 역추적 없이 입력 문자열을 문자별로 탐색하는 데 사용되는 자동 장치를 실제로 구축합니다. 이는 정규식의 복잡성에 관계없이 전체 입력에 선형 시간을 제공합니다. NFA에서와 같이 일치하는 문자열을 순차적으로 검색하는 대신 DFA는 병렬 검색을 시뮬레이션합니다. 그렇다면 왜 Java(및 .NET, Perl, Python, Ruby, PHP 등)에서는 훨씬 더 나은 동작을 제공하는 DKA가 아닌 NKA를 사용합니까? 그 이유는 NKA가 다음과 같은 여러 가지 중요한 이점을 갖고 있기 때문입니다.

더 빠르게 컴파일되고 훨씬 적은 메모리가 필요합니다.
몇 가지 유용한 기능을 허용합니다( 자세한 내용은 Sun의 튜토리얼 참조 ).

그룹 캡처 및 백링크
위치 확인
확장 수량자(탐욕스럽고 게으른)

인기 있는 용어인 NKA와 DKA는 정규 표현식의 맥락에서 사용될 때 부정확하다는 점에 유의하는 것이 중요합니다. 이론적으로 이 두 모델은 동일한 컴퓨팅 성능을 갖습니다. 이는 다른 오토마타 모델에서는 표현할 수 없는 정규식을 하나의 오토마타 모델에서 작성할 수 없다는 것을 의미합니다. 실제로는 두 가지 유형의 구현이 의미론적으로 달라지도록 더 많은 기능이 필요합니다. NKA 엔진은 더 많은 유연성을 제공하므로 컴퓨팅 성능 면에서 DKA보다 우수합니다. DFA의 속도와 NFA의 고유한 기능으로 인해 정규식을 구현하는 "미리 만들어진" 방법이 두 가지 더 있습니다. 일부 구현에서는 두 가지 유형을 모두 사용하고(예: 런타임에 특정 엔진을 선택하는 GNU egrep) 일부는 모든 이점을 갖춘 진정한 하이브리드 버전(예: Tcl 정규식)을 구현했습니다.

조언

다음은 Java에서 정규식 효율성 문제를 방지하는 방법에 대한 몇 가지 팁입니다. 그들 중 다수는 수익을 줄이는 것을 목표로 합니다.

1) 사전 컴파일

진부하지만 언급할 가치가 있습니다. 정규식을 두 번 이상 사용하는 경우 미리 컴파일해야 합니다.

// компиляция p = Pattern.compile(regex, flags); … // использование Matcher a = p.matcher(input);

2) 게으른 수량자 vs 탐욕스러운 수량자

기본적으로 수량자( * + ? )는 탐욕적입니다. 이는 가능한 가장 긴 시퀀스와 일치를 시작한 다음 필요한 경우 점차적으로 다시 작업한다는 의미입니다. 일반적으로 일치 항목이 짧다는 것을 미리 알고 있는 경우 지연 수량자를 사용해야 합니다. 가장 작은 일치 항목부터 시작하여 필요한 경우 더 멀리 이동합니다. "hello" 시퀀스와 일치하는 행만 찾고 싶다고 가정해 보겠습니다. 일반 .*hello.*는 모든 작업을 올바르게 수행하지만 "hello"가 일반적으로 텍스트 시작 부분에 더 가깝게 나타난다는 것을 알고 있으면 .*?hello.*가 평균적으로 더 빠르게 작동합니다.

3) 가능하다면 초탐욕 수량자를 사용하세요.

성능에 영향을 주지만 일반 동작에는 영향을 주지 않는 게으른 수량자와 달리, 초탐욕적 수량자는 실제로 정규 표현식의 의미를 변경할 수 있습니다. * 대신 *+ 를 사용하면 첫 번째 일치 항목은 탐욕적(즉, *인 것처럼 가능한 가장 큰 일치 )이 되지만, 전체 검색이 실패하더라도 실패하면 폴백이 발생하지 않습니다. 언제 유용할까요? 따옴표로 묶인 텍스트를 찾아야 한다고 가정해 보겠습니다. 일반 \"[^\"]*\"는 잘 작동합니다. 그러나 부정적인 경우(예: "bla bla bla)"에서는 불필요한 들여쓰기가 됩니다. \"[^\"]*+\"를 사용하면 들여쓰기가 제거됩니다 . 표현의 의미를 바꾸지 않고 롤백합니다. 독립적인 그룹화는 동일한 효과를 얻고 더 많은 제어를 제공합니다( Sun의 자습서 참조 ).

4) 그룹 캡처를 피하십시오

괄호 안의 표현식은 기본적으로 그룹으로 간주됩니다. 이는 성능에 약간의 영향을 미칩니다. ( 대신 (?: 로 시작하여 가능할 때마다 그룹을 "캡처할 수 없게" 만듭니다 .

5) 인터리빙을 현명하게 사용하세요

인터리브가 사용되는 경우(예: Paul|Jane|Chris ) 엔진이 옵션을 일치시키려고 시도하는 순서는 해당 옵션이 나타나는 순서와 동일합니다. 이 기능을 활용하고 가장 일반적인 옵션을 시작 부분에 더 가깝게 배치할 수 있습니다. 이렇게 하면 평균 긍정적 응답 시간이 향상됩니다.

6) 모호함을 피하라

입력 문자열에서 서로 다른 일치 항목 수를 최소화하는 방식으로 정규식을 작성합니다. 예를 들어, 기사 시작 부분에 제공된 정규식 (a*b*)*를 사용 하면 "aabb" 문자열이 너무 많은 방식으로 해석될 수 있습니다. 반면 (a2b2) (a1)(a1)(b1)(b1) (a2)(b2) (a1)(a1b2) etc… Regexp (a|b)*는 고유한 문자열만 해석합니다. 긍정적으로 조합합니다. 이는 거의 일치하는 경우 수익을 줄이는 데 매우 중요합니다.

7) 미리보기

미리보기를 사용하면 현재 위치의 왼쪽/오른쪽에 시퀀스에 대한 제한을 추가할 수 있습니다. 특히, 부정적인 예측을 사용하면 일부 시퀀스가 포함되지 않은 행을 검색할 수 있습니다(이것이 없으면 어떻게 될까요!). 이것이 어떻게 생산성을 높이는 데 도움이 됩니까? 링크 태그에서 URL을 가져오고 싶다고 가정해 보겠습니다. 다음 정규식을 고려하십시오. a .* href=(\S*).*/ 일반 태그의 경우 이 표현식은 텍스트에 "href" 속성이 포함된 경우에만 주소와 일치합니다(\S는 구분 기호를 제외한 모든 문자에 사용됨). 그러나 예를 들어 일부 특이한 태그에서는 롤백이 발생합니다. 예: “a href= href=href=… href=뭔가.” 다음 정규식은 표현식의 ".*"를 "href"와 일치하지 않는 것으로 바꿀 때 이러한 일이 발생하는 것을 방지합니다. a ((?!href).)* href=(\S*)((?!href).)*/

8) 길이 지정

Java에는 정규식에서 얻은 최소 및 최대 길이에 대해 입력 문자열의 길이를 확인하는 정규식 최적화 프로그램이 포함되어 있습니다. 이를 통해 경우에 따라 검색을 즉시 중지할 수 있습니다. 이 메커니즘을 지원하려면 가능할 때마다 반복 횟수를 지정해야 합니다. 예를 들어 [01]{6}은 6자 길이의 모든 이진 문자열과 일치합니다.

9) 동일한 라인 선택

때때로 동일한 문자열이 그룹이나 대안 내부에 숨겨져 있습니다. (hello|hell|heel) 이 표현식은 다음과 같이 단순화될 수 있습니다. he(llo|ll|el) 이렇게 하면 정규식 최적화 프로그램에 더 많은 정보를 제공합니다.

10) 정규식 테스트

성능이 중요한 응용 프로그램에서 정규식을 사용할 경우 먼저 정규식을 테스트하는 것이 현명할 수 있습니다. 다양한 입력 데이터에 대한 표현식을 테스트하는 마이크로 벤치마크를 작성하세요. 다양한 길이의 데이터와 샘플과 거의 일치하는 데이터를 테스트해야 합니다.

연결:

http://java.sun.com/docs/books/tutorial/essential/regex/index.html http://www.javaworld.com/javaworld/jw-09-2007/jw-09-optimizingregex.html?page =1 http://www.softec.st/en/OpenSource/DevelopersCorner/RegularExpressions/RegularExpressionEngines.html http://www.devarticles.com/c/a/Java/NFA-DFA-POSIX-and-the-Mechanics -표현 처리/