2020. 6. 4. 19:16ㆍ자료구조\알고리즘
아호 코라식 알고리즘이란
아호 코라식 알고리즘은 문자열 S와 여러 개의 문자열 T가 주어졌을 때, T에 있는 문자열 중 하나와 S가 매칭이 되는지를 계산할 수 있는 알고리즘 입니다. 아호 코라식 알고리즘은 KMP에서 사용하는 Failure Function을 Trie에 확장시킨 알고리즘입니다. 아래의 예시를 통해 알아보겠습니다.
앞에서 말했듯이 아호 코라식 알고리즘은 트라이 구조를 이용해 동작합니다. 우선 기본 문자열들을 he, she, his, hers으로 설정하고 위의 그림과 같이 트라이를 만들어 줍니다. 그리고 S = "cdhisxy"일 때 어떤 문자열들이 들어있는지 확인해봅니다. 우선 앞에 존재하는 cd의 경우에는 일치하는 문자열이 없으니 스킵하겠습니다.
위의 세 그림을 확인해 보면 'his'라는 문자열을 따라 output에 도달합니다. 그러므로 "his"는 S에 속한다는 것을 알 수 있습니다. 이후 x와 y에 대한 이동경로는 없으니 생략하겠습니다.
일반적으로 트라이를 사용하면 S를 앞에서부터 한 글자씩 훑어가다가 결과가 나오고, 절대 뒤로 돌아가지 않는다는 원칙이 있습니다. 그런데 만약 S = "shis"라면 s,h를 지나고 i가 나왔을 때 어디로 가야 할까요? 일단 S에 "his"가 있는 것은 확실한데, i를 보고 시작지점으로 돌아가면 절대 찾을 수가 없습니다. "his"를 찾기 위해서는 아래의 그림과 같이 이동해야 탐색을 할 수 있습니다.
위의 그림과 같이 빨간 점선으로 이어진 노드로 이동한 후 다음 지점으로 이동할 수 있다면 이동합니다. 이처럼 아호 코라식 알고리즘은 트라이를 탐색하면서 갈 곳이 없어지면 단순히 시작지점이 아니라 다른 어떤 곳으로 보내는 다른 함수가 필요합니다. 이를 Fail함수라고 합니다. Fail 함수를 이루는 규칙은 자신보다 깊이가 작으면서 가장 가까이 위치한 노드를 가리킨다는 것입니다. Fail 함수는 BFS를 통해 깊이가 작은 노드부터 방문해가며 만들 수 있습니다.