Acho-Corasick 알고리즘

Aho-Corasick 알고리즘이란?

Aho-Corasick 알고리즘은 문자열 검색 알고리즘으로, 여러개의 패턴을 동시에 검색하는데 사용됩니다.

알고리즘을 이용하면 O(m+n+k)의 시간 복잡도로 패턴 집합에 대하여 패턴 길이와 텍스트의 선형 시간에 탐색을 처리할 수 있습니다(m: 모든 패턴의 길이 합, n: 텍스트 크기, k: 텍스트 내에 패턴의 발생 수).

 

알고리즘의 구성

● 키워드 트리

패턴의 글자 하나하나를 간선으로 한다.

서로 패턴들의 접두사가 최대한 같을 때까지는 같은 정점으로 간선을 따라가고 글자가 달라지면 다른 간선으로 가도록 만든다.

 

● 실패 링크

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

 

● 출력 링크

각각의 패턴들이 끝이 나는 정점은 그 정점을 Output link로 가지게 된다. 그리고 다른 정점에서 Failure link를 따라 가서 패턴이 끝이 나게 되면 여러 단계의 Failure link를 무시하고 바로 그 정점으로 Output link를 연결해 주게 된다. 이를 하기 위하여 Failure link를 추가할 때, 같이 Failure link를 따라간 정점이 패턴의 끝이면 그 정점으로 Output link로 하고 그렇지 않으면 그 정점의 Output link를 가져옴으로 모든 패턴들의 길이의 합의 시간 복잡도 안에 처리가 가능하게 된다.

 

아호코라식 알고리즘

1. 키워드 트리 및 출력 링크 설정

글자 하나씩 간선으로 설정 서로 패턴들의 접두사가 최대한 같을 때까지는 같은 정점으로 간선을 따라가고 글자가 달라지면 다른 간선으로 가도록 트리를 만들고 패턴이 끝나는 정점을 Output 하도록 설정한다.

 

 

2. 실패링크 설정

정점이 더이상 연결이 되지 않고 Output이 되지 않을때 자신보다 깊이가 작은 노드 중 동일한 노드로 실패링크를 연결한다

 

 

 

[자료] 해당 사이트를 참고하였습니다

 

아호 코라식 알고리즘 - 위키백과, 우리 모두의 백과사전

 

[알고리즘] 다중 문자열 검색 아호 코라식(Aho-Corasick) 알고리즘 정리 (Java)