다중 문자열 검색, 아호-코라식 알고리즘

[1. 개요]

트라이를 활용하여 해결 할 수 있는 문제 중 하나로, 다중 문자열 검색 문제가 있다.

먼저 배경지식, 부분 매치 테이블 이란?

실패 함수(Failure function)

[2. 실패 함수]

다중 문자열 검색 문제에서 실패 함수의 정의

failure(s) = s 의 접미사이면서 트라이에 포함된 가장 긴 문자열까지 연결 됨.
접미사 인 이유는?
# 트라이의 노드는 문자열의 접두사를 표현한다.
# 즉, 접두사이자 접미사가 되는 문자열을 의미함. (KMP 알고리즘에서 부분 매치 테이블)
문자열 s 가 문자열 H 의 begin 위치에서 matched 만큼 일치하고, matched+1 에서 불일치가 발생한 경우.
다음 탐색 위치를 찾고자 함. (KMP 알고리즘 처럼..)

[3. 야호-코라식 문자열 검색 알고리즘]

알고리즘 Flow

실패 함수 계산 과 실제 문자열 탐색 과정 이렇게 두가지 스텝으로 구현한다.

[4. 아호-코라식 알고리즘, 실패 함수 계산]

먼저 트라이의 각 노드는 아래와 같은 추가 정보를 갖는다.

실패 연결
# 이 노드에서 실패 함수 값
# 이 노드에서 다음 글자 대응 실패 시, 다음으로 가서 시도 해야 할 노드의 포인터
출력 문자열 목록
# 각 노드에 도달했을 때, 어떤 바늘 문자열이 발견되는지 저장
# 한 문자열이 다른 문자열의 부분 문자열 인 경우 등에 대처 할 수 있다.
# 접두사를 공유할 수 있기 때문,

실패 연결을 계산하는 중요한 단서

부모 노드의 실패 연결을 이용해 자식 노드의 실패 연결을 알 수 있다는 것이다.

위와 같은 이유로 부모 노드인 A 의 실패 연결 B 에 x 를 붙인 자식 노드가 있는지 확인하면 된다.

이 규칙으로 실패 연결을 찾을 수 없는 경우 (부모 노드의 실패 연결이 x 로 끝나지 않는 경우)

부모의 실패 연결에 해당하는 노드의 실패 연결을 따라가보는 방식으로 찾는다.

실패 연결을 따라 갈 때는, root 가 아니라는 조건이 필요하다.
# root 의 실패 연결을 root, 즉, 자기자신 이므로 무한루프(Cycle ?) 가 발생하게 된다.
대응 되는 것이 없다면 결국 root 까지 가게 된다.

실패 연결을 찾는 방법의 특성 상, BFS 를 이용하여 구현이 된다.

어떤 노드에서 실패 연결을 계산하기 위해서는, 조상 노드들의 실패 연결이 모두 계산되어 있어야 한다.

BFS 는 root 에서 퍼져 나가는 형태로 탐색이 되기 때문에, 이러한 조건을 충족 할 수 있다.

[4. 아호-코라식 알고리즘, 실패 함수 구현]

[5. 아호-코라식 알고리즘, 탐색 함수]

실패 함수를 계산하고 나면, 실제 탐색 과정은 KMP 알고리즘과 유사하다.

[6. 시간 복잡도]

짚더미 문자열의 길이 : N

바늘 문자열의 출현 횟수 : P

바늘 문자열 길이의 합 : M

실패 함수를 계산하는 알고리즘의 시간복잡도: O(M)

전체 시간 복잡도: O(N + M + P)

test_kernelv2