본문 바로가기

자료구조 & 알고리즘/문자열 매칭 알고리즘

[박혜웅] 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]) 이면, PT[s..s+m-1] 이다.

      • 텍스트 T를 위치 s부터 m길이 단위로 나눈 후, fingerprint 함수를 통하여 비교하면, 패턴 PT[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*103) + (0 * 102) + (4*101) + (5*100)  = 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;
       }

    }

'자료구조 & 알고리즘 > 문자열 매칭 알고리즘' 카테고리의 다른 글

[박혜웅] Shift-Or  (0) 2010.03.27
[박혜웅] Knuth-Morris-Pratt(KMP)  (0) 2010.03.27
[박혜웅] Brute Force(BF)  (0) 2010.03.27
[박혜웅] Boyer-Moore-Horspool  (0) 2010.03.27
[박혜웅] Boyer-Moore  (0) 2010.03.27