라빈카프 문자열 매칭

라빈카프 문자열 매칭

  해시(Hash)를 활용하는 알고리즘이며 평균적으로 O(N+M)의 시간 복잡도를 갖는 알고리즘이다.

  아스키코드 기반의 해시함수를 이용하여 특정한 문자열에 대한 해시값을 구한다.

  연속적인 문자열이 이어지는 상황이므로 해시함수의 동작에 있어서 연산속도가 O(1)이다.

 

  라빈카프 문자열 매칭 알고리즘에서 해시함수는 각 문자의 아스키코드값에 2의 제곱수를 차례대로 곱하여

  더한값을 구한다. 일반적으로 서로 다른 문자열의 경우 일반적으로 해시값이 다르게 나온다.

 

  해시함수에 기반한다는 점에서 해시충돌에 대한 처리가 필요하다.

  

  때에 따라서는 KMP알고리즘보다 빠르게 동작하기도 하지만 특정한 상황에서는 KMP알고리즘보다

  매우 느리게 동작할 수 있다.

 

해시함수 눈사태효과

  문자열 abacdab가 있다고 했을 때 이것은 12,380이라는 해시값을 갖는데

  = 97 * 2^6 + 98 * 2^5 + 97 * 2^4 + 100 * 2^2 + 97 * 2^1 + 98 * 2^0

  = 12,380

  이렇게 해시값이 나온다.

  a는 아스키코드값으로 97이다. 제곱수는 제일 오른쪽에 있는 값에 0제곱부터 올라오는데

  아스키코드값에 2의 제곱수를 곱한 값을 다 더한 값이 해시값이 된다.

  여기서 abacdab가 bbacdab로 변한다면 12,444로 해시값이 변하게 되는데 이것을 눈사태 효과라고 한다.

  이러한 눈사태 효과 때문에 서로 다른 문자열은 해시값이 서로 다르게 되는데 이 원리를 이용해서

  문자열 매칭을 수행하게 된다.

 

처리과정

  라빈카프 문자열매칭 알고리즘에서는 해시 충돌을 감안해야 한다는 점에서 부분 문자열의 해시값이 일치하는

  경우에만 문자열을 재검사한다.

  

  부모해시값 : 12,398

  패턴해시값 : 12,380

  여기서 부모해시값과 패턴 해시값이 동일하지 않으므로 부모문자열을 한칸 이동한다.

 

  부모해시값 : 12,477

  패턴해시값 : 12,380

 

  부모해시값 : 12,380

  패턴해시값 : 12,380

  반복해서 이렇게 해시값이 동일하다면 매칭이 발생한 것이다.

 

  부모해시값 : 12,441

  패턴해시값 : 12,380

 

  부모해시값 : 12,437

  패턴해시값 : 12,380

  이렇게 한칸씩 이동하면서 매번 부모해시값과 패턴해시값을 비교한다음 다시 앞부분부터 차근차근

  모든 문자가 동일하지 확인하는 방식으로 문자열 매칭 여부를 확인한다.

  결과적으로 부모문자열에서 한번만 발생했다고 판단할 수 있는 것이다.

 

 

  해시함수를 반복적으로 계산할때는 부모 문자열에서 패턴문자열의 길이와 똑같은 크기로 한칸씩 이동하면서 해시값을

  확인한다고 했는데 그렇기 때문에 문자열이 이어진다는 특징을 따라갈 수 있는 것이다.

  여기서 한칸 이동하게 되면 결국 c, a, b, a, c, d 이 6자리는 그대로 사용된다는 특징이 있다.

  그래서 실제로 새로 다음 해시값을 구하는데에 있어서 시간 복잡도는 O(1)인것이다.

  다음 해시값은

  2 * (현재해시값 - 가장앞에 있는 문자의 수치) + 새문자의 수치

  이 연산으로 구할 수 있다.

  가장 앞에 있는 문자인 a는 97 * 2^6 = 6208이다.

  그리고 새로 들엉올 문자의 수치는 97 * 2^0 = 97이다.

  그럼 연산에 적용해보면 2 * (현재해시값(12,398) - 가장앞에 있는 문자의 수치(6208)) + 새문자의수치(97)

  이렇게 계산해주면 두번째 해시값인 12,477이라는 해시값이 나온다.

 

예제코드

 

#include <stdio.h>
#include <string.h>

char* parent = "acabacdabac";
char* pattern = "abacdab";

void check(char* parent, char* pattern, int start){
  //부모문자열에서 패턴문자열이 일치하는지 확인하는 함수
  //부모문자열과 패턴문자열의 해시값이 일치하는 경우에만 수행된다.
  //실제로 모든 문자가 다 일치하는지 확인하기 위해서 사용되는 함수다.
  //start는 해시값이 일치하기 시작한 인덱스
  int found = 1;
  int patternSize = strlen(pattern);
  
  for(int i = 0; i < patternSize; i++){
    if(parent[start + i] != pattern[i]){
      //부모문자열과 패턴문자열이 정확히 일치하는지 확인
      found = 0;
      break;
    }
  }
  if(found){
    printf("[인덱스 %d]에서 매칭 발생.\n", start + 1);
  }
}

void rabinkarp(char* parent, char* pattern){
  int parentSize = strlen(parent);
  int patternSize = strlen(pattern);
  int parentHash = 0, patternHash = 0, power = 1;
  //각 해시값을 0으로 초기화
  //power는 제곱승을 의미한다.
  
  for(int i = 0; i <= parentSize - patternSize; i++){
    if(i == 0){ //i가 0일때는 부모의 해시와 패턴의 해시값을 구하게 된다.
      for(int j = 0; j < patternSize; j++){
        parentHash = parentHash + parent[patternSize - 1 - j] * power;
        //뒤에서 앞으로 이동하면서 곱해나간다.
        //패턴문자열 : abacdab가 있는데
        //제일 뒤에 있는 b의 아스키코드값에 power를 곱한다.
        //제일 뒤에있는 문자는 2^0을 곱하니 1을 먼저 곱하게 되는것이다ㅣ.
        
        patternHash = patternHash + pattern[patternSize - 1 - j] * power;
        //parentHash와 마찬가지로 처리
        
        if(j < patternSize - 1){
          power = power * 2;
          //2제곱을 만들어주기위해 반복문이 한번 수행될때마다
          //2를 곱해서 제곱과 같은 형태로 유지하게 한다.
        }
      }
    }
    else{
      parentHash = 2 * (parentHash - parent[i - 1] * power) + parent[patternSize - 1 + i];
      //i가 증가했으니 부모문자열이 한칸 뒤로 넘어갔다는 의미이다.
      //다음 해시값을 구하는 연산인
      //2 * (현재해시값 - 가장앞에있는 문자수치) + 새문자수치 연산을 수행하는것
    }
    
    if(parentHash == patternHash){
      //두 해시값이 일치하는 경우에는 check로 값을 보내 모든 문자열이 일치하는지 확인
      check(parent, pattern, i);
    }
  }
}

int main(void){
  rabinkarp(parent, pattern);
  system("pause");
}

  [인덱스 3]에서 매칭발생   이라는 결과값을 확인할 수 있다.

 

 

 

레퍼런스

패스트캠퍼스 올인원 패키지 - 소프트웨어 베이직