F#으로 구현된 초고속 정규 표현식 엔진 RE#, 성능과 혁신을 동시에!
by DD
4개월 전
조회수 6
RE#는 기존 엔진과 달리 교집합(&) 및 여집합(~) 연산자를 지원하며, O(n) 시간 복잡도를 보장함
Brzozowski 미분(Derivatives) 개념을 활용하여 정규 표현식의 교집합과 여집합 연산을 효율적으로 처리함
Minterm 압축(Minterm Compression) 기술을 통해 유니코드 문자 클래스를 효율적으로 처리하여 성능을 향상시킴
좌측 최장 일치(Leftmost-Longest Match) 의미론을 통해 정규 표현식의 일관성을 확보하고, 예상치 못한 동작을 방지함
RE#의 핵심 기술: Brzozowski 미분(Derivatives)
RE#는 정규 표현식의 Brzozowski 미분(Derivatives) 개념을 핵심으로 사용한다. 미분은 문자열을 처리하면서 정규 표현식을 단순화하는 방법으로, 교집합과 여집합 연산을 자연스럽게 확장할 수 있다. 특히, `.*a.*&.*b.*`와 같은 교집합 연산에서 미분을 통해 `.*b.*`로 단순화하여 복잡한 패턴을 효율적으로 처리한다. 이러한 접근 방식은 정규 표현식 엔진의 구현 복잡도(Implementation Challenges)를 줄이고, 성능을 향상시키는 데 기여한다.
Minterm 압축(Minterm Compression)을 통한 성능 최적화
RE#는 Minterm 압축(Minterm Compression) 기술을 사용하여 문자 집합을 효율적으로 관리한다. 이 기술은 유니코드 문자 클래스를 여러 개의 등가 클래스로 분할하여, 각 클래스에 고유한 ID를 할당한다. 예를 들어, `[a-zA-Z]`와 같은 패턴은 문자와 문자가 아닌 문자로 구분하여 처리한다. 이로 인해, 엔진은 각 문자를 개별적으로 처리하는 대신, minterm ID를 기반으로 연산을 수행하여 메모리 사용량(Memory Usage)을 줄이고, 성능을 향상시킨다.
좌측 최장 일치(Leftmost-Longest Match) 의미론의 중요성
RE#는 좌측 최장 일치(Leftmost-Longest Match) 의미론을 채택하여 정규 표현식의 일관성을 보장한다. 이는 여러 가능한 일치 항목 중에서 가장 왼쪽에서 시작하고 가장 긴 문자열을 선택하는 방식이다. 이러한 접근 방식은 정규 표현식의 수학적 정확성(Mathematical Correctness)을 유지하고, 개발자가 예상치 못한 결과를 방지하도록 돕는다. 또한, 교환 법칙과 같은 기본적인 연산 규칙이 적용되도록 하여, 정규 표현식의 유지 보수성을 높인다.
RE#의 아키텍처: Lazy DFA와 파생 기반 접근 방식
RE#는 Lazy DFA(Deterministic Finite Automata) 방식을 기반으로 하며, NFA(Nondeterministic Finite Automata)를 거치지 않고 직접 DFA를 구성한다. 이 방식은 정규 표현식의 Brzozowski 미분(Derivatives)을 활용하여 DFA를 생성하며, 필요한 상태만 동적으로 생성하여 메모리 사용량을 최적화한다. 이러한 아키텍처는 복잡한 정규 표현식에서도 O(n) 시간 복잡도를 유지하며, 성능과 효율성을 동시에 확보한다.
