F#으로 구현된 정규식 엔진, 기존 엔진보다 빠르다!

RE#는 Brzozowski derivatives를 핵심 기술로 활용하여 정규식의 교집합, 여집합 연산을 지원한다. 특히, 문자열의 각 문자에 대한 파생(Derivative)을 계산하여 매칭 여부를 판단하는 방식으로, 복잡한 부울 연산자(Boolean Operators)를 O(n) 시간 복잡도 내에서 처리한다. 이러한 접근 방식은 기존의 백트래킹 엔진(Backtracking Engine)이 가진 ReDoS 공격(Denial of Service Attacks) 취약점을 해결하고, 정규식의 성능을 향상시키는 데 기여한다.

RE#는 Minterm 압축 기술을 통해 성능을 극대화한다. 문자 집합을 동등 클래스로 분할하여 각 클래스에 Minterm ID를 할당하고, 해당 ID를 기반으로 파생을 계산한다. 이러한 방식은 유니코드(Unicode)와 같이 다양한 문자를 처리해야 하는 경우, 필요한 상태 전이(State Transition)의 수를 획기적으로 줄여 메모리 사용량을 감소시키고, 전반적인 정규식 처리 속도를 향상시킨다. 특히, \w와 같은 문자 클래스에서 그 효과가 두드러진다.

RE#는 왼쪽-최장(Leftmost-longest) 매칭 방식을 채택하여 정규식의 정확성을 높인다. 이는 여러 가능한 매칭 결과 중 가장 왼쪽에서 시작하고 가장 긴 문자열을 선택하는 방식이다. 이러한 접근 방식은 정규식의 의미를 명확하게 정의하고, 예상치 못한 매칭 결과를 방지하여 개발자가 정규식을 더 쉽게 이해하고 사용할 수 있도록 돕는다. 또한, 부울 연산자와의 호환성을 보장하여 정규식의 조합 및 확장을 용이하게 한다.

백트래킹 엔진(Backtracking Engine)은 복잡한 기능을 제공하지만, ReDoS 공격(Denial of Service Attacks)에 취약하고 성능이 불안정하다는 단점이 있다. 반면, RE#는 선형 시간 복잡도(Linear Time Complexity)를 보장하며, 교집합 및 여집합 연산을 지원하여 이러한 문제를 해결한다. 또한, RE#는 DFA(Deterministic Finite Automata) 기반으로 설계되어, NFA(Nondeterministic Finite Automata) 기반 엔진보다 빠르고 안정적인 성능을 제공한다.

RE#는 Lookarounds를 지원하여 특정 문맥(Context)을 기반으로 매칭을 수행할 수 있다. 이는 정규식 엔진의 유연성을 높이는 중요한 기능이며, RE#는 이를 위해 파생(Derivative)을 활용하여 상태에 문맥 정보를 인코딩한다. 이러한 접근 방식은 O(n) 시간 복잡도를 유지하면서도, 다양한 형태의 Lookarounds를 지원할 수 있게 한다. 다만, 임의의 중첩된 Lookarounds는 지원하지 않으며, 이는 성능 최적화를 위한 트레이드오프(Trade-offs)이다.