[알고리즘] 아호 코라식 (Aho-Corasick)

여러개의 문자열 패턴을 단순하게 순회하면서 비교해서는 알고리즘 문제의 시간초과를 감당할 수 없어서 찾은 알고리즘 방식이

아호 코라식이다.

 

Aho-Corasick  알고리즘

- 여러개의 문자열 패턴을 한 번에 빠르게 텍스트에서 찾을 수 있게 해주는 알고리즘이다.

 

- 해당 알고리즘은 간단하게 얘기하면 KMP + Trie + BFS 가 결합된 구조로, 여러패턴을 동시에 검색할 수 있는 효율적인 알고리즘이다.

 

- 비교하고 싶은 문자열이 여러개일 때, 트라이 구조로 패턴 문자를 삽입하여 비교한다.

 

원리를 많이 설명하는데 해당 사진을 많이 사용해서 참고자료로 가져와봤다.

- 노드가 처음시작할 때 h냐 s냐에 따라 갈 수 있는 방향이 다음과 같이 정해진다.
- 만약에 he에서 글자가 끝나지만 찾는 문자가 hers라면 rs까지 도달해야 원하는 문자열이 반환된다.

- 해당 구조를 잘 이용하면 자동완성기능에도 유용하게 사용이 가능하다.

- 예를 들어, h만 있을 때 he, hers, his를 모두 반환하고 i로 넘어가면 his만 반환하도록 만들어서 만들어 질 수 있는 모든 경우의 수를 output으로 반환하는 방식으로도 사용 할 수도 있다.

 

 

아래 문제는 백준의 한 문제를 예시로 가져왔다.

class Node {
  constructor() {
    this.children = {}; // 자식 노드들 (Trie)
    this.fail = null;   // 실패 링크
    this.output = [];   // 이 노드에서 끝나는 패턴들
  }
}

class AhoCorasick {
  constructor() {
    this.root = new Node();
  }

  // 1. 패턴 삽입
  insert(pattern) {
    let node = this.root;
    for (const char of pattern) {
      if (!node.children[char]) {
        node.children[char] = new Node();
      }
      node = node.children[char];
    }
    node.output.push(pattern);
  }

  // 2. 실패 링크 구성
  buildFailureLinks() {
    const queue = [];
    for (const char in this.root.children) {
      const child = this.root.children[char];
      child.fail = this.root;
      queue.push(child);
    }

    while (queue.length > 0) {
      const current = queue.shift();
      for (const char in current.children) {
        const child = current.children[char];
        let fail = current.fail;
        while (fail && !fail.children[char]) {
          fail = fail.fail;
        }
        child.fail = fail ? fail.children[char] : this.root;
        child.output = child.output.concat(child.fail.output);
        queue.push(child);
      }
    }
  }

  // 3. 문자열에 패턴이 포함되어 있는지 탐색
  containsAny(text) {
    let node = this.root;
    for (const char of text) {
      while (node && !node.children[char]) {
        node = node.fail;
      }
      node = node ? node.children[char] || this.root : this.root;
      if (node.output.length > 0) return true;
    }
    return false;
  }
}

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

const n = parseInt(input[0]);
const patterns = input.slice(1, 1 + n);
const q = parseInt(input[n + 1]);
const queries = input.slice(n + 2);

// AC 트리 구축
const ac = new AhoCorasick();
for (const pattern of patterns) {
  ac.insert(pattern);
}
ac.buildFailureLinks();

// 질의 처리
const result = queries.map(str => ac.containsAny(str) ? 'YES' : 'NO');
console.log(result.join('\n'));

 

1. AhoCorasick 클래스에 트라이 구조를 바탕으로 패턴을 삽입하고, 각 패턴의 마지막에 해당하는 값을 output으로 반환한다.

2. 실패 링크(fail)을 설정한다. BFS 로 Trie를 순회하면서 각 노드에 실패할 시 이동할 노드를 설정한다.

    - KMP 의 실패함수와 비슷한 역할이라고 생각된다.

3. 텍스트를 한글자씩 보면서 매칭이 되는 각각의 트라이로 이동해서 실패하면 fail로 점프하고, 성공하면 마지막에 output에 문자를 처리한다.

4. AhoCorasick을 처리할 수 있는 클래스를 만들었으면, 해당 클래스에 패턴을 삽입하여, 구조를 연결한다.

5. 특정 문자열을 AhoCorasick에 넣어서 해당 문자열에 맞는 패턴이 존재하는지 확인한다.

 

이 구조를 이요하면 모든 패턴을 한 번의 탐색으로 동시에 검색이 가능해서, 시간복잡도가 엄청나게 줄어든다.

최근에 코딩 테스트를 봤는데 미리 준비했다면 조금 더 좋은 결과를 볼 수 있었을 것 같다는 아쉬움이 있다.

 

참고자료 : 

https://m.blog.naver.com/kks227/220992598966

아호코라식(Aho-Corasick)