[알고리즘] 라빈-카프(Rabin-Carp) 알고리즘

오늘의 포스팅은 문자열검색 알고리즘인 라빈-카프 알고리즘입니다.

 

장문의 문자열 A가 있을때 문자열A 안에 특정 문자열B가 있는지 알수 있는 방법은 뭐가 있을까? 고민했을때 제일 간단한 방법은

 

찾고자 하는 문자열B의 첫글자가 있는곳을 문자열A에서 순차적으로 탐색해서 발견했을때 본격적으로 비교를 시작하는것입니다.

 

그러나 이방법은 제일 간단하고 무식한(?) 방법이지만 무식한(?)만큼 탐색하는데 비용이 많이듭니다.

 

그래서 이렇게 무식한(?) 방법 보다는 비용이 덜 들면서 빠르게 찾을수 있는 알고리즘인 카프-라빈 알고리즘을 설명하려고 합니다. 

 

 

 

라빈-카프 알고리즘을 간단히 설명하자면 문자열을 수치로 변환시켜 탐색하는 알고리즘입니다.

 

알고리즘 공식은 다음과 같습니다.

 

장문의 문자열 A가 있을때 A[n]은 A문자열의 n번째 문자입니다.
 

그리고 m은 찾고자하는 문자열B의 길이입니다. 

 

마지막으로 H는 문자열 A 에서 문자열 B의 길이를 수치로 변환시킨 값입니다.

 

수치값을 뽑아내는 기본식은 다음과 같습니다. 

만약에 문자열A[0]번째부터 A[m]번째까지의 문자열을 수치값으로 변화시키것을 H0라고 표현하면 그 식은 다음과 같습니다.

 

그리고 그 다음 A[1]번째부터 A[m+1]번째 까지의 문자열은 H1이라 칭하고 식은 다음과 같습니다.  

그리고 이 식을 다르게 표현하면 다음과 같습니다.


그 후 A[0] * 2^3을 더하고 빼면 식은 다음과 같은 모양으로 변합니다. 

이렇게 되면 다음과 같은 결과가 나옵니다. 


이를 식으로 쓰면 다음과 같습니다!

 

이제 공식은 끝!!

i가 0일때는 다음 식을

i가 1이상일때는 다음식을 적용합니다!

그렇다면 이 공식을 어떻게 쓰냐!?

 

문자열B의 H값이 A[i]값과 같으면 문자열A[ i ]번째가 찾고자하는 문자열B의 시작점입니다!

예를 보겠습니다.

 

다음과 같은 문자열이 있다고 할때 CDEF 문자열을 찾는다고 가정해보겠습니다.

 

문자열A : 

 

찾는 문자열B: 

 

Step1. 찾고자 하는 문자열B의 수치값을 계산합니다!

   

 

수치값은 다음과 같이 1016입니다.

 

 

Step2. 문자열A의 시작위치부터 찾고자하는 문자열B의 길이만큼의 수치값을 계산합니다.

 

 

H0의 값(998)은 찾고자하는 값이였던 1016과 다르네요!

 

Step3. 전 위치에서 옆으로 한칸 이동해서 다시 수치값을 계산합니다!

H1의 값도(1025)은 찾고자하는 값이였던 1016과 다르네요!

 

그렇다면 한번더 Step3를 반복!

 

H2의 값도(1016)이 찾고자하는 값이였던 1016과 드디어 같네요!

 

그 결과 i값은 2 따라서 문자열A[ 2 ] 부터 찾고자하는 문자열과 같다는 것을 알수입니다!  

 

기본원리는 여기까지이고 실제로 사용하려면 찾고자하는 문자열이 길때 그 결과인 H값이 표현범위를 넘을수 있기 때문에 

커다란 상수로 나머지 연산계산을 한후 나머지값으로 비교를 하게 됩니다! 

Hi = 1016 / mod Q   ( Q는 적당한 상수 )

H0 = 998 / mod Q    

그 후 문자열이 달라도 같은 나머지값이 존재할수 있기 때문에 나머지값이 같은 녀석을 다시한번 비교함으로써 찾게 됩니다.

 

라빈-카프 알고리즘에 대한 설명은 여기까지 입니다!

 

누군가에게는 작은도움이 되었기를 바라면서 오늘의 포스팅 끝~​