Aho-Corasick 알고리듬

원문 발행 2026. 09. 30. 17:02원문 언어 한국어GeekNews 원문 보기

요약

Aho-Corasick 알고리듬은 여러 패턴을 동시에 검색하는 오토마톤 구조를 설명합니다. 트라이에 접미사 링크와 출력 링크를 추가하여, 입력 시퀀스에서 여러 부분 문자열을 효율적으로 찾는 방법을 제시합니다. 이 과정을 통해 결정적 유한 오토마톤(DFA)을 구성할 수 있습니다.

핵심 포인트

Aho-Corasick은 다중 패턴 검색에 최적화된 오토마톤입니다.
접미사 링크는 전이 실패 시 가장 긴 접두사를 보존하여 매칭을 복구합니다.
출력 링크는 하나의 패턴 발견 시 그 접미사에 해당하는 다른 패턴도 함께 출력하게 합니다.

Aho-Corasick 은 여러 패턴을 저장한 트라이에 링크를 추가해, 입력 시퀀스에서 여러 부분 문자열을 동시에 찾는 오토마톤을 구성함
접미사 링크 는 전이 실패 시 현재 문자열의 접미사이면서 패턴의 접두사인 가장 긴 문자열을 보존해, 해당 상태에서 실패한 문자를 다시 처리하도록 함
출력 링크 는 한 패턴을 찾았을 때 그 접미사에 해당하는 다른 패턴도 함께 출력하게 함
접미사 링크와 출력 링크는 너비 우선 탐색 으로 계산하며, 먼저 처리한 짧은 문자열의 정보를 더 긴 문자열의 링크 구성에 활용함
링크를 추가한 트라이를 직접 실행할 수도 있지만, 추가 너비 우선 탐색으로 전이와 출력을 미리 확정한 결정적 유한 오토마톤(DFA) 을 구성할 수도 있음
트라이로 패턴 집합 저장하기
트라이(trie) 는 문자열 집합을 저장하는 n진 트리로, 각 간선에는 문자가 붙고 각 노드는 루트에서 해당 노드까지 간선 문자를 이어 붙인 문자열을 나타냄
공통 접두사를 가진 문자열은 같은 경로를 공유해 중복을 줄임
suit

, suited

, suitable

을 저장하면 세 항목이 suit

경로를 공유함
완전한 패턴에 해당하는 노드는 별도로 표시함
접미사 링크로 전이 실패에서 복구하기
접미사 링크(suffix link) 는 현재 노드가 나타내는 문자열의 접미사 중, 트라이에 있는 패턴의 접두사와 일치하는 가장 긴 문자열을 보존함
현재 상태에서 입력 문자를 처리할 간선이 없으면 이 링크를 따라 이동하고, 실패한 문자부터 다시 매칭을 진행함
패턴이 item

, suits

이고 입력이 suitems

이면, suit

까지 읽은 상태에서 다음 문자 e

를 처리할 간선이 없음
suit

상태의 접미사 링크는 it

상태 를 가리킴
이 상태에서 e

부터 계속 읽으면 su[item]s

처럼 item

을 찾을 수 있음
루트에서도 전이할 수 없는 문자 는 어떤 패턴의 시작도 될 수 없으므로, 루트에 머문 채 입력 위치만 다음 문자로 이동함
너비 우선 탐색으로 접미사 링크 구성하기
링크 계산은 너비 우선 탐색(BFS) 순서로 진행함
루트와 루트의 바로 아래 자식들은 접미사 링크가 루트를 가리킴
나머지 노드는 부모의 접미사 링크가 가리키는 상태에서 시작해, 현재 노드로 들어오는 문자와 같은 이름의 간선을 찾음
해당 간선이 있으면 그 목적지를 접미사 링크로 사용하고, 없으면 접미사 링크를 계속 따라감
루트까지 왔을 때도 해당 간선이 없으면 루트를 사용하며, 루트의 자기 링크를 무한히 따라가지 않도록 멈춤
cadence

, facade

트라이 예시는 먼저 계산한 링크의 재사용 을 보여줌
노드 번호는 BFS 방문 순서이며, 큐가 [(c, 5), (d, 6)]

일 때 노드 5의 부모 접미사 링크는 루트임. 루트에 c

간선이 있으므로 그 목적지가 노드 5의 접미사 링크가 됨
다음 큐는 [(d, 6), (a, 7)]

이며, 노드 6은 부모 접미사 링크가 루트지만 루트에 d

간선이 없어 루트를 접미사 링크로 사용함
cad

를 읽은 노드 6에서 다음 문자가 e

가 아니면, 읽었던 cad

를 버리고 실패한 문자를 루트에서 다시 처리함
노드 7은 부모의 접미사 링크가 루트가 아닌 노드 2를 가리키며, 그곳의 a

간선을 따라 노드 4를 접미사 링크로 삼음. 이는 faca

의 접미사 ca

가 cadence

의 유효한 접두사라는 정보를 보존함
같은 패턴을 따라가다가도 자기 패턴의 접두사로 복귀 할 수 있음
완성된 예시에서 노드 12는 노드 2를 가리켜, cadence

를 매칭하던 경로 안에서도 다시 cadence

를 찾는 데 필요한 접두사 문맥을 보존함
출력 링크로 겹치는 패턴 함께 찾기
패턴을 트라이에 삽입할 때 마지막 노드는 출력 노드 로 표시하며, 보통 해당 패턴을 저장함
그 상태에 진입하면 연결된 패턴을 출력함
현재 패턴의 접미사도 등록된 패턴이라면, 그 패턴 역시 같은 시점에 출력해야 함
출력 링크(output link) 는 함께 출력해야 할 노드를 연결하며, 접미사 링크처럼 더 짧은 문자열을 나타내는 노드를 가리킴
spin

, pin

, in

을 저장한 트라이에서 spin

상태인 노드 9에 도달하면, 노드 8의 pin

과 노드 6의 in

도 출력함
직접 매처를 실행할 때는 출력 링크를 연결 리스트처럼 순회하며 패턴을 차례로 출력할 수 있음
출력 링크는 각 노드의 접미사 링크를 계산한 직후 결정할 수 있음
접미사 링크의 목적지가 출력 노드이면 그 노드를 출력 링크로 사용함
그렇지 않으면 접미사 링크가 가리키는 노드의 출력 링크를 이어받음
더 짧은 문자열은 BFS에서 먼저 처리되므로 필요한 정보가 이미 계산되어 있음
링크가 있는 트라이에서 DFA로 변환하기
접미사 링크와 출력 링크의 계산은 핵심 단계지만, 오토마톤 구성의 중간 단계 임
링크를 추가한 트라이를 직접 실행할 수 있으나, 다음 상태를 찾으려고 접미사 링크를 반복해서 따라갈 수 있어 전이 한 번의 작업량이 상수는 아님
링크 구성이 끝나면 전이와 출력을 정적으로 확정해 DFA 로 만들 수 있으며, 이를 위해 마지막 BFS를 수행함
루트의 전이 부터 모든 입력 기호에 대해 계산함
해당 기호의 간선이 있으면 그 목적지로 이동함
간선이 없으면 루트로 자기 전이해 해당 기호를 건너뜀
이 과정에서 루트의 간선으로 도달하는 상태들을 탐색 큐에 넣음
나머지 노드도 BFS 순서로 각 입력 기호의 다음 상태를 확정 함
해당 기호의 직접 간선이 있으면 그 목적지를 사용함
없으면 현재 노드의 접미사 링크가 가리키는 상태에서 같은 기호로 전이할 때의 목적지를 사용함
이는 현재 경로에서 더 진행할 수 없을 때, 다른 패턴의 접두사이기도 한 가장 긴 접미사를 보존하는 동작을 전이에 반영함
많은 전이가 빈 문자열 ε

를 보존하는 루트로 향하므로, 미리 구성하는 Aho-Corasick 오토마톤에는 희소 행렬 저장 방식 이 권장됨
he

, she

, her

예시에서는 접미사 링크와 출력 링크가 있는 트라이의 전이를 확정하고 출력을 집합으로 합쳐 DFA를 구성함
데모와 추가 자료
댓글과 토론

AI 자동 생성 콘텐츠

원문 바로가기