rabin-karp

이번에는 hashing을 활용한 문자열 매칭 알고리즘인 라빈-카프(rabin-karp)에 대해 알아보고자 합니다.

 

 

라빈-카프 알고리즘의 시간복잡도는 O(N)으로 지금까지 진행하였던 왠만한 문자열 매칭 알고리즘보다 빠르다는 장점이 있습니다.

그치만, 여러 가지 다양한 부분에서 문제점이 있어 실제 서비스에서는 사용하기 어렵다는 단점이 있습니다.

 

장점

 - 시간이 빠르다

단점

 - hashing 값이 충돌이 날 수 있다.

 - overflow가 발생할 수 있다.

 

"abbaba"라는 문자열에 "aba"라는 문자가 포함되어 있는지 확인하는 방법을 예시로 들어보겠습니다.

hashing을 사용하기 때문에, 자리수마다의 문자의 아스키 코드 넘버에 특정 값을 곱하여 하나의 숫자 단위로 표현합니다.

2를 활용하여 예시를 들면 pattern은 97 * 2^2 + 98 * 2^1 + 97 * 2^0 = 681 이라는 숫자로 표현이 가능합니다.

마찬가지로 parent는 pattern의 길이만큼 계산한 97 * 2^2 + 98 * 2^1 + 98 * 2^0 = 682로 표현이 가능합니다.

이후 단어 불일치가 발생할 경우, 1자리수 위치를 옮긴 후, 서식을 적용합니다.

 

 

소스코드로 표현하면 다음과 같습니다.

public static boolean rabin_karp(String parent, String pattern) {
        int parentSize = parent.length(), patternSize = pattern.length();
        int parentHash = 0, patternHash = 0, power = 1;
        for (int i = 0; i <= parentSize - patternSize; i++) {
            if (i == 0) {
                for (int j = 0; j < patternSize; j++) {
                    parentHash += parent.charAt(patternSize - j - 1) * power;
                    patternHash += pattern.charAt(patternSize - j - 1) * power;

                    if (j < patternSize - 1) {
                        power *= 2;
                    }
                }
            } else {
                parentHash = 2 * (parentHash - parent.charAt(i - 1) * power) + parent.charAt(patternSize - 1 + i);
            }

            if (parentHash == patternHash) {
                boolean find = true;
                for (int j = 0; j < patternSize; j++) {
                    if (parent.charAt(i + j) != pattern.charAt(j)) {
                        find = false;
                        break;
                    }
                }

                if (find) {
                    return true;
                }
            }
        }
        return false;
    }

 

power에 해당하는 값은 2를 곱하여 상승시키지만, 다른 값을 사용하여도 됩니다.

추가로, 큰 값을 사용할 경우 overflow가 발생할 수 있어 모듈러 연산을 활용하는 것도 하나의 방법입니다.

 

 

https://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_algorithm

Rabin–Karp algorithm - Wikipedia

http://courses.csail.mit.edu/6.006/spring11/rec/rec06.pdf