RE#: 우리가 F#으로 세계에서 가장 빠른 정규식 엔진을 만든 방법
**RE#**는 **F#**으로 개발된 새로운 정규 표현식 엔진으로, 기존 닷넷 및 산업용 엔진들을 능가하는 성능을 보이며 교집합(&), 여집합(~) 같은 불리언 연산자와 제한적 형태의 문맥 인지형 룩어라운드를 지원합니다.
핵심 기술로는 1964년 Janusz Brzozowski의 정규식 도함수(derivatives) 개념을 활용해, **NFAs 없이 직접 DFA를 지연 생성(lazy DFA construction)**하며, 문자 집합을 동치 클래스(민텀)로 압축해 메모리와 속도 효율을 극대화했습니다.
또한, 양방향 스캔을 통한 좌측 최장 매칭(leftmost-longest match) 알고리즘으로, 기존 백트래킹 엔진의 비결정적이고 비효율적인 매칭 문제를 해결하고, 수학적으로 엄밀한 집합 연산 기반의 정규식 의미론을 구현해 일관된 결과를 제공합니다.
RE#는 .NET의 SIMD 최적화 기능과 F#의 대수적 자료구조를 활용해 실용성과 성능을 동시에 달성했으며, 오픈소스로 공개되어 있어 실제 개발 및 보안 분야에서 복잡한 패턴을 효율적으로 다룰 수 있는 혁신적인 도구로 평가받고 있습니다.