라빈-카프(Rabin-Karp) 알고리즘

1. 개념 ⚽

  라빈-카프(Rabin-Karp) 알고리즘이란 해싱(Hashing)을 이용한 문자열 매칭 알고리즘이다. 비교하고자 하는 문자들과 패턴의 문자들을 일일이 비교하는 대신에 문자열의 해시값을 비교하는 방식으로 진행된다.

 

2. 동작방식(연습용) 🏀

동작 방식은 아래와 같다.

1. 해시 함수를 설정한다.
2. 해시 함수를 이용하여 패턴의 해시값을 구한다.
3. 비교하고자 하는 문자열의 해시값을 구한다.
4. 일치하면 패턴과 찾은 문자열을 1:1 비교한다.
   일치하지 않으면 비교하고자 하는 문자열을 한 칸 뒤로 옮겨서 3번부터 다시 시작한다.

  해시값이 같더라도 1:1 매칭을 통해서 최종적으로 패턴과 비교하고자 하는 문자열이 일치하는지 확인하는 절차가 필요하다. 그 이유는 해시값이 같다고 해서 무조건 같은 문자열이라고 보장할 수 없기 때문이다.

  매우 간단한 예시를 통해 동작방식을 이해해 보자. '4 1 2 3 5'라는 문자열과 '1 2 3'이라는 패턴이 주어졌다고 하자.

  해시함수은 문자열을 10진수로 표현하는 것이라고 하자. 예를 들어, 패턴 '1 2 3'의 해시값은 123이 되고 '4 3 1'의 해시값은 431이 될 것이다.

  위에서 살펴본 동작방식 이용하여 패턴과 일치하는 문자열을 찾아보자.

1. 비교하고자 하는 문자열의 해시값(412) != 패턴의 해시값(123)

2. 비교하고자 하는 문자열의 해시값(123) == 패턴의 해시값(123)

3. 1:1 매칭 비교

  해시값도 일치하고 1:1 매칭도 성립하므로 패턴과 일치하는 문자열의 찾게 되었다.

 

3. 동작방식(실전용) 🏐

  위의 방식으로 해시 함수를 사용하면 해시값이 너무 커지는 문제가 존재한다. 라빈-카프 알고리즘에 사용되는 일반적인 해시 함수는 다음과 같다.

  해시 함수는 '각 문자의 아스키코드 값에 2의 제곱 수를 차례대로 곱하여 더해주는 것'을 사용한다. 이 방식을 사용하면 서로 다른 문자열의 경우 일반적으로 다른 해시 값을 가지게 된다.

  예를 들어 'aba'의 해시 값은 '(97 * 2^2) + (98 * 2^1) + (97 * 2^0) = 388 + 196 + 97 = 681', 'bab'의 해시값은 '(98 * 2^2) + (97 * 2^1) + (98 * 2^0) = 392 + 194 + 98 = 684'가 되게 된다.

  문자열 'ababacab'와 패턴 'baca'를 이용하여 실제 적용을 해보자. 패턴의 해시값은 '(98 * 2^3) + (97 * 2^2) + (99 * 2^1) + (97 * 2^0) = 1467'이다.

1. 비교하고자 하는 문자열의 해시값 : (97 * 2^3) + (98 * 2^2) + (97 * 2^1) + (98 * 2^0) = 1460

패턴의 해시값(1467)과 불일치

2. 비교하고자 하는 문자열의 해시값 : (98 * 2^3) + (97 * 2^2) + (98 * 2^1) + (97 * 2^0) = 1465

패턴의 해시값(1467)과 불일치

3. 비교하고자 하는 문자열의 해시값 : (97 * 2^3) + (98 * 2^2) + (97 * 2^1) + (99 * 2^0) = 1461

패턴의 해시값(1467)과 불일치

4) 비교하고자 하는 문자열의 해시값 : (98 * 2^3) + (97 * 2^2) + (99 * 2^1) + (97 * 2^0) = 1467

패턴의 해시값(1467)과 일치

5. 1:1 매칭 비교

  해시값도 일치하고 1:1 매칭도 성립하므로 패턴과 일치하는 문자열의 찾게 되었다.

 

4. Rolling Hash ⚾

  Rolling Hash를 이용한다면 비교하고자 하는 문자열의 해시값을 더 간단하게 구할 수 있다. Rolling Hash란 Sliding Window와 같이 문자열을 훑으면서 해시값을 구하는 데 사용된다. 방법은 중복되는 해시값은 그대로 두고 업데이트되는 부분만 해시값을 계산해 주는 것이다. (Sliding Window와 같은 방법이다.)

  위에서 사용한 해시 함수를 이용한다면, 새로운 문자열의 해시값은 '2 * (이전 문자열의 해시값 - 가장 앞에 있는 문자의 값) + 새로 들어온 문자의 값'이라고 할 수 있다. '이전의 해시값을 구한 방식'과 'Rolling Hash를 이용해서 값을 구하는 방식'을 비교하면서 살펴보자.

[기존 방식]

주어진 문자열 : ababacab

1. 비교할 문자열 : abab
   해시값 : (97 * 2^3) + (98 * 2^2) + (97 * 2^1) + (98 * 2^0) = 1460
2. 비교할 문자열 : baba
   해시값 : (98 * 2^3) + (97 * 2^2) + (98 * 2^1) + (97 * 2^0) = 1465
3. 비교할 문자열 : abac
   (97 * 2^3) + (98 * 2^2) + (97 * 2^1) + (99 * 2^0) = 1461
4. 비교할 문자열 : baca
   (98 * 2^3) + (97 * 2^2) + (99 * 2^1) + (97 * 2^0) = 1467

[Rolling Hash를 이용하는 방식]

주어진 문자열 : ababacab

1. 비교할 문자열 : abab
   해시값 : (97 * 2^3) + (98 * 2^2) + (97 * 2^1) + (98 * 2^0) = 1460
2. 비교할 문자열 : baba
   해시값 : 2 * (1460 - (97 * 2^3)) + 97 = 1465
3. 비교할 문자열 : abac
   해시값 : 2 * (1460 - (98 * 2^3)) + 99 = 1461
4. 비교할 문자열 : baca
   해시값 : 2 * (1460 - (97 * 2^3)) + 97 = 1467

 

5. MOD & 오버플로우 🏈

  정확한 해시값의 일치 여부를 검증하기 위해서 모듈러 연산을 사용하는 경우가 있다. 하지만, 일반적으로 오버플로우가 발생하더라도 해시값은 동일하다고 볼 수 있기 때문에 모듈러 연산을 사용하지 않아도 정상적으로 동작한다. (더 안정적인 프로그램을 작성하고자 한다면 모듈러 연산을 사용하도록 하자.)

 

6. 구현(JAVA) 🎱

public static void main(String[] args) {
    String str = "ababacab";
    String pattern = "baca";

    int findIdx = 0;
    boolean isFind = false;

    int strLen = str.length();
    int patternLen = pattern.length();
    int power = 1;


    int compareStrHash = 0;
    int patternHash = 0;
    for(int i = 0; i <= strLen - patternLen; i++) {
        // 첫 비교 문자열과 패턴 해시값 구하기
        if(i == 0) {
            for(int j = 0; j < patternLen; j++) {
                compareStrHash += str.charAt(patternLen - 1 - j) * power;
                patternHash += pattern.charAt(patternLen - 1 - j) * power;
                if(j < patternLen - 1) {
                    power *= 2;
                }
            }
        }
        else {
            compareStrHash = 2 * (compareStrHash - str.charAt(i - 1) * power) 
                            + str.charAt(patternLen - 1 + i); 
        }

        // 해시값이 일치하는 경우 // 1:1 매칭 비교
        if(compareStrHash == patternHash) {
            for(int j = 0; j < patternLen; j++) {
                if(str.charAt(i + j) != pattern.charAt(j)) {
                    break;
                }

                if(j == patternLen - 1) {
                    isFind = true;
                    findIdx = i;
                }
            }
        }

        if(isFind) {
            break;
        }
    }

    if(isFind) {
        System.out.println(findIdx + "번째에서 일치하는 문자열을 찾았습니다.");
    }
    else {
        System.out.println("일치하는 문자열을 찾지 못했습니다.");
    }
    // 3번째에서 일치하는 문자열을 찾았습니다.
}

 

7. 시간복잡도 🎳

  주어진 문자열의 길이가 N이고 패턴의 길이가 M이라고 할 때, 최악의 경우 시간복잡도는 O(NM)을 가진다. 주어진 문자열의 마지막에 찾고자 하는 문자열이 있고 항상 해시 충돌이 일어나는 경우가 있을 수 있기 때문이다.

  하지만, 일반적으로는 O(NM) 보다 적게 소요된다.

 

해당 글은
나동빈 님의 '31. 라빈 카프(Rabin-Karp) 알고리즘',
별준 님의 'Rabin-karp(라빈 카프) 알고리즘',
기억하고싶은것들 블로그의 '[알고리즘] 라빈 카프(Rabin-Karp)(문자열 탐색)(Rolling Hash)'
를 참고하였습니다.