Rabin-Karp Algorithm라빈 카프 알고리즘은 문자열 매칭 알고리즘이다. Show 기본적으로 롤링 해시(Rolling Hash)를 사용한다.
그럼 이제 실제 알고리즘의 동작과정을 살펴보자. 문자열 Brute-force 방법과 동작 과정은 거의 유사하다. Pattern과 Text의 첫 3개 문자열을 비교한다. 이 때, 직접 하나씩 비교하는 것이 아닌 Text에서의 첫 3개 문자열인 당연히 다르므로 다음 index로 넘어간다. 이 때는 매칭에 성공하게 된다. 이런식으로 모든 문자열 조각과 패턴을 비교한다. 자 그러면 이런 의문이 들 수가 있다.
하지만, 앞서 말했듯 이 알고리즘에서는 롤링 해시를 사용한다. H[0]=A∗4+B∗2+C∗1H[0] = A*4 + B*2 + C*1 의 값을 알고 있다면, O(1)O(1)만에 다음 해시 값 H[1]=B∗4+C∗2+ D∗1H[1] = B*4 + C*2 + D*1 를 구할 수 있다. 다음 식으로 보면 이해가 좀 더 빠를 것이다. H[1]=(H[0]−A∗ 4)∗2+DH[1] = (H[0] - A*4) * 2 + D 이는 상수시간에 동작하는 연산이다. 즉 이 경우 시간 복잡도는 O(N) O(N)이 된다. (NN은 문자열의 길이) 이해가 안되는 부분은 코드를 보며 극복해보자. C++ 구현 코드
KMP(Knuth-Morris-Prett) Algorithm라빈 카프가 해시값을 통해 하나씩 건너가면서 보는 시간을 단축했다면, KMP는 하나씩 건너가지 않는다. KMP에서 도입한 개념은 실패 함수 (failure function)이다. 이 실패함수는, '문자 매칭에 실패했을 때, 얼만큼 건너뛰어야 하는가?'를 알기 위해 사용된다. 다른 말로는, '문자 매칭에 실패하기 직전 상황에서, 접두사 / 접미사가 일치한 최대 길이'라고 풀이된다.
심지어 다섯 번째, 여섯 번째 인덱스는 같다는 것이 보장되어 있기 때문에 일곱 번째 인덱스부터 비교하면 된다.
이게 바로 KMP의 아이디어다. 그리고 ii 인덱스에서 틀렸을 때, pi(i)pi(i) 부터 다시 보면 돼요! 라고 알려주는 것이 바로 실패 함수의 역할인 것이다.
알고리즘 동작 과정실패함수
정리하면 다음과 같다.
실패함수 구현 방법자 이제 남은 건 하나다. 실패함수 Naive하게 접근한다면, 접두사의 길이를 증가시키면서 접미사의 길이를 증가시키고 비교해야 하므로 O(M2)O(M^2) 임을 알 수 있다. 말도 안된다. 배보다 배꼽이 더 큰 상황이다. 하지만? 여기에서 위에 쓴 KMP의 구현을 가져다가 써볼 수 있다
굉장히 유사하다! 그럼 한번 pi 배열의 생성과정을 살펴보도록 하자.
쭉쭉쭉 다 다르므로
이제
그다음은
다시 다르므로
이렇게 실패함수가 구현된다. 전체 코드는 다음과 같을 것이다. C++ 구현 코드
Boyer-Moore-Horspool Algorithm
Bad Match Table우선 Bad Match Table을 만들어야 한다. 일단 이게 뭔지는 알고리즘 설명에서 보도록 하고 어떻게 만드는지부터 살펴보자. 기본적으로 Bad Match Table은 다음과 같은 식을 반복하여 만들어진다.
에 대해서 Bad Match Table은 다음과 같은 과정으로 생성된다.
코드는 다음과 같을 것이다.
알고리즘 동작 과정자 그러면 이제 어떻게 탐색을 할 것이냐.
여기에서 P의 가장 마지막 글자와 T의 다섯 번째 글자를 비교한다. 다르다! 그렇기 때문에 P를 이동시키는데, 이 때, T[4]의 Bad Match Table 값 만큼 점프를 한다. 여기에서는 1이므로 한 칸 이동한다.
H 끼리 같고, T도 같다. S는 Bad Match Table에서 정의되지 않았으므로 패턴의 길이인 5가 된다. 따라서 이번에는 다섯 칸을 점프한다.
O는 Bad Match Table에서 2로 정의되어 있으므로 두 칸 점프한다.
다시 T는 Bad Match Table에서 1로 정의되어 있으므로 한 칸 점프한다.
이런식으로 Boyer-Moore-Horspool 알고리즘은 점프를 한번에 어마어마하게 많이 뛴다.
구현은 다음과 같이 할 수 있을 것이다. C++ 구현 코드
사실 이 방법은 보이어-무어 알고리즘을 호스풀 교수가 간략하게 바꾼 것이다. 보이어-무어 알고리즘은 성능이 뛰어나기 때문에 GNU grep을 비롯한 여러 곳에 사용되며 문자열 검색 알고리즘 성능 비교의 표준으로 쓰이지만, 비교적 복잡하다는 단점이 있다. 그것을 가장 중요한 부분만 남긴 것이 바로 이 알고리즘인 것이다. |