Skip to content

Aho Corasick algorithm

아호 코라식 알고리즘(Aho–Corasick string matching algorithm)은 Alfred V. Aho와 Margaret J. Corasick이 고안한 패턴 집합에 대한 매칭 알고리즘이다. 패턴 1개를 탐색하는 매칭 알고리즘은 선형 시간에 구현됨을 KMP 등 여러 알고리즘을 통하여 증명되었다. 하지만 패턴 집합에 대하여 이러한 알고리즘을 수행하게 되면 패턴 개수에 비례하여 그 속도가 느려지게 된다. 즉, O(m + zn)의 시간 복잡도를 가지게 된다.(m : 모든 패턴들의 길이 합, z : 패턴 수, n : text 크기) 하지만 Aho-Corasick 알고리즘을 이용하면 O(m + n + k)의 시간 복잡도로 패턴 집합에 대하여 패턴 길이와 텍스트의 선형 시간에 탐색을 처리할 수 있게 된다.(k : 텍스트 내에 패턴의 발생 수) 이러한 Aho-Corasick 알고리즘을 구현하기 위하여 Keyword Tree, Failure link, Output link 자료구조를 사용하여야 한다.

Favorite site

References

  1. Aho-corasick_algorithm.pdf ↩