Aho-Corasick 알고리즘

Aho-Corasick 알고리즘

다중 패턴 문자열 매칭을 위한 알고리즘으로 트라이(Trie)와 실패 링크(Failure Link)를 사용하여 O(n+m+z) 시간에 텍스트에서 여러 패턴을 동시에 검색 (m=모든 패턴 길이 합, z=매칭 수)

목적: 다중 패턴 동시 검색, 효율적 문자열 매칭, 네트워크 보안

특징: 트라이 기반, 실패 링크, KMP 일반화, 선형 시간

구성요소

• •트라이(Trie): 모든 패턴 저장
• •실패 링크(Failure Function): 불일치 시 이동할 노드, KMP의 실패 함수와 유사
• •출력 링크: 매칭된 패턴 목록

동작: ① 패턴들로 트라이 구축 → ② BFS로 실패 링크 계산 → ③ 텍스트 순회하며 트라이 탐색, 불일치 시 실패 링크 따라감 → ④ 매칭 발견 시 출력

실패 링크 계산: 현재 노드의 접미사 중 트라이에 존재하는 가장 긴 것을 가리킴

시간 복잡도: O(n + m + z), n=텍스트 길이, m=모든 패턴 길이 합, z=매칭 수

공간 복잡도: O(m × σ), σ=알파벳 크기

장점: 다중 패턴 효율적, 선형 시간, 한 번 순회로 모든 패턴 찾기

단점: 메모리 많음(트라이), 전처리 복잡, 구현 어려움

적용사례: 안티바이러스(바이러스 시그니처), IDS/IPS(침입 탐지), 텍스트 필터링, DNA 서열 분석, 키워드 검색

비교: Aho-Corasick(다중패턴/트라이/선형) vs Rabin-Karp(해시/충돌) vs KMP(단일패턴)

연관: 트라이, 실패 링크, KMP, 다중 패턴 매칭, IDS