Aho-Corasick·Suffix Array·Suffix Tree로 텍스트 검색 구조 선택하기

텍스트 검색은 질의 형태에 따라 인덱스가 달라진다

로그 스트림에서 여러 시그니처를 동시에 찾아야 하는 경우와, 큰 텍스트에서 임의의 부분 문자열을 조회해야 하는 경우는 같은 문자열 검색 문제처럼 보여도 요구하는 구조가 다르다. Aho-Corasick, Suffix Array, Suffix Tree는 각각 다중 패턴 탐지와 접미사 기반 질의에 맞춰 설계된 대표적인 선택지다.

Aho-Corasick는 패턴 집합으로 트라이를 만들고 실패 링크와 출력 링크를 더한 오토마톤이다. 전처리 시간은 O(Σ|P|)이며, 텍스트 검색은 O(n + z)로 수행한다. 여기서 n은 텍스트 길이, z는 매칭 수다.

Suffix Array는 텍스트의 모든 접미사를 사전순으로 정렬한 인덱스 배열이다. LCP(Longest Common Prefix) 배열을 함께 두고 RMQ를 이용하면 빠른 서브스트링 질의를 구성할 수 있다. 전처리는 O(n log n) 또는 O(n), 검색은 O(m log n + occ) 특성을 갖는다. m은 패턴 길이, occ는 발생 수다.

Suffix Tree는 모든 접미사를 압축 트라이로 보관한다. Ukkonen 등의 방식으로 O(n) 구축이 가능하고 패턴 검색은 O(m)이다. 다만 실제 운영에서는 상수 계수와 메모리 오버헤드가 선택의 제약이 된다.

다중 패턴과 임의 질의가 요구하는 구조

Aho-Corasick의 핵심은 실패 전이다. 현재 상태에서 문자가 맞지 않아도 실패 링크를 따라 적절한 상태로 복귀하므로, 텍스트를 되돌아가지 않고 문자당 상수 시간 전이를 이어갈 수 있다. 패턴 집합이 고정된 환경, 특히 스트리밍 입력에서 효율적이다.

Suffix Array는 SA, LCP, RMQ 또는 세그먼트 트리로 구성할 수 있다. 패턴이 위치할 접미사 범위를 이진 탐색으로 찾고, LCP를 통해 문자열 비교를 줄인다. 구현과 메모리 사용의 균형이 좋으며 다양한 질의에 활용하기 쉽다.

Suffix Tree는 압축 에지, 엔드포인터, Active Point 같은 구조를 사용한다. 패턴 문자를 따라 에지를 이동해 O(m) 탐색을 수행하고, 해당 하위 트리에서 발생 위치를 확인할 수 있다. 시간 복잡도는 매력적이지만 포인터 중심 구조의 운영 비용이 크다.

세 구조 모두 전처리와 검색을 분리하는 방식으로 운용한다. 인덱스나 오토마톤을 먼저 구축하고, 직렬화와 캐시 전략을 정한 뒤 온라인 스트리밍 또는 배치 질의를 처리한다. 메모리 한계가 뚜렷하면 샤딩이나 외부 메모리 인덱스도 검토 대상이다.

⤢✕

검색 성능뿐 아니라 운영 비용까지 비교하기

알고리즘	성능(검색)	확장성	일관성	안정성	운영 편의
Aho-Corasick	O(n+z) 다중 패턴 최적	패턴 수↑ 시 상태 수 증가, 샤딩 필요	결정적 결과, 재현 용이	실패 링크 정합성 유지 시 안정	라이브러리 풍부, 동적 업데이트 난이로 인덱스 재생성 빈도 높음
Suffix Array	O(m log n + occ)	대용량 n에 선형/준선형 구축, 외부메모리 구현 용이	불변 인덱스 기반 결정성	메모리 예측 가능, LCP로 비교 안정	구현 단순, 직렬화·메모리 매핑 용이
Suffix Tree	O(m)	메모리 급증 시 제약, 대용량에 튜닝 난이	트리 정합성 보장 시 결정성	포인터 구조로 파편화·GC 부담	구현 난이도 높음, 운영 복잡

z와 occ는 발견된 매칭 개수이고, m은 패턴 길이, n은 텍스트 길이다.

보안·검색·분석 파이프라인에 적용하는 방식

보안 로그나 DPI의 다중 시그니처 탐지에는 규칙 세트를 AC 오토마톤으로 전처리한 뒤 네트워크 또는 로그 스트림을 선형 스캔하는 구성이 맞는다. 패턴 버전 관리, 오토마톤 핫스왑, 포트·프로토콜 기준의 샤딩이 운영 포인트가 된다.

유전체 모티프와 바이오마커 검색에서는 참조 게놈에 SA/LCP를 만들고, 모티프를 이진 탐색한 뒤 발생 위치를 집계할 수 있다. 외부메모리 SA와 압축 인덱스인 FM-index도 대안으로 고려한다.

검색 엔진의 하이라이팅이나 LIKE 가속은 문서별 SA 캐시에서 쿼리 토큰의 범위를 찾고, 오프셋으로 스팬을 추출하는 흐름으로 구성할 수 있다. 문서 단위 인덱스 직렬화와 캐시 만료·LRU 정책이 함께 필요하다.

악성 코드 시퀀스 탐지와 포렌식에서는 바이너리 스트림에 AC와 SA를 혼합해 바이트 패턴을 매칭하고 컨텍스트를 검사한다. 이스케이프, 바이너리 널 처리, 블록 경계 매칭을 놓치지 않아야 한다.

AC 기반 스트리밍 매칭은 네이티브 구현과 워크로드에 따라 CPU 코어당 수백 MB/s~~수 GB/s를 달성할 수 있다. SA 질의는 문서 단위 O(m log n)로 지연을 예측할 수 있다. SA는 ST와 비교해 메모리 사용량이 2~~4배 이상 절감되는 경향이 있으며, 불변 인덱스는 캐시 히트율 상승에도 유리하다. 결정적 재현성을 확보하고 장애 시 인덱스 스냅샷을 롤백하기 쉬우며, 패턴 변경 주기를 분리하면 배포 안정성도 높일 수 있다.

선택 기준은 갱신 방식까지 포함한다

실시간 스트리밍에서 여러 패턴을 찾아야 한다면 Aho-Corasick가 적합하다. 임의 서브스트링 질의, 하이라이트, 오프라인 분석이 중심이면 LCP를 결합한 Suffix Array가 실용적이다. Suffix Tree는 이론적으로 최선의 검색 시간을 제공하지만, 메모리가 충분하고 전문 팀이 유지보수할 수 있는 조건에서 선택할 수 있다.

AC는 패턴 수가 늘수록 상태와 전이 테이블도 커진다. 압축 전이와 알파벳 축소, Bloom을 이용한 2단계 필터로 부담을 완화할 수 있다. SA는 O(n log n) 구축 방식이 단순한 대신 시간이 늘어나며, SA-IS 같은 O(n) 알고리즘은 복잡하지만 빌드 시간을 줄일 수 있다. ST는 탐색은 빠르지만 메모리 단편화와 GC 영향을 고려해야 하므로 FM-index, CSA 같은 파생 구조도 검토할 만하다.

패턴이나 말뭉치가 바뀔 때는 스냅샷 인덱스를 교체하는 Blue-Green 방식으로 배치 재구축을 할 수 있다. 로그 스트림은 AC 다중 오토마톤을 나누어 로딩하고, SA와 ST는 세그먼트 샤딩 뒤 주기적으로 머지하는 방식이 가능하다.

Aho-Corasick로 패턴 집합을 스캔하는 코드

전제조건: pip install pyahocorasick

import ahocorasick

patterns = ["attack", "error", "failed"]
A = ahocorasick.Automaton()
for idx, p in enumerate(patterns):
    A.add_word(p, (idx, p))
A.make_automaton()

text = "connection failed with error code; possible attack detected"
matches = []
for end_idx, (idx, p) in A.iter(text):
    matches.append((p, end_idx - len(p) + 1, end_idx))

print(matches)  # [(패턴, 시작, 끝)]

대소문자와 정규화는 검색 전에 처리하고, 상태 수를 모니터링하며 오토마톤 직렬화를 사용한다.

Suffix Array를 만들고 범위를 질의하는 코드

전제조건: 표준 라이브러리만 사용(대용량 비권장)

def build_sa(s):
    sa = sorted(range(len(s)), key=lambda i: s[i:])
    return sa

def binary_search_sa(s, sa, p):
    import bisect
    class S:
        def __getitem__(self, i): return s[sa[i]:sa[i]+len(p)]
        def __len__(self): return len(sa)
    left = bisect.bisect_left(S(), p)
    right = bisect.bisect_right(S(), p)
    return sa[left:right]

text = "banana$"
sa = build_sa(text)
print(binary_search_sa(text, sa, "ana"))  # 발생 위치 목록

실제 서비스에서는 O(n) SA-IS 구현 또는 검증된 네이티브 라이브러리를 사용하고, LCP/RMQ를 결합해 비교 수를 최소화한다.

인덱스를 서비스에 올리기 전 확인할 항목

요구 분석 단계에서는 다중 패턴인지, 임의 서브스트링인지, 스트리밍 입력인지부터 구분한다. 지연 한도, 처리량, 메모리 상한도 함께 설정한다.

후보 구조를 정한 뒤에는 샘플 데이터로 벤치마크하고, 메모리·빌드 시간·질의 패턴별 프로파일링을 수행한다. 전처리 파이프라인은 빌드, 검증, 스냅샷 흐름으로 만들고 검색 서비스에는 샤딩, 캐시, 백프레셔를 반영한다.

운영 중에는 빌드 시간, 상태 또는 노드 수, 검색 QPS/P99, 메모리를 관측한다. 타임아웃, 부분 재시도, 히프 상한, 스로틀링은 장애 대응 경로에 포함한다.