문자열 패턴 매칭 2 - Rabin Karp

Michael O. Rabin과 Richard M. Karp가 함께 만든 이 알고리즘은 문자열 검색을 위해 해쉬값 함수를 이용한다.  매번 문자 하나씩 비교하지 않고 패턴의 해쉬와 부분 문자열의 해쉬만을 비교하기 때문에 상당히 빠른 성능을 보여주고 구현도 쉬운 편이다.

 

해쉬값의 생성

해쉬값은 문자들에 어떤 가공을 해서 일정한 패턴으로 만들어내는 값으로 문자열이 가지고 있는 hashCode와는 다른 값이다. 

패턴의 해쉬값은 당연히 고정되어있다.

비교 대상인 문자열의 해쉬값은 패턴 불일치로 대상 범위가 달라질 때마다 매번 계산되어야 한다. 이때 계산되는 해쉬는 아주 빠른 시간에 처리되어야 하고 새로 들어오는 문자와 나가는 문자의 처리에서 일관성이 있어야 한다.

이를 위해 패턴은 통상 아래 수식으로 계산된다.

 

 

여기서 P는 그냥 임의 의 수이고 자리수는 문자의 길이에서 index를 뺀 값이 된다.

 

예를 들어 P를 10이라고 했을 때 ABCD라는 문자열의 해쉬값은 아래와 같다.

이 과정에서 가장 앞 자리에 곱해지는 수는 10^3 즉  1000이다. 이 값은 나중에 다음 해쉬를 구할 때 매우 유용하게 사용된다. 이 값을 head라고 하자.

그럼 검색 구간이 변경되는 과정에서 어떻게 해쉬의 일관성이 유지될 수 있을까?

일단 처음 해쉬값은 위 설명과 동일하다.

처음의 해쉬를 tHash라고 하자.

 

여기서 미스매치가 난다면 다음 문자열들을 비교해야 하므로 tHash에서 'A'에 해당하는 값을 빼고 'E'에 해당하는 값을 추가시켜야 한다. 나머지 문자열들은 한단계 씩 상위 단계로 가기 위해 지수가 1씩 증가해야 한다.

 

'A'라는 문자열은 인덱스 기반으로 쉽게 찾을 수 있는데 10^3이 곱해져야한다.(패턴의 길이가 길다면 지수도 커질 것이다. 이 연산 과정을 줄이기 위해 위에서 head라는 값을 저장해 뒀음을 기억하자.)

즉 (tHash - target.charAt(i) * head) 와 같은 식으로 맨 앞에 있던 'A'의 영향을 제거할 수 있다.

이제 B, C, D로만 구성된 해쉬를 한단계 올리기 위해서는 처음 설정했던 P를 곱해주면 된다.

(tHash - target.charAt(i) * head) * P

마지막으로 추가될 문자를 더해주자.(이 문자는 아마 처음 위치 i에서 패턴의 길이만큼 떨어져 있을 것이다.)

(tHash - target.charAt(i) * head) * P + target.charAt(pl + i)

 

알고리즘 구현

전체적인 소스코드는 아래와 같다.

private static void rabinKarp(String target, String pattern) {
    int fl = target.length();
    int pl = pattern.length();
    final int P = 10;
    // 맨 큰 단위에서 곱해지는 수
    long head = 1;
        
    long pHash = 0;
    long tHash = 0;
    // 초기 해쉬 구하기
    for (int j = 0; j < pl; j++) {
        pHash = (pHash * P + pattern.charAt(j));
        tHash = (tHash * P + target.charAt(j));
        if (j != 0) {
            head = (head * P);
        }
    }

    for (int i = 0; i <= fl - pl; i++) {
        if (pHash == tHash) {
            System.out.print(i + "\t");
        }
        // 해쉬가 다르다면 다음 해쉬 찾아보기
        if (i + pl < fl) {
            tHash = (tHash - target.charAt(i) * head) * P + target.charAt(pl + i);
        }
    }
}

 

하지만 이렇게 작성한 코드를 적용해보면 문제는 fail이 된다. 답이 틀렸단다.

곱해지는 P를 10이 아닌 7로 바꾸로 시도해보면 성공한다. 이런 케바케가 발생하다니. ㅜㅜ

어디가 잘못된걸까? 문제는 해쉬과정에 있다. 간단하게 만든 해쉬 함수이기 때문에 해쉬값이 일치하더라도 실제 패턴과 일치하지 않는 경우가 발생한다. 이런 경우를 해쉬 충돌이라고 한다. P를 10으로 처리했을 때는 해쉬 충돌이 발생해서 동일하지 않은 문자열이 동일하다고 판단되었고 P가 7인 경우는 다행히 해쉬 충돌이 발생하지 않은 것이다.

 

이를 보완하기 위해 해쉬값이 일치하는만 실제 문자열을 비교해보는 방법이 있다.

for (int i = 0; i <= fl - pl; i++) {
    // 해쉬 값이 일치하는 상황에서 문자열 비교
    if (pHash == tHash && pattern.equals(target.substring(i, i + pl))) {
        System.out.print(i + "\t");
    }
    // 해쉬가 다르다면 다음 해쉬 찾아보기
    if (i + pl < fl) {
        tHash = (tHash - target.charAt(i) * head) * P + target.charAt(pl + i);
    }
}

 

하지만 이번에는 시간 초과가 발생한다. ㅜㅜ

패턴의 길이가 매우 길다면 그냥 brute-force 형태가 되기 때문에 시간이 그만큼 소요되는 것이다.

결국 Rabin-Karp는 해쉬값을 구하는 방식과 테스트 케이스에 따라 될 수도 있고 안될 수도 있다.

Brute Force: https://goodteacher.tistory.com/127
RabinKarp: https://goodteacher.tistory.com/128
KMP: https://goodteacher.tistory.com/129