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

[1. 개요]

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

• 문자열 H 에서 여러 문자열(N) 의 출현위치를 모두 계산하는 문제
• 단순한 해결법은 KMP 알고리즘을 찾고자 하는 문자열 개수 만큼 반복하는 방법
• 그러나 이보다 더 빠르게 계산 할 수 있는 방법이 있다.
• 트라이에 포함된 문자열들이 접두사를 공유할 경우, 탐색 공간을 줄일 수 있다.
• 찾고자 하는 문자열들을 모두 트라이에 저장한 뒤,
• 이 트라이를 이용하여 모든 문자열을 한꺼번에 찾을 수 있다.

부분 매치 테이블

• KMP 알고리즘 시, 전처리 되는 데이터
• 문자열 H의 어떤 시작위치 에서 찾고자하는 문자열과 matched 만큼 일치했을 때
• 각 접두사마다 이 접두사의 접두사도 되고, 접미사도 되는 문자열의 최대 길이가 계산되어 있다.

실패 함수(Failure function)

• KMP 알고리즘으로 문자열 탐색 시, 불일치가 발생했을 때,
• 어느 곳으로 이동하여 탐색 할지는 부분 매치 테이블을 통해 알 수 있다.
• 즉, 대응에 실패했을 때, 어디로 가서 검색을 계속해야 할지 알려주는 함수.

---

[2. 실패 함수]

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

• failure(s) = s 의 접미사이면서 트라이에 포함된 가장 긴 문자열까지 연결 됨.

---

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

알고리즘 flow

• 찾고자 하는 문자열로 구성 된 트라이에서
• 각 노드에 실패 함수를 계산 (전처리 과정)
• 짚더미 문자열 (검색 대상이 되는 문자열)의 글자를 순회하면서 트라이의 상태를 서로 오가면
• 모든 바늘 문자열 (검색 할 문자열) 들에 대해 동시에 KMP 알고리즘을 수행하는 효과

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

---

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

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

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

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

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

• 문자열 A
• Ax 는 문자열 A 에 문자 x 를 덧붙임.
• 여기서 A 는 Ax 의 부모 노드가 된다.
• [2. 실패 함수] 에서 문자열 s 의 접미사를 대상으로 하므로,
• Ax 의 실패 연결이 루트가 아닌 이상, 실패 연결을 따라가 만나는 문자열의 마지막 문자는 항상 x 이다.
• 그래서 Ax 의 실패 연결이 Bx 와 연결되어 있다고 볼 수 있다. (마지막 문자만 같으면 된다.)
• 그런데 여기서 B 는 항상 A 의 접미사가 된다.

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

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

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

• 대응 되는 것이 없다면 결국 root 까지 가게 된다.

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

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

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

---

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

---

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

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

• 몇 글자나 대응되었는지를 나타내는 matched -> 현재 상태의 노드를 나타내는 포인터
• 부분 일치 테이블 -> 실패 연결을 참조

---

[6. 시간 복잡도]

짚더미 문자열의 길이 : N

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

바늘 문자열 길이의 합 : M

 

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

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