아호 코라식 알고리즘

아호 코라식 알고리즘(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 자료구조를 사용하여야 한다.

키워드 트리 편집

키워드 트리(Keyword Tree)는 패턴의 글자 하나를 하나의 간선으로 한다. 그리고 서로 패턴들의 접두사가 최대한 같을 때까지는 같은 정점으로 간선을 따라가고 글자가 달라지면 다른 간선으로 가도록 만들게 된다. 전 처리 과정에서 Keyword Tree를 만들면서 모든 패턴들의 길이의 합의 시간 복잡도 안에 만들 수 있게 된다.

실패 링크 편집

모든 패턴을 차례로 Keyword Tree에 넣은 이 후에는 이 Tree에 실패 링크(Failure link)를 추가해주게 된다. 루트에서 거리가 1인 정점들의 Failure link는 루트로 초기화한다. 그리고 거리가 2 이상인 정점들에 대해서 거리를 키워가면서 바로 앞 정점의 Failure link를 따라 가서 앞 정점과 해당 정점 사이의 간선에 해당하는 글자와 Failure link를 따라 간 정점의 글자가 같으면 그 정점으로 Failure link를 저장하게 되고 아니면 계속 Failure link를 따라가면서 처리하고 만약 루트가 나오면 해당 글자와 같은 거리가 1인 정점이 존재하면 거기로 Failure link를 저장하고 아니면 루트로 저장하게 된다. 위와 같은 방법으로 하게 되면 모든 패턴들의 길이의 합의 시간 복잡도 안에 모든 Failure link를 만들 수 있게 된다.

출력 링크 편집

여기에 패턴들 중에 다른 패턴의 substring이 존재하게 되면 패턴들을 탐색하지 못 할 때가 발생할 수 있다. 이를 막기 위하여 출력 링크(Output link)라는 자료 구조를 추가하게 된다. 각각의 패턴들이 끝이 나는 정점은 그 정점을 Output link로 가지게 된다. 그리고 다른 정점에서 Failure link를 따라 가서 패턴이 끝이 나게 되면 여러 단계의 Failure link를 무시하고 바로 그 정점으로 Output link를 연결해 주게 된다. 이를 하기 위하여 Failure link를 추가할 때, 같이 Failure link를 따라간 정점이 패턴의 끝이면 그 정점으로 Output link로 하고 그렇지 않으면 그 정점의 Output link를 가져옴으로 모든 패턴들의 길이의 합의 시간 복잡도 안에 처리가 가능하게 된다.

자료구조를 이용한 탐색 편집

텍스트의 글자와 Keyword Tree의 간선의 글자와 비교하면서 정점으로 내려가게 된다. 비교하면서 내려가면서 Output link가 존재하는지 확인을 계속 하고 Output link가 존재하면 패턴이 발생했음을 알려주게 된다. 또한 비교하다가 틀리게 되면 Failure link를 따라 가서 계속 글자를 비교해 주면서 탐색을 하게 된다. 이와 같이 탐색을 하게 됨으로 텍스트에 대하여 한번 확인하였으면 다시 확인하지 않게 되고 따라서 $O(m+n+k)$ 의 시간 복잡도로 처리가 가능하게 된다.

참조 편집

Alfred V. Aho, Margaret J. Corasick, "Efficient string matching: An aid to bibliographic search", Communications of the ACM, 18, 6, 333-340, 1975.
Thomas H. Cormen, Charles E. Leiserson, Ronald L.Rivest, Clifford Stein, "Introduction to Algorithms 3rd edtion", The MIT press, 772-812, 2009.