레이블된 매치 — 왜 모든 정규식 엔진에 없는가?

본문

정규식 엔진 RE#의 개발자 iev가 '레이블된 매치(labeled matches)'라는 기법을 소개합니다. 여러 정규식 패턴에 각각 레이블을 붙여 하나의 상태 기계로 합친 뒤, 텍스트를 한 번 순회하면서 매치된 패턴의 카테고리를 함께 반환하는 방식입니다. 저자는 이를 일종의 개체명 인식(NER)으로 볼 수 있다며, 결정론적 정규식이 신경망 기반 도구를 대체할 수 있는 영역을 강조합니다.

신경망 없이 하는 분류, 그리고 벤치마크

저자는 spaCy의 en_core_web_sm 모델(NER 컴포넌트만 사용)과 resharp의 categorize_all(패턴 10개)을 비공식적으로 비교했습니다. spaCy 3.8은 1스레드 0.09 MB/s, 8스레드 0.43 MB/s를 기록한 반면 resharp는 0.36 GB/s와 1.92 GB/s를 기록해 약 4,500배 빨랐습니다. 저자는 apples-to-oranges 비교임을 인정하면서도 yyyy-MM-dd 같은 날짜 형식은 정규 언어이므로 정규식이 '근사'가 아니라 윤년을 포함해 100% 정확하게 판별할 수 있다고 주장합니다. '이게 날짜인지 55.1% 확신해야 하는가'라며, 확률적 추론이 필요 없는 문제에는 주사위를 굴릴 이유가 없다는 것입니다.

패턴과 확장 연산자

예시에는 DATE, MONEY, PERCENT, EMAIL, URL, NUM, NAME, VERB, ADJ, ADV 등 10개의 레이블이 사용됩니다. NAME 패턴 [A-Z][a-z]+\b&~(On|In|At|To|For|Of|The|An|And|Via|Was|Is)에서 보듯, RE#는 교집합(&)과 여집합(~) 연산을 지원해 문장 첫머리의 'On', 'In' 같은 단어가 이름으로 오탐되는 것을 제외합니다.

if-then-else와 달력 정규식

교집합·여집합이 있으면 정규 언어를 벗어나지 않고도 if-then-else를 표현할 수 있습니다. 글에서는 (cond&a)|(~cond&b) 형태의 조합자를 JavaScript 문자열로 만들어 날짜 검증을 구성합니다. 2월은 29일까지, 그 외는 31일까지 허용하는 패턴이 26개 DFA 상태로 컴파일되고, 윤년 규칙까지 전부 나열한 24,504자짜리 패턴도 32개 DFA 상태에 불과합니다. 내부 simplify를 거치면 599자로 줄어들며, 부산물로 윤년 규칙 자체가 정규식 안에 '발견'됩니다. 여집합과 교집합 없이 합집합·연결만으로 같은 걸 표현하면 크기가 이중 지수적으로 폭증한다고 덧붙입니다. 또한 상태 기계는 실제 방문한 상태만 지연 컴파일하므로, 이론상 거대한 그래프도 문제가 되지 않는다고 설명합니다.

동작 원리와 사용법

구현은 단순합니다. 여러 패턴의 합집합 상태 기계에서 각 수용 상태에 레이블을 붙여 두고, 매치 시 상태에서 레이블을 조회하는 배열 lookups 하나만 추가됩니다. 대수적으로 레이블은 '미화된 빈 문자열'로, 미분 과정을 거쳐 수용 상태의 메타데이터로 남습니다. SIMD 가속과 단순화 등 RE#의 기존 최적화가 그대로 적용됩니다. Rust에서는 regex_set 피처의 RegexSet으로 사용하며, categorize_all이 각 매치의 태그와 범위를 반환합니다. 동일 범위에 여러 패턴이 매치되면 현재는 낮은 인덱스 하나만 보고합니다.

겹침 검사와 이론적 기반

enum으로 매핑하려면 레이블이 서로소(disjoint)여야 하는데, 저자는 A&B가 공집합인지 검사하는 정규식 겹침 검사기로 이를 증명할 수 있다고 설명합니다. A ⊆ B 포함 관계(subsumes)도 검사 가능하며, 예시로 모든 VERB([a-z]+ing)가 WORD([a-z]+)에 포함됨을 보여줍니다. 관련 내용은 CAV 2025 논문 'Regex Decision Procedures in Extended RE#'로 정리되어 있습니다.

Lobsters 반응

• @sunshine — RE#를 rebar에 추가해 볼 생각이 있나요? JavelinPattern과의 성능 비교가 궁금합니다.
• @viega — 한동안 업데이트가 없었고, 많은 부분에서 apples-to-apples가 아니기 때문일 수도 있지만 작업을 하긴 했습니다. 포크된 리포지토리는 여기입니다: https://github.com/ieviev/rebar 빠릅니다.
• @iev — JavelinPattern은 몰랐네요! 매우 흥미롭습니다, 감사합니다. 여기에 벤치마크된 이전 버전이 있는데, 곧 다시 벤치마크해 보겠습니다. 경쟁력이 높을 겁니다. 이전 버전에는 이차 복잡도를 만드는 최적화 버그가 몇 개 있었습니다.

원문: iev.ee / 번역·요약: Trawling