문자열 일치 알고리즘 - Rabin - Karp 알고리즘

문자열 일치 알고리즘 - Rabin - Karp 알고리즘
참고 자료
1 알고리즘 서론
2  lalor
3  기억의 파편
Rabin - karp 알고리즘 안내
실제 응용 에서 Rabin - Karp 알고리즘 은 문자열 일치 문제 에 대해 잘 작 동 합 니 다.Rabin - Karp 알고리즘 은 문자열 과 패턴 을 미리 처리 해 야 합 니 다. 예비 처리 시간 은 O (m) 이 고 최 악의 경우 실행 시간 은 O (n - m + 1) m 이지 만 특정한 가설 (어떤 가설 인지 모 르 겠 음) 을 바탕 으로 평균 적 인 상황 에서 실행 시간 이 좋 습 니 다.
설명 하기 편리 하도록 가설 하 다. 
∑ = {0, 1, 2......................................................................(더 일반적인 상황 에 대해 서 는 모든 문자 가 기수 가 d 인 표현법 중의 한 숫자 라 고 가정 할 수 있 습 니 다. d = | ∑ |.) k 길이 의 10 진수 로 k 개의 연속 문자 로 구 성 된 문자열 을 표시 할 수 있다.따라서 문자열 31415 는 10 진수 31415 에 대응 합 니 다.
모드 P [1. m] 를 알 고 있 습 니 다. p 를 설정 하면 이 모드 에 대응 하 는 10 진수 의 값 을 표시 합 니 다 (예 를 들 어 모드 P = "31415", 수치 p = 31415).주어진 텍스트 T [1. n] 에 대해 서 는 길이 가 m 인 하위 문자열 T [s + 1. s + m] (s = 0, 1, n - m) 에 해당 하 는 10 진수 의 값 을 ts 로 표시 합 니 다.ts = p 당 및 T [s + 1. s + m] = P[ 1.. m ] ，따라서 s 는 유효 변위 이 고 ts = p 로 만 작 동 합 니 다.
전처리 - p 와 t0
그래서 호 너 법칙 (Horner 's Rule) 을 사용 하여 O (m) 의 시간 내 에 p 의 값 을 계산 합 니 다.
         p = P[ m ] + 10( P[ m-1 ] + 10 ( P[ m-2 ] + .. + 10( P[ 2] + P[ 1 ]) ... ))
유사 하 다 O (m) 시간 내 에 T [1. m] 에 따라 t0 의 값 을 계산한다.
위 하 다 O (n - m) 의 시간 내 에 남 은 값 t1, t2,..., t (n - m) 를 계산 하여 상수 시간 내 에 ts 에 따라 t (s + 1) 를 계산 할 수 있다.... 때문에
        t ( s + 1) = 10 ( ts - 10^(m-1) T [ s+1 ] ) + T [ s + m +1]             ( 1 )
사실 가장 높 은 자 리 를 빼 고 한 명 을 왼쪽으로 옮 겼 어 요. T [s + m + 1] 를 얻 었 습 니 다. t ( s + 1) 。
미리 처리 하 는 시간 은 O (m) 입 니 다.
문자열 일치
사전 처 리 를 마 친 후에 문자열 이 일치 하 는 것 을 실행 할 수 있 습 니 다.우 리 는 ti (i = 0, 1, ...  n - m) p 와 비교 하면 합 법 적 으로 일치 하고 그렇지 않 으 면 불법 으로 일치 합 니 다.전체 일치 과정의 시간 은 O (n - m + 1)
그러나 상기 문 제 는 모델 p 의 길이 가 시간 에 비해 비교적 편리 하 다.p 와 ts 의 값 이 매우 클 때 p 의 결 과 는 너무 커서 이런 문 제 를 잘 처리 하지 못 할 것 이다.그래서 다음 개선 버 전이 생 겼 습 니 다.
구제 방법
p 와 ts 의 모드 를 계산 하기 위해 적당 한 모드 q 를 사용 합 니 다.모든 문 자 는 10 진수 입 니 다. p, t0 및 재 귀 식 1 계산 과정 은 모 q 를 진행 할 수 있 기 때문에 O (m) 시간 내 에 모 q 의 p 값 을 계산 할 수 있 습 니 다.시간 O (n - m + 1) 에서 모 q 의 모든 ts 값 을 계산 합 니 다.보통 모드 q 를 소수 로 선택 하여 10q 를 컴퓨터 길이 로 만 듭 니 다.
일반적인 상황 에서 d 진 알파벳 {0, 1,..., d - 1} 을 사용 할 때 선택 한 q 는 dq 의 값 을 한 컴퓨터 글자 길이 에 만족 시 키 고 재 귀 식 (1) 을 조정 하여 모 q 를 연산 하여 이 를
          
 t ( s + 1) = ( d ( ts -  T [ s+1 ] h ) + T [ s + m +1]  ) mod q
그 중 
≡ d ^ ( m-1 ) (mod q) 。
모드 q 가입 후, 우 리 는 이미 ts 를 통과 할 수 없습니다. ⊙ p (mod q) 는 ts = p 를 설명 할 수 없습니다. ts ⊙ p (mod q) 가 서 있 지 않 으 면 ts! = p 를 인정 합 니 다. 따라서 ts ▼ p (mod q) 시 우 리 는 ts 가 같은 지 더 테스트 해 야 한다. p. ts 가 일치 할 수도 있 고 가짜 가 일치 할 수도 있 기 때 문 입 니 다.
이 알고리즘 은 hash 를 사용 하 는 사상 입 니 다. 패턴 문자열 을 미리 처리 하고 mod, 주 문자열 을 하나씩 간단 한 hash 맵 을 한 다음 mod 를 비교 합 니 다.
의사 코드 는 다음 과 같다.

RABIN-KARP-MATCHER( T,P,d,q)
1  n ← length[ T ]
2  m ← length[ P]
3  h  ← d^(m-1) mod q
4  p  ← 0
5  t0 ← 0
6  for i ← 1 to  m         Preprocessing(   )
7           do p ← (dp + P[i]) mod q
8                t0 ← (dt0 + T[i]) mod q
9      for s ← 0 to s-m     Matching(    )
10          do if  p = t
11                then  if P[1..m] = T[s+1..s+m]         p   T           
12                     then   print "  "
13              if s < n - m
14                then t(s+1) ← (d (ts - T[s+1] h) + T[s+m+1]) mod q

코드 구현 

*Copyright(c) Computer Science Department of XiaMen University  
* 
*Authored by laimingxing on: 2012  03  04      18:18:28 CST 
* 
* @desc: 
* 
* @history 
*/  
// d = 256 ; q = 127

void RABIN_KARP_MATCHER( char *T, char *P, int q)  
{  
    assert( T && P && q > 0 );  
    int M = strlen( P );  
    int N = strlen( T );  
    int i, j;  
    int p = 0;//hash value for pattern  
    int t = 0;//hash value for txt  
    int h = 1;  
      
    //the value of h would be "pow( d, M - 1 ) % q "      
    for( i = 0; i < M - 1; i++)  
        h = ( h * d ) % q;  
  
    for( i = 0; i < M; i++ )  
    {  
        p = ( d * p + P[i] ) % q;  
        t = ( d * t + T[i] ) % q;  
    }  
      
    //Slide the pattern over text one by one  
    for( i = 0; i <= N - M; i++)  
    {  
        if( p == t)  
        {  
            for( j = 0; j < M; j++)  
                if(T[i+j] != P[j])  
                    break;  
            if( j == M )  
                printf("Pattern occurs with shifts: %d
", i);  
        }  
        //Caluate hash value for next window of test:Remove leading digit,  
        //add trailling digit  
        if( i < N - M )  
        {  
            t = ( d * ( t - T[i] * h ) + T[i + M] ) % q;  
            if( t < 0 )  
                t += q;//           t     ，          。  
        }  
    }  
}     

Rabin - Karp - Matcher 의 사전 처리 시간 은 O (m) 이 며, 일치 시간 은 최 악의 경우 O (n - m + 1) m 입 니 다.
비록... 일지 라 도 Rabin-Karp-Matcher 최 악의 경우 소박 함 과 일치 하지만 실제 응용 에 서 는 소박 한 알고리즘 보다 훨씬 빠 르 고 응용 이 넓다.