여러분이 카카오톡이나 게임 서버의 채팅 금칙어 필터링 시스템을 개발한다고 상상해 보십시오. 채팅방에 올라오는 긴 문장 속에, 데이터베이스에 등록된 10만 개의 욕설 중 단 하나라도 포함되어 있는지 실시간으로 검사해야 합니다. 앞서 배운 고속 문자열 탐색 알고리즘인 KMP를 사용한다 하더라도, 패턴이 10만 개라면 KMP 알고리즘을 10만 번 반복해서 돌려야 하므로 서버는 순식간에 터져버릴 것입니다. "찾아야 할 단어가 수만 개라도, 본문 텍스트를 딱 한 번만 쭉 훑으면서 모든 단어의 포함 여부를 동시에 알아낼 수는 없을까?" 1975년, 알프레드 아호와 마거릿 코라식이 이 미친 발상을 현실로 만들어 낸 궁극의 오토마타가 바로 '아호-코라식(Aho-Corasick)' 알고리즘입니다. 트라이(Trie)의 확장성과 KMP의 점프력을 결합하여 문자열 검색의 종결자로 불리는 이 알고리즘을 완벽 해부합니다.
1. 두 거장의 결합: Trie 자료구조와 KMP 알고리즘
아호-코라식 알고리즘은 단순히 새로운 공식을 외우는 것이 아닙니다. 이미 존재하는 두 가지 천재적인 알고리즘의 뼈대를 레고 블록처럼 결합한 오토마타(Automaton, 상태 전이 기계)입니다.
- 트라이(Trie): 찾아야 할 10만 개의 금칙어 패턴들을 메모리 낭비 없이 하나로 뭉쳐놓기 위해, 글자 단위로 쪼개어 거대한 접두사 트리(Trie)를 구축합니다.
- KMP (실패 함수): 트리를 타고 내려가며 문자를 대조하다가 일치하지 않는 글자가 나왔을 때, 처음(루트)으로 무식하게 돌아가지 않고 "지금까지 일치했던 접두사와 접미사 정보를 활용해 안전하게 건너뛸 수 있는 최적의 중간 위치"로 점프하는 실패 링크(Failure Link)를 트라이 위에 덧씌웁니다.
2. 아호-코라식의 심장: 실패 링크(Failure Link) 구축하기
10만 개의 단어를 모두 트라이에 집어넣었다면, 이제 트라이의 각 노드를 잇는 파란색 화살표, 즉 실패 링크(Failure Link)를 연결해야 합니다. 이 링크는 BFS(너비 우선 탐색)를 사용하여 트리의 위에서부터 아래로 한 층씩 내려가며 구축됩니다.
2-1. 실패 링크가 연결되는 논리
어떤 노드 U에서 글자 'c'를 만나 노드 V로 간다고 가정해 봅시다. 만약 실제 본문을 대조하다가 V에서 다음 글자가 틀렸다면 어디로 가야 할까요?
노드 V의 실패 링크는 "노드 U의 실패 링크를 타고 간 노드에서, 똑같이 글자 'c'를 간선으로 가지고 있는 노드"로 연결됩니다. 말이 복잡하지만 핵심은 "내가 지금까지 맞춰온 문자열의 끝부분(접미사)과, 트라이 어딘가에 있는 다른 단어의 시작 부분(접두사)이 가장 길게 일치하는 곳"으로 거미줄처럼 비상탈출구를 뚫어놓는 것입니다. 이렇게 모든 노드에 실패 링크를 연결해 두면, 본문을 대조하다가 막히더라도 루트로 돌아가지 않고 실패 링크만 타고 슉슉 넘어가며 탐색을 중단 없이 이어갈 수 있습니다.
3. 탐색 시뮬레이션과 출력 링크(Output Link)
실패 링크가 완벽히 구축된 아호-코라식 트라이에 본문 텍스트를 첫 글자부터 하나씩 던져줍니다.
- 현재 노드에서 다음 글자로 가는 간선이 있다면, 기분 좋게 그 간선을 타고 아래로 내려갑니다.
- 다음 글자로 가는 간선이 없다면? 당황하지 않고 미리 연결해 둔 실패 링크(Failure Link)를 타고 다른 노드로 점프합니다. 점프한 곳에서 다시 다음 글자가 있는지 물어봅니다.
- 어떤 노드에 도달했을 때, 그 노드가 '어떤 단어의 끝(End)'을 의미하는 마킹이 되어 있다면, 10만 개의 금칙어 중 하나를 찾아낸 것입니다!
3-1. 치명적인 함정: 부분 문자열의 포함
만약 금칙어 사전에 "HE"와 "SHE"가 모두 들어있다고 해봅시다. 본문에서 "SHE"를 찾아 트라이를 타고 끝에 도달했을 때, 알고리즘은 "SHE"를 찾았다고 알립니다. 하지만 그 안에 "HE"가 포함되어 있다는 사실도 알려주어야 완벽한 필터링이 됩니다.
이를 위해 아호-코라식은 출력 링크(Output Link)라는 또 다른 화살표를 준비합니다. 실패 링크를 타고 가는 경로 중간에 다른 단어의 완성본(End)이 있다면, 이를 출력 링크로 체인처럼 엮어두어 "SHE"를 찾음과 동시에 그 속에 숨은 "HE"까지 단번에 긁어모아 출력합니다.
이 마법 같은 구조 덕분에 본문의 길이가 $N$, 모든 패턴 길이의 합이 $M$, 발견된 단어의 개수가 $Z$일 때, $O(N + M + Z)$라는 시간 복잡도로 10만 개의 단어를 한 큐에 찾아내는 문자열 검색의 제왕으로 군림하고 있습니다.
1. 아호-코라식(Aho-Corasick)은 수만 개의 패턴 문자열을 긴 본문 텍스트 단 한 번의 스캔으로 동시에 몽땅 찾아내는 다중 문자열 검색 알고리즘입니다.
2. 패턴들을 압축한 트라이(Trie) 자료구조 위에, 매칭에 실패했을 때 돌아갈 최적의 위치를 알려주는 KMP 원리의 실패 링크(Failure Link)를 BFS로 구축하는 것이 핵심입니다.
3. 문자열이 포함 관계(예: SHE 안에 HE)에 있을 때 이를 놓치지 않기 위해 출력 링크(Output Link)를 활용하며, 백신 프로그램의 바이러스 시그니처 검사나 욕설 필터링 엔진에 필수적으로 응용됩니다.