이클립스에서 코드를 작성하면 일부 문자열을 찾기 위해 CTRL-F을 수행 할 때 일반 단어의 대소 문자를 구별하는 표준화 된 옵션과는 별도로 정규식 검색 옵션도 있습니다 (메모장에 ++도 있음) .일반 정규 표현식을 최적화 할 수있는 방법이 있습니까?
나는 한두 번 시도했는데 일반적으로 결과는 거의 즉각적입니다. 그러나 결국 코드 파일은 엄청난 것이 아니며, 가장 큰 파일은 500 줄을 넘지 않으며 대부분의 줄은 절반 이하로 채워져 있습니다. 어떤 사용자 지정 정규 표현식이 큰 텍스트 (예 : 10-15MB 크기)에서 훨씬 빠르게 실행되도록 최적화 할 수있는 방법이 있습니까?
Rabin-Karp 또는 접미사 트리와 같은 표준화 된 검색 알고리즘이 여기에 적용되지 않기 때문에 어떤 방법도 생각할 수 없습니다!
접미어 트리가이 문제에 적합한 알고리즘이 아니라고 생각합니까? http://en.wikipedia.org/wiki/Suffix_tree에서 :
실수의 특정 번호가 허용되는 경우 [접미사 트리가있다] 문자열의 위치를, S에서 문자열을 찾는 예를 들어, 여러 작업을 신속하게 수행 할 수 있습니다 구성, 찾기가 일반에 대한 일치하면 표현 패턴 등
변형 된 Boyer-Moore 문자열 검색 알고리즘도 가능할 것이라고 생각합니다.
정규 표현식이 Eclipse에서 구현되는 방법과 왜 그렇게 느린 지에 대해서는 잘 모릅니다. 다음은 몇 가지 생각입니다.
우선, 알아 두어야 할 몇 가지 개념이 있습니다 : Nondeterministic finite automaton (NFA) 및 Deterministic finite automaton (DFA). 이론적으로 정규 표현식, NFA 및 DFA는 동등하므로 언어 (문자 시퀀스)를 설명하는 능력이 정확히 동일 함을 의미합니다. 이것은 그 중 하나가 다른 것으로 변환 될 수 있음을 의미합니다 (this site 참조).
일반 표현식은 DFA로 변환하여 구현할 수 있으며 DFA를 사용하여 텍스트를 일치시키는 데는 선형 시간 만 걸립니다 (예 : KMP와 같은 많은 문자열 일치 알고리즘이 실제로 특수 DFA 임). 그러나 문제는 대부분의 정규 표현식 구현에서 역 참조와 같은 기능을 도입하여 DFA를 사용할 수 없게 만드는 것입니다.
따라서 이러한 복잡한 기능을 삭제할 수 있다면 빠른 정규식을 구현하는 것이 가능합니다 (선형 시간으로 일치 시키십시오). this article에서 자세한 내용을 확인할 수 있습니다.
"모든 사용자 제공 정규식"이라고 할 때 사용자에게 나쁜 정규 표현식을 쓸 수있는 백지 수표를 제공합니다. 예를 들어 많은 역 추적, 마지 막 한정 기호 등이 있습니다. 이를 최적화 할 수있는 방법이 없습니다. 같은 방식으로 코드를 빠르게 실행하는 컴파일러를 작성하는 것은 불가능합니다. – dasblinkenlight
역 참조를 제외하고 정규식을 약간 제한 할 수 있다면 성능을 크게 향상시킬 수 있습니다. http://swtch.com/~rsc/regexp/ –