정규 표현식(Regex) 모든 매치, 이제 선형 시간 안에!

기존 정규 표현식(Regex) 엔진은 단일 매치(Single Match) 탐색에는 선형 시간을 보장하지만, 모든 매치(All Matches)를 찾을 때는 O(n²)의 시간 복잡도를 갖는 문제가 있었다. 특히, RE2, Go, Rust의 정규 표현식 엔진도 예외는 아니었다. 이는 '.*a|b' 패턴과 'n'개의 'b'로 구성된 입력에서 각 위치마다 매칭을 시도하며 발생하는 시간 낭비(Time Waste) 때문이다. 이러한 문제로 인해 AI 코딩 에이전트(AI Coding Agents)와 같은 도구에서 모든 매치를 필요로 할 때 성능 저하가 발생했다.

RE# 엔진은 이러한 문제를 해결하기 위해 두 번의 입력 패스(Two Passes)를 활용하는 새로운 알고리즘을 제시했다. 이 알고리즘은 입력 문자열을 두 번 순회하며, 각 매치의 시작과 끝 지점을 표시한다. 이러한 방식은 패턴과 입력에 관계없이 선형 시간 내에 모든 매치를 찾을 수 있게 해준다. 특히, 악성 패턴(Adversarial Pattern)에 대한 강력한 방어(Strong Defense)를 제공하며, 기존 엔진의 성능 저하 문제를 해결했다.

RE# 엔진은 BurntSushi의 rebar 벤치마크를 통해 성능을 검증했다. 벤치마크 결과, RE#은 기존 Rust regex 엔진과 비교하여 리터럴 매칭(Literal Matching) 및 대체(Alternation) 패턴에서 유사하거나 더 나은 성능을 보였다. 또한, CPU 벡터 명령어(CPU Vector Intrinsics)를 활용한 Skip Acceleration 기술을 통해 성능을 더욱 향상시켰다. 특히, 하드 모드(Hardened Mode)를 통해 악성 패턴에 대한 방어력을 높였으며, 일반적인 패턴에서는 성능 저하를 최소화하기 위해 최적화(Optimization)를 적용했다.

RE# 엔진은 악성 패턴(Adversarial Pattern)에 대한 방어를 위해 하드 모드(Hardened Mode)를 제공한다. 하드 모드는 O(n * S)의 시간 복잡도를 가지며, 입력의 길이가 길어질수록 성능 향상을 체감할 수 있다. 하지만, 일반적인 패턴에서는 3~8배의 성능 저하가 발생할 수 있다. 따라서, RE#은 하드 모드를 선택적으로 사용(Selective Use)하도록 권장하며, 신뢰할 수 없는 입력을 처리해야 하는 경우에 하드 모드를 활성화하여 보안(Security)을 강화할 수 있다. 또한, lookarounds와 lazy quantifiers는 현재 지원하지 않는다.

RE# 엔진은 현재 스트리밍(Streaming)을 직접적으로 지원하지 않지만, 아키텍처적으로는 스트리밍을 위한 준비가 되어 있다. 특히, leftmost-longest semantics를 유지하면서 스트리밍을 지원하기 위해서는 입력의 경계를 명확히 정의해야 한다. RE#은 캡처 그룹(Capture Groups)과 lazy quantifiers를 지원하지 않는다는 제한 사항이 있다. 하지만, boolean 연산자(Boolean Operators), lookarounds, true-linear all-matches, POSIX semantics를 제공하며, 향후 캡처 그룹 지원을 위한 연구가 진행될 예정이다.