Context Vault

Cursor Fast Regex Search - 에이전트 도구용 텍스트 인덱싱

3 min read

Fast Regex Search: 에이전트 도구용 텍스트 인덱싱

Cursor가 AI 에이전트를 위한 빠른 정규표현식 검색 구현 방법 공유.

역사적 배경

1973: grep 탄생 (기본 정규표현식 매칭)
  ↓
ctags (구문 인덱스)
  ↓
IDE/LSP (타입 정보 포함 구문 인덱스)
  ↓
Agentic Coding → "에이전트는 grep을 좋아한다"

시간은 평평한 원이다. 결국 다시 grep으로 돌아왔다.

문제: 일반 검색 엔진으로는 정규표현식 검색 불가

  • GitHub 초기 Code Search: 복잡한 토크나이저 + ElasticSearch
  • 결과가 좋지 않았음
  • 식별자 검색은 가능했지만 정규표현식 매칭은 안 됨

해결책: Trigram 분해

Trigram이란?

모든 중첩되는 3글자 세그먼트를 토큰으로 사용.

입력: "the cat"

Trigrams:
  "the", "he ", "e c", " ca", "cat"

왜 3글자?

크기키 개수포스팅 리스트 크기
Bigram (2)~64K너무 큼
Trigram (3)적절적절
Quadgram (4)수십억작음

Trigram이 균형 잡힌 선택.

인덱싱 과정

  1. 문서 인덱싱: 모든 중첩 3글자 시퀀스 추출 → 역인덱스에 저장
  2. 정규표현식 토크나이징: 정규표현식 파싱 → 휴리스틱으로 trigram 추출
  3. 검색: trigram으로 후보 문서 필터링 → 실제 매칭 수행

의미

  • AI 에이전트가 대규모 코드베이스에서 정규표현식 검색 가능
  • 기존 시맨틱 검색만으로는 부족한 경우 해결
  • “code-review-graph”와 비슷한 맥락: 최소한의 컨텍스트로 정확한 검색

관련 기술

  • Inverted Index: 검색 엔진의 기본 구조
  • Posting List: 각 토큰이 등장하는 문서 ID 목록
  • Russ Cox의 블로그: Google Code Search 종료 후 2012년 공개한 알고리즘 설명

그래프 뷰