[18-알고리즘] 문자열 탐색(String Match) 라빈 카프 알고리즘(Rabin-Karp algorigm)

앞의 포스팅에서 가장 무식한 방법인 Naive string match를 살펴 보았다. 패턴이 문자열애서 어디있는지 찾기 위해서 앞에서 부터 차례대로 찾는 방법이었습니다. 이렇게 무식한 방법보다 비용이 적게 들면서 빠르게 찾을 수 있는 방법인 라빈 카프 알고리즘을 살펴 보겠습니다. 

텍스트 2359023141526739921이 있다고 합시다.(숫자로 구성되어있지만, 이는 문자열로 봅니다.) 여기서 패턴 문자열 31415를 찾으려고합니다.

텍스트 2359023141526739921에 패턴 문자열 31415가 있는지 확인하려고 합니다.

패턴 문자수는 '3', '1', '4', '1', '5' 즉 5개이다. 텍스트를 5개씩 앞에서 숫자로 변형시킬 것입니다. 라빈 카프 알고리즘의 핵심은 문자를 숫자 비교 문제로 바꾸는데 있습니다.

1번 인덱스 부터 31415랑 같은 숫자가 있는지 숫자 비교연산을 합니다.

문자열을 숫자 바꾸는 방법은 Horner's rule방법이 있습니다.  

[Horner's rule]

p = P[m] + 10 (P[m-1]) + 10(P[m-2] + ... + 10(P[2] + 10P[1])...)

Horner's rule에 맞추어서 위의 예제 Pattern P[1...m] = 314225을 변형해보자. 

p = 5+10*(2+10*(4+10*(1+10*3))) = 31,425

Honer's rule을 좀 더 빠르게 적용할 수 있다.

다음과 같은 수식을 이용하여 을 에서 좀 더 간단히 구할 수 있다, 

수식만 봐서 바로 이해되지 않으니 예를 들어보자. 7번 인덱스 31415의 비교를 끝내고 8번 인덱스인 14152와 비교한다고 하자. 

= 31415이고 T[s+5+1]=2이다. 그러면  = 10(31415-10000*3) + 2 = 14152 이다.

여기서 더 간단하게할 수 있다. 바로 모듈러 연산을 사용하는 것이다. 

인덱스에 있는 숫자, 그리고 패턴에 있는 숫자에 모듈려(%) 13하는 것이다.

그러면 찾으려는 패턴의 숫자 31415는 7이 된다. 그러면 31415의 모듈러13의 연산값인 7과 같은 숫자를 텍스트에서 찾는 것이다. 같은 값은 인덱스 7과 같은 값이 된다. 그런데 문제가 있다. 찾으려는 숫자 패턴 31415가 아니지만 모듈려 13한 값이 같은 택스트 인덱스 13번의 값 7이 이 있다. 따라서 패턴의 모듈려와 값이 같은 애들 중에서 이 값이 실제 맞는지 확인하는 과정이 추가적으로 필요하다. 

Θ(n-m+1)만큼 패턴과 택스트가 일치하는데 확인하는데 시간이 걸린다. 

Θ(m)만큼 s가 실제 패턴의 값과 일치하는지 확인하는데 시간이 걸린다. 

모듈러를 사용한 라빈 카프 알고리즘의 시간 복잡도는 최악의 경우 Θ((n-m+1)m)으로 표현 할 수 있다.