[박혜웅] Karp-Rabin

• Karp-Rabin 의 특징

  • fingerprint 후 hash function 적용

    • h(k) = k mod q ( q>m, q=prime)

  • 텍스트의 각 윈도우와 패턴에 대하여, 문자열을 십진수(또는 d진수)로 바꾸고 이를 해쉬값으로 변환하여 사용

    • 예: 문자열 "12345" -> 숫자 12345 -> 해쉬값 5

      •  h(x)= mod 5일 경우

  • 성능

    • 전처리과정 시간복잡도: O(m)

    • 검색과정 최악의 시간복잡도: O(mn)

      • 텍스트의 모든 윈도우의 해쉬값이 패턴의 해쉬값과 같을 경우

    • 검색과정 예상 시간복잡도: O(m+n)

      • 텍스트에서 n회  비교하고, 충돌이 없을 경우 발견된 위치에서 텍스트와 패턴이 일치하는지 m회 검증
      • 대부분 해쉬값이 같지 않을 것이므로 일반적으로 O(m+n)일 확률이 높다.

 

• fingerprint의 개념

  • 길이가 m인 패턴P에 대하여, fingerprint 함수 f(P) 는 O(m) 시간에 계산가능하다.

  • f(P) ≠ f(T[s..s+m-1]) 이면, P≠T[s..s+m-1] 이다.

    • 텍스트 T를 위치 s부터 m길이 단위로 나눈 후, fingerprint 함수를 통하여 비교하면, 패턴 P와 T[s..s+m-1]가 일치하는지 알수 있다.

  • f' = f(T[s+1..s+m]) 는 T[s..s+m-1]를 이용하여 O(1)시간에 계산할 수 있다.

    • 이미 위치 s부터 s+m-1까지 fingerprint 값을 계산했다면, 그 다음 위치인 s+1부터 s+m은 이미 계산된 값을 이용해 쉽게 구할 수 있다.
    • 
       

 

• fingerprint 를 이용한 알고리즘의 예

  • 알파벳 ∑={0,1,2,3,4,5,6,7,8,9}

  • 문자를 숫자로 변환

    • f("1045") =  (1*10³⁾ + (0 * 10²) + (4*10¹) + (5*10⁰)  = 1045
  •  
    

 

 

• 문자열을 해쉬값으로 변환하는 과정

  1. 알파벳 수(d) 계산

     • 
       
       

  2. fingerprint( 문자열을 d진수로 변환 )

     

  3. hash ( 변환된 숫자를 충분히 큰 수 q 로 나눠서 나머지 사용 )

     • 과정2에서 변환된 수가 너무 크기 때문에, 그 값대신 나머지 값 사용
     • 나머지를 사용함으로써, 해쉬값이 같을 경우, 텍스트와 패턴의 문자를 하나식 검사하는 과정이 필요
       

 

 

• Karp-Rabin 의 실행
•    

 

• Karp-Rabin 의 소스

1. #define REHASH(a, b, h) ((((h) - (a)*d) << 1) + (b))
   void KR(char *x, int m, char *y, int n) {
      int d, hx, hy, i, j;
   
      /* Preprocessing */
      /* computes d = 2^(m-1) with
         the left-shift operator */
      for (d = i = 1; i < m; ++i)
         d = (d<<1);
   
      for (hy = hx = i = 0; i < m; ++i) {
         hx = ((hx<<1) + x[i]);
         hy = ((hy<<1) + y[i]);
      }
   
      /* Searching */
      j = 0;
      while (j <= n-m) {
         if (hx == hy && memcmp(x, y + j, m) == 0)
            OUTPUT(j);
         hy = REHASH(y[j], y[j + m], hy);
         ++j;
      }
   
   }