아호-코라식 알고리즘은 대표적인 문자열 알고리즘 중 하나로써,
매우 빠른 일대 다 패턴 매칭 알고리즘입니다.
이와 관련해 설명하기 전에, 아호 코라식이 어떻게 쓰이는지, 왜 필요한지 간단한 예제를 통해 한번 알아보겠습니다.
주어진 단어가 다음과 같을 때, 트리는 아래처럼 구현됩니다.
Words = {"HE","SHE","HIS"}
우리는 KSHE라는 문자열에서, 다음의 트라이에 포함되는 문자가 무엇이 있는지를 알고 싶습니다.
먼저, 기존의 방식처럼, 그냥 트라이를 따라 이동하는 경우를 생각해봅시다.
자식을 따라 이동하다가, 더이상 이동이 불가능한 경우, 시작 위치로 이동한다고 해봅시다.
현재 노드 Root
1 ) K로는 시작 노드에서 이동할 수 없으니 패스합니다.
현재노드 : Root
2 ) 시작노드에서 S를 타고 이동할 수 있으므로, 자식 노드로 이동합니다.
현재 노드 : Root.Child[S] -> 편의상 S라 합시다.
3 ) S에서, H를 타고 이동할 수 있으므로, 자식 노드로 이동합니다.
현재 노드 : S.Child[H] -> H
3 ) H에서, E를 타고 이동할 수 있으므로, 자식 노드로 이동합니다.
현재 노드 : H.Child[H] -> E
이때, E의 Fin은 참이므로, 우리는 주어진 문자열 안에 SHE가 있음을 알 수 있습니다.
하지만, 상술한 방법으로는 몇가지 한계점이 존재합니다,
첫째, 완성한 단어가 다른 단어를 부분집합으로 포함하지만, 결과로는 그것을 알 수 없습니다.
Ex) SHE는 HE를 부분집합으로 포함하지만, SHE라는 문자열이 주어질 경우 우리는 HE를 얻을 수 없습니다.
둘째, 특정 단어가 입력 문자열에 있음에도 불구하고, 순서에 따라 이를 찾지 못할수도있습니다.
EX) 주어진 입력 문자열이 SHIS라고 한다면, 우리는 먼저 Root->S->H로 이동한 뒤, S->H에서 I를 자식으로 가지지 않으므로 Root로 이동합니다. 때문에, HIS을 얻을 수 없습니다.
그렇다면, 이 문제를 어떻게 해결할 수 있을까요?
주어진 문자열에 대해 시작을 달리하며 패턴 검색을 진행한다면, 우리는 상술한 문제들을 해결할 수는 있을겁니다. (아마도?)
하지만, 이는 굉장히 오랜 시간이 걸립니다.
주어진 단어의 i번째 요소부터의 길일를 $L_i$, 패턴 단어 중 가장 긴 길이를 $L_{m}$라고 하면,
간단하게만 계산해보아도, $O(min(L_i,L_m) * ... * min(1,L_m))$번의 연산을 필요로 합니다.
단어가 짧은 경우에는 큰 문제가 없겠지만, 단어가 길어지면 길어질 수록 필요한 시간은 기하급수적으로 늘어날겁니다.
이것이 바로 우리가 아호-코라식을 사용하는 이유입니다.
아호-코라식 알고리즘은, 다음과 같은 시간 복잡도를 가집니다.
K번째 단어의 길이를 $L_{k}$라고 하면,
Fail 구현에 총 $O(L_{1} + L_{2} + ... + L_{k})$ | Search에 O($L_{input}$)의 시간 복잡도가 필요합니다.
아호-코라식 알고리즘은 $O(L_{input} + L_{1} + L_{2} + ... + L_{k})$의 시간 복잡도를 가집니다.
그럼, 이제부터 아호-코라식 알고리즘이 어떤 원리로 동작하는지 알아보겠습니다.
트라이를 통한 아호-코라식의 구현을 위해, 트라이의 각각의 노드들은 다음의 요소들을 가집니다.
Fin - 현재 노드가 주어진 어떤 단어의 마지막인지 여부
Output - 해당 노드의 Fin이 참일 때, 해당 노드의 키워드로 끝나는,
해당 노드까지의 문자열에 포함되는 부분 단어들의 집합
ex) 주어진 패턴이 Sheep,heep,she,ep인 경우, output[Sheep] = {sheep,heep,ep}
Child - 각 노드의 자식 노드들(알파벳을 키로 함)
Fail - 현재의 문자(알파벳 등)을 가지고 현재 노드에서 다음 노드로 넘어가는 것이 불가능할때 이동할
가장 가까운, 현재의 문자를 자식 노드로 가지는 이전 노드
Fail이 어떻게 사용되는지, 아까의 SHIS 문자열을 통해 확인해보겠습니다.
S-H순으로 트라이를 따라 이동할 때,
S-H에는 I라는 자식 노드가 존재하지 않기 때문에, 우리는 SH의 부분 집합 중 가장 긴(깊이가 깊은) 노드로 이동합니다.
여기서는, H가 되겠죠. 그럼 우리는, H-I-S를 따라 이동하며 SHIS배열에 HIS가 존재함을 성공적으로 알아낼 수 있습니다.
그런데, 여기서 의문이 생길 수 있습니다.
첫번째 문제를 아호-코라식에서는 어떻게 해결할까?
이는, 아호-코라식 알고리즘에서 각 노드별 Fail을 구하는 방법과 일맥상통합니다.
Fail은 현재 노드의 "가장 깊은", 즉 가장 길이가 긴 부분집합을 의미하며, Fail의 추적을 위한 방법으로
우리는 쉽게 BFS를 떠올릴 수 있습니다.
BFS를 통한 트라이의 각노드의 Fail 추적은, 다음과 같은 절차를 거칩니다.
def constFail(self):
queue = deque()
self.fail = self
queue.append(self)Root는, 자기 자신을 Fail로 가집니다. ($Fail(Root) = Root$) 그리고, BFS의 진행을 위해 큐에 Root를 넣습니다.
def constFail(self):
queue = deque()
self.fail = self
queue.append(self)
while queue:
cur = queue.popleft()
for nextc in cur.child:
nextNode = cur.child[nextc]
if cur == self:
nextNode.fail = self
else:
f = cur.fail
while f is not self and nextc not in f.child:
f = f.fail
if nextc in f.child:
f = f.child[nextc]
nextNode.fail = f
if nextNode.fail.fin:
nextNode.out = nextNode.out.union(nextNode.fail.out)
nextNode.fin = True
queue.append(nextNode)현재 노드를 $cur$이라고 할때, 문자$x$를 키워드로 하는 모든 자식 노드 $C_x$에 대해,
만약 $cur$ is root라면, $C_x$는 root를 Fail로 가집니다. ($Fail(C_x) = root$)
그렇지 않다면,
모든 자식 노드들은 문자$x$를 키워드로 하는 자식 노드가 있거나, Root인 노드가 나오기 전까지 while문을 반복해 나온 결과물 F에 대해,
$F$의 자식 노드 $F.Child[x]$를 Fail로 가집니다. (
$Fail(C_x) = F.child[x]$)
만약 문자$x$를 키워드로 하는 자식 노드가 존재하지 않는다면, 자연스럽게 $C_x$의 fail은 root가 될 것입니다.
이는 위에서 설명한, Fail의 의미에 부합합니다.
이렇게 $Fail(C_x)$가 구해지고 나서, 만약 $Fail(C_x)$.fin이 참이라면, $C_x$는 기존의 output에 $Fail(C_x)$값의
output을 추가로 가지게 되고, $C_x.fin$값도 참이 됩니다.
그 후, 큐에 $C_x$를 추가합니다.
다음과 같은 과정을 거치며, 트라이를 구성하는 각각의 노드는 자신의 fail을 구하고, 부분집합을 output에 추가하고, fin값을 갱신할 수 있습니다.
def search(self,string):
res = set()
cur = self
for s in string:
#print(s, cur.child.keys())
while cur != self and s not in cur.child:
cur = cur.fail
if s in cur.child:
cur = cur.child[s]
if cur.fin:
res = res.union(cur.out)그렇게 Fail함수가 종료된 후에는, 원하는 문자열을 조회하는 일만이 남았습니다.
주어진 문자열을 가지고 한단계씩 진행해나가며, $s$을 키워드로 하는 자식노드가 존재하지 않는 경우,
$s$를 키워드로 하는 Fail을 찾거나 Root에 도달할 때 까지 $cur = Fail(cur)$을 반복합니다.
조회 도중 현재 노드 $cur$의 fin이 참인 경우, resultSet에 해당 노드의 output을 추가합니다.
즉, 결괏값에 현재 노드의 모든 부분집합 단어들을 추가합니다.
반복문이 종료되면, 우리는 주어진 문자열에 포함된 모든 단어들의 집합을 구할 수 있습니다.
전체 소스는 다음과 같습니다.
from collections import deque
class TrieNode():
def __init__(self):
self.fin = False
self.fail = None
self.out = set()
self.child = dict()
def addString(self,string):
cur = self
for s in string:
if s not in cur.child:
cur.child[s] = TrieNode()
cur = cur.child[s]
cur.fin = True
cur.out.add(string)
def search(self,string):
res = set()
cur = self
for s in string:
#print(s, cur.child.keys())
while cur != self and s not in cur.child:
cur = cur.fail
if s in cur.child:
cur = cur.child[s]
if cur.fin:
res = res.union(cur.out)
#print(res)
return res
def constFail(self):
queue = deque()
self.fail = self
queue.append(self)
while queue:
cur = queue.popleft()
for nextc in cur.child:
nextNode = cur.child[nextc]
if cur == self:
nextNode.fail = self
else:
f = cur.fail
while f is not self and nextc not in f.child:
f = f.fail
if nextc in f.child:
f = f.child[nextc]
nextNode.fail = f
if nextNode.fail.fin:
nextNode.out = nextNode.out.union(nextNode.fail.out)
nextNode.fin = True
queue.append(nextNode)
T = TrieNode()
for _ in range(int(input())):
T.addString(input().rstrip())
T.constFail()
for _ in range(int(input())):
print("YES" if T.search(input().rstrip()) else "NO")
여기까지 아호-코라식(Aho-Corasick)알고리즘에 대해서 알아보았습니다.
아직 실력이 부족해 잘못된 점이 있을 수 있으니, 지적해주시면 감사하겠습니다.