선행 지식

아호-코라식이란?

아호-코라식 알고리즘은 여러 개의 패턴 문자열을 동시에 찾을 수 있는 효율적인 문자열 매칭 알고리즘이다.

이 알고리즘은 1975년 알프레드 아호(Alfred V. Aho)와 마거릿 코라식(Margaret J. Corasick)이 벨 연구소에서 개발한 알고리즘이다. 당시 문서 내에서 특정 단어 목록을 검색하는 작업을 효율적으로 수행하기 위해 개발되었다.

아호-코라식 알고리즘의 핵심 특징은 다음과 같다:

아호-코라식 알고리즘은 특히 대용량 텍스트에서 수천 개의 패턴을 동시에 검색해야 하는 상황에서 매우 효율적인 성능을 보여준다.

알고리즘 작동

  1. 다중 매치 될 패턴을 trie에 넣는다

    Untitled.png

  2. 각 노드에 대해 fail함수를 작성한다

    Untitled.png

  3. kmp처럼 이 fail함수를 통해 매칭을 시작한다

구현

from collections import deque, defaultdict

class AhoCorasick:
    class Node:
        def __init__(self):
            self.children = dict()
            self.fail = None
            self.output = []

    def __init__(self):
        self.root = self.Node()

    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = self.Node()
            node = node.children[char]
        node.output.append(word)  # 패턴 끝에 도달하면 출력 리스트에 추가

    def build(self):
        queue = deque()

        # 1. 루트의 모든 자식은 실패 링크가 루트
        for char, child in self.root.children.items():
            child.fail = self.root
            queue.append(child)

        # 2. BFS로 실패 링크 연결
        while queue:
            current = queue.popleft()
            for char, child in current.children.items():
                # 부모 노드의 실패 링크를 따라가며 가능한 문자를 찾음
                fail_node = current.fail
                while fail_node and char not in fail_node.children:
                    fail_node = fail_node.fail
                child.fail = fail_node.children[char] if fail_node and char in fail_node.children else self.root

                # 실패 링크가 가리키는 노드의 출력 결과도 같이 물려줌
                child.output += child.fail.output

                queue.append(child)

    def search(self, text):
        node = self.root
        results = defaultdict(list)  # 패턴별로 등장 위치 저장

        for i, char in enumerate(text):
            # 실패 링크를 따라가며 문자 전이를 찾음
            while node and char not in node.children:
                node = node.fail
            node = node.children[char] if node and char in node.children else self.root

            for pattern in node.output:
                results[pattern].append(i - len(pattern) + 1)  # 패턴의 시작 위치 기록

        return dict(results)