[알고리즘] 카프-라빈(Karp-Rabin) 알고리즘 - 코딩밥상

카프-라빈(Karp-Rabin) 알고리즘이란?

카프-라빈 알고리즘은 문자열 탐색을 위해 해시 함수를 이용합니다. 패턴 내의 문자들을 일일이 비교하는 대신 패턴의 해시값과 본문 내의 있는 하위 문자열의 해시값만 비교하는 방식입니다.

 

해시 함수를 다음과 같이 임의로 정의해보겠습니다.

 

최초의 해시함수

 

문득 여기서 궁금점은 각 패턴 문자열마다 해시값을 부여하면 문자열의 각 요소에 일일이 접근하여 곱셈연산을 하고 덧셈까지 하는 '비용'이 추가적으로 발생하기때문에 오히려 부르트 포스 알고리즘이 유리해 보입니다.

 

하지만 여기서 해시 함수의 비용을 획기적으로 줄이는 방법이 추가됩니다.

 

전 단계의 해시함수로 다음 단계의 해시값을 설정(새로운 해시 함수)

 

앞 단계에서 계산된 해시함수 값으로 다음 단계의 해시값을 간추리는 것입니다. 이렇게 되면 원래의 해시 함수로는 비교할 때마다 매번 패턴 길이 M 만큼 문자에 접근해야 했지만, 새 해시 함수를 이용하면 단 2개의 문자에만 접근하면 되는 것입니다.

즉 총 탐색 시간이 패턴 길이와 상관없이 본문 길이에만 영향을 받으므로 탐색 기능이 크게 향상됩니다.

 

다만 새 해시 함수는 i 가 0일 때, 즉 이전 해시값을 미리 구해놓지 못하면 사용할 수 없으므로 최초의 해시값을 구할 때는 기존의 해시 함수를 사용해야 합니다.

또한 최초의 해시 함수와 새로운 해시 함수 모두 문자열의 길이가 늘어나면 해시값도 같이 커진다는 문제가 있습니다. 이는 해시값을 일정 범위 안에 가두면 해결됩니다. 그 방법으로는 해시 함수의 결과값을 임의의 값으로 나눈 나머지를 해시값으로 사용하면 됩니다. 바로 모듈 연산을 하면 됩니다. 

 

마지막으로 간과해서는 안될 부분이 한가지 남았습니다. 카프-라빈 알고리즘이 해시 함수에 기반하고 있으므로 서로 다른 문자열에서 얻어낸 해시값이 동일한 경우(충돌)도 생길 수 있습니다. 다시 말해, 패턴의 해시값과 일치하는 문자열이라고 해서 패턴과 동일하다는 보장은 없다는 뜻입니다.

따라서 패턴과 일치하는 해시값을 가진 문자열들을 본문에서 찾아낸 다음, 실제로 각 문자가 패턴의 문자와 일치하는지 한 차례 더 확인합니다.

해시값으로 빠르게 문자열들을 걸러내고 후보값들만 다시 한번 확인하는 것입니다.

---

구현

int Hash(char* String, int Size){
    int HashValue = 0;
    
    for(int i=0; i<Size; i++){
        HashValue = String[i] + (HashValue*2);
    }
    
    return HashValue;
}

int ReHash(char* String, int Start, int Size, int HashPrev, int Ceofficient){
    if(Start == 0) return HashPrev;
    
    return String[Start + Size - 1] + ((HashPrev - Ceofficient * String[Start-1]) * 2);
}

int KarpRobin(char* Text, int TextSize, int Start, char* Pattern, int PatternSize){
    int Coefficient = pow(2, PatternSize - 1);
    int HashText = Hash(Text, PatternSize);     //초기 해시함수 사용
    int HashPattern = Hash(Pattern, PatternSize);   //초기 해시함수 사용
    int i,j = 0;
    
    for(i=Start; i<=TextSize - PatternSize; i++){
        HashText = ReHash(Text, i, PatternSize, HashText, Coefficient);     //새로운 해시함수 사용
        
        if(HashPattern == HashText){
            for(j=0; j<PatternSize; j++){
                if(Text[i+j] != Pattern[j]) break;  //해시 값이 같다면 실제로 같은 문자열인지 확인
            }
            
            if(j >= PatternSize) return i;
        }
    }
    
    return -1;
}