Aho-Corasick은 문자열 패턴매칭이 필요한 다수의 응용에서 아주 광범위하게 쓰입니다. 스노트의 경우 아래와 같이 상당히 많은 변형 알고리즘이 존재합니다.

– ac Aho-Corasick Full (highmemory, best performance)
– ac-std Aho-Corasick Standard (moderate memory, high performance)
– ac-bnfa Aho-Corasick NFA (low memory, high performance)
– acs Aho-Corasick Sparse (small memory, moderate performance)
– ac-banded Aho-Corasick Banded (small memory,moderate performance)
– ac-sparsebands Aho-Corasick Sparse-Banded(small memory, high performance)

기본적으로는 Trie를 자료구조로 사용하고 여러 개의 키워드를 한 번의 스캔으로 exact match 하는 것이 가능합니다. 아래 Trie 이미지와 C#으로 구현한 코드를 코드 프로젝트에서 받으실 수 있습니다.

위 Trie는 검색하려는 키워드는 HE, HIS, SHE, HERS로 만든 Trie 입니다. 일반 Trie에서 변형된 부분은 Failure가 났을 때 다른 브랜치에서 최장 prefix로 점프하도록 연결 정보를 노드에 넣어놨다는 점이지요. 가령 SHIS를 이 Trie를 이용해서 검색한다면, 글자 하나씩 맞춰보면서 다음 노드로 전이하는 것입니다. 처음엔 루트 노드에 있다가 S를 보고 S 노드로 가고, H를 보고 H 노드로 가고, 이제 I로 가려니 I가 없는 겁니다. 그러면 이전 문자열에서 최장 prefix 일치가 되는 Failure 노드로 점프합니다. 여기서는 위쪽에 있는 H 노드로 점프하게 됩니다. 거기서부터 I를 보고 I로 가고, S로 가게 됩니다. 가는 도중에 노드에 Keyword 정보가 있으면 모조리 검색 결과 목록에 집어넣습니다. 가령 검색하려는 키워드가 HI도 있었다고 한다면 I 노드를 지나갈 때 HI 키워드가 노드 정보에 있음을 발견하고 결과 목록에 추가하는 식입니다.

그러면 최장 일치 prefix 정보를 어떻게 찾아서 각 노드별로 Failure 노드 링크를 구축하느냐가 궁금하겠죠. 간단하게는 BFS로 쓸어내리면서 Failure 노드를 찾으면 됩니다. 루트 노드에선 아무 것도 없으니 Failure Node 라고 해봐야 자기 자신 밖에 없겠지요. 첫번째 레벨 탐색된 노드들도 Failure Node라고 해봐야 루트 노드 밖에 안 되겠죠. 제대로 된 Failure 노드 찾기는 당연히 2레벨부터 되겠습니다. 찾는 방법은 부모의 Failure 노드의 전이 목록에서 뒤지는 것입니다. DFS로 쓸어내리면서 항상 상위 노드의 Failure 노드에 이어붙이는 식으로 하면 자연히 최장 일치를 찾을 수 있게 됩니다. 가령 위 예에서는 두번째 노드가 I, E, H가 있는데 H의 경우 상위 노드인 S의 Failure 노드는 루트 노드이고, 루트 노드의 전이에서 H를 찾을 수 있습니다. 그러면 위쪽에 있는 H 노드가 밑에 있는 H 노드의 Failure 노드가 됩니다. 마찬가지로 밑에 있는 H 옆의 E의 Failure 노드는 상위 노드인 H 노드의 Failure Node인 위쪽 H 노드의 전이 중 E 노드를 찾을 수 있으니 위쪽의 E 노드가 아래쪽 E 노드의 Failure 노드가 됩니다.