문자열 알고리즘 (2) - 라빈 카프 (Rabin Karp) 알고리즘

1. 부르트 포스 (Naive Search)의 문제점

• Naive Search는 매 위치에서 찾을 문자열의 길이만큼 루프를 반복해야했음.

• 그러나 이는 매우 비효율적이며 O(N x M)의 시간복잡도가 소모됨 (M은 전체, N은 부분)

• Rabin Karp 알고리즘을 이용하면 평균적으로 O(M)으로 탐색시간을 단축시킬 수 있음.

 

2. 라빈 카프 (Rabin Karp) Algorithm

• Rabin Karp 알고리즘은 Hash를 활용하는 대표적인 알고리즘임.

• 기존 Naive Search의 경우, 모든 경우에 두번째 루프 (inner loop)를 수행하였음.

• 예를 들어 10000글자가 있는 글을 탐색하면서 100글자의 패턴을 매치하는데, 만약 99글자가 맞고 1글자가 틀리면 그 패턴은 매치되지 않음. 그러나 99번째 문자가 틀리다는 것을 모르기 때문에 loop를 돌면서 확인해야함

• Rabin Karp 알고리즘에서는 inner loop를 돌기전에 두 수의 Hash값을 먼저 비교함. 그래서 두 수의 해시값이 같을 때만 들어가서 진짜 동일한지 확인함. (해시함수를 업데이트 하는 로직이 O(1)이기 때문에 시가소모가 없음)

• 그러나 현실에서 실제로 Hash 값이 겹치는 경우는 거의 없다고 봐도 무방함. 때문에 정확히 매치되는 패턴에서만 실제로 맞는지 확인하여 매치되는 위치를 찾아낼 수 있음.

 

3. Hashcode

1) 해시 생성

 

해시코드는 위와같은 규칙으로 생성함. 만약 abcde가 있으면, $(a \times 2^4) + (b \times 2^3) + (c \times 2^2) + (d \times 2^1) + (e \times 2^0)$과 같이 생성한다. 이 때 문자의 수는 아스키코드를 의미한다.

    private int hash(String string, int length) {
        int hash = 0, power = 1;

        for (int i = length - 1; i >= 0; i--) {
            // 뒤부터 각 문자의 해시값을 구하여 합산한다

            hash += string.charAt(i) * power;
            power *= 2;
        }

        return hash;
    }

 

2) 해시 업데이트

해시코드의 생성은 O(N)이 걸림. 만약 해시코드를 매번 O(N)이 걸려서 생성해야한다면, 기존 나이브서치보다도 느릴 것임. Rabin Karp 알고리즘에서는 O(1)의 해시 업데이트 방법을 쓰는데 그 방식은 아래와 같음.

 

새로운해시 = 2 x (기존해시 - 가장 앞문자해시) + 가장 뒷문자해시

 

예를 들어 ABCDEFG라는 전체 문자열에서 3글자의 부분을 매칭하는 중이라면 가장 처음 매칭되는지 테스트할 전체부분은 ABC임. 때문에 $A \times 2^2 + B \times 2^1 + C \times 2^0$과 같은 해시값이 만들어짐. 이 때 만약 ABC가 매치되지 않았다면 한칸 옆으로 움직여서 BCD의 해시값을 구해야하는데, 가장 먼저 전체 해시값에서 A의 해시값을 빼면 BC의 해시값($B \times 2^1 + C \times 2^0$)이 된다. 해당 해시값에 2를 곱하면 $B \times 2^2 + C \times 2^1$이 되고 여기에 D의 해시값인 $D \times 1$을 넣으면 전체 해시는 $B \times 2^2 + C \times 2^1 + D \times 2^0$이 되어 새로운 해시값이 잘 계산된다. 

 

4. 소스코드

package string;

import java.util.LinkedList;
import java.util.List;

public class RabinKarpSearching implements StringSearching {
    public static void main(String[] args) {
        StringSearching searching = new RabinKarpSearching();
        List<Integer> pos = searching.search("hello nice to meet you", "nice");
        System.out.println(pos);
    }

    @Override
    public List<Integer> search(String whole, String part) {
        List<Integer> pos = new LinkedList<>();
        int wholeSize = whole.length(), partSize = part.length();

        int wholeHash = hash(whole, partSize);
        int partHash = hash(part, partSize);
        int power = 1 << (partSize - 1);

        for (int i = 0; i < wholeSize - partSize; i++) {
            if (i != 0) { // update hash
                int removeValue = whole.charAt(i - 1) * power; // 맨앞
                int newValue = whole.charAt(i - 1 + partSize); // 맨뒤 (partSize 만큼 뒤)
                wholeHash = 2 * (wholeHash - removeValue) + newValue;
            }

            if (wholeHash == partHash) {
                boolean find = true;
                for (int j = 0; j < partSize; j++) {
                    if (whole.charAt(i + j) != part.charAt(j)) {
                        find = false;
                        break;
                    }
                }
                if (find) {
                    pos.add(i);
                }
            }
        }

        return pos;
    }

    private int hash(String string, int length) {
        int hash = 0, power = 1;

        for (int i = length - 1; i >= 0; i--) {
            // 뒤부터 각 문자의 해시값을 구하여 합산한다

            hash += string.charAt(i) * power;
            power *= 2;
        }

        return hash;
    }
}

 

5. Reference