[알고리즘] 라빈-카프 알고리즘

라빈-카프(Rabin-Karp) 알고리즘은 1987년 리처드 M. 카프와 마이클 O. 라빈에 의해 개발된 문자열 검색 알고리즘입니다.

이 알고리즘은 주어진 텍스트에서 특정 패턴 문자열을 효율적으로 찾기 위해 해싱(Hashing) 기법을 활용합니다.

특히, 롤링 해시(rolling hash)라는 기법을 사용하여 텍스트의 각 위치에서 패턴과의 일치 여부를 빠르게 확인할 수 있습니다.

 

라빈-카프 알고리즘의 기본 개념은 텍스트와 패턴을 비교할 때, 각 문자를 일일이 대조하는 대신,

텍스트의 부분 문자열과 패턴의 해시 값을 비교함으로써 비교 과정을 단순화하는 것입니다.

해시 값이 일치하는 경우에만 실제 문자열 비교를 수행하여, 불필요한 비교를 줄이고 속도를 높입니다.

이 과정에서 롤링 해시를 사용하여 이전에 계산된 해시 값을

바탕으로 다음 해시 값을 효율적으로 계산할 수 있습니다.

이 알고리즘의 가장 큰 의의는 문자열 검색 문제를 해싱 문제로 변환함으로써

비교적 간단한 연산을 통해 빠른 검색이 가능해졌다는 점입니다.

특히, 다중 패턴 검색에 유리하며, 특정 문자 열이나 패턴이 다수 포함된 텍스트에서

매우 효율적으로 작동할 수 있습니다. 따라서 표절 검사에 자주 사용됩니다.

 

라빈-카프 알고리의 특징

---

1. 해싱

라빈-카프 알고리즘의 핵심은 해시 함수를 이용하여 문자열을 숫자 값으로 변환하는 것입니다. 해시 함수는 텍스트 내에서 패턴과 동일한 길이의 부분 문자열을 빠르게 비교할 수 있도록 해줍니다. 이 과정에서, 텍스트와 패턴의 해시 값을 비교하여 일치 여부를 판단하고, 해시 값이 일치할 때만 실제 문자열 비교를 수행합니다.

2. 롤링 해시 기법

라빈-카프 알고리즘의 또 다른 중요한 특징은 롤링 해시 기법입니다. 롤링 해시는 텍스트의 각 위치에서 새로운 부분 문자열로 이동할 때, 기존 해시 값을 사용하여 새 해시 값을 빠르게 계산하는 방법입니다. 이를 통해 전체 문자열을 처음부터 끝까지 비교하는 대신, 각 문자 이동 시 해시 값을 효율적으로 업데이트할 수 있습니다.

롤링 해시를 사용함으로써, 텍스트의 길이가 길어질수록 효율성이 증가합니다. 텍스트 내의 모든 부분 문자열을 처음부터 해시 값을 재계산하지 않고, 이전 계산을 기반으로 새로운 값을 빠르게 구할 수 있기 때문입니다.

라빈-카프 알고리즘의 동작 방법

---

1. 초기 설정: 패턴의 해시 값 계산

• 해시 함수 선택: 먼저, 문자열을 숫자로 변환하는 해시 함수를 정의합니다. 이 해시 함수는 주어진 문자열을 고유한 숫자 값으로 변환하며, 같은 문자열은 항상 동일한 해시 값을 가져야 합니다. 또한, 서로 다른 문자열은 가능하면 다른 해시 값을 가져야 합니다.
• 패턴 해시 값 계산: 주어진 패턴 문자열의 해시 값을 계산합니다. 이 해시 값은 이후 텍스트의 부분 문자열들과 비교할 때 사용됩니다.

2. 텍스트의 첫 부분 문자열 해시 값 계산

• 부분 문자열의 해시 값 계산: 텍스트에서 패턴의 길이와 동일한 첫 번째 부분 문자열을 추출하고, 이 부분 문자열의 해시 값을 계산합니다. 이 해시 값은 이후에 패턴의 해시 값과 비교됩니다.

3. 해시 값 비교 및 매칭

• 해시 값 비교: 패턴의 해시 값과 텍스트의 부분 문자열 해시 값을 비교합니다.
  • 해시 값이 일치하지 않는 경우: 다음 부분 문자열로 이동하여 해시 값을 재계산하고 비교를 계속합니다.
  • 해시 값이 일치하는 경우: 해 시 값이 일치하더라도 실제 문자열이 다를 수 있기 때문에, 해당 부분에서 패턴과 문자열이 일치하는지 확인하기 위해 직접적인 문자열 비교를 수행합니다.

4. 롤링 해시를 사용한 다음 부분 문자열로 이동

• 롤링 해시 계산: 텍스트에서 다음 부분 문자열로 이동할 때, 이전 해시 값을 바탕으로 새로 추가된 문자와 제거된 문자를 고려하여 해시 값을 빠르게 업데이트합니다. 
• 해시 값 업데이트: 롤링 해시를 통해 새로 계산된 해시 값과 패턴의 해시 값을 다시 비교하고, 동일한 과정을 반복합니다.

5. 전체 텍스트에 대해 반복

• 반복 과정: 텍스트의 마지막 부분 문자열까지 위의 과정을 반복합니다. 패턴과 일치하는 부분 문자열을 찾으면 그 위치를 기록합니다.

6. 결과 반환

• 일치하는 위치 반환: 텍스트 내에서 패턴이 발견된 모든 위치를 반환합니다. 만약 패턴이 텍스트 내에 존재하지 않으면, 아무 위치도 반환하지 않습니다.

라빈-카프 알고리즘 구현

---

 

public class RabinKarp {
    // 문자열을 검색하는 메서드
    public static void search(String text, String pattern) {
        int d = 256; // 사용 가능한 문자 수 (ASCII 문자 집합)
        int q = 101; // 소수, 해시 충돌을 줄이기 위한 모듈로 사용
        int n = text.length();
        int m = pattern.length();
        int i, j;
        int p = 0; // 패턴의 해시 값
        int t = 0; // 텍스트의 현재 창의 해시 값
        int h = 1;

        // h = (d^(m-1)) % q 계산
        for (i = 0; i < m - 1; i++) {
            h = (h * d) % q;
        }

        // 패턴과 텍스트의 첫 번째 문자열의 해시 값 계산
        for (i = 0; i < m; i++) {
            p = (d * p + pattern.charAt(i)) % q;
            t = (d * t + text.charAt(i)) % q;
        }

        // 텍스트에서 패턴을 찾는 과정
        for (i = 0; i <= n - m; i++) {
            // 현재 문자열의 해시 값과 패턴의 해시 값이 일치하면
            if (p == t) {
                // 해시 값이 일치하는 경우 문자도 일치하는지 확인
                for (j = 0; j < m; j++) {
                    if (text.charAt(i + j) != pattern.charAt(j)) {
                        break;
                    }
                }

                // 패턴이 텍스트 내에 존재하는 경우
                if (j == m) {
                    System.out.println("패턴 위치: " + i);
                }
            }

            // 다음 문자열로 이동 (롤링 해시 사용)
            if (i < n - m) {
                t = (d * (t - text.charAt(i) * h) + text.charAt(i + m)) % q;

                // 음수 해시 값을 양수로 변환
                if (t < 0) {
                    t = (t + q);
                }
            }
        }
    }

    // 메인 메서드
    public static void main(String[] args) {
        String text = "ABCCDDAEFG";
        String pattern = "CDD";
        search(text, pattern);
    }
}

 

라빈-카프 알고리즘 시간복잡도

---

1. 평균 시간 복잡도

라빈-카프 알고리즘에서 해시 값을 계산하는 연산과 패턴을 비교하는 연산을 기준으로 시간 복잡도를 분석할 수 있습니다.

• 해시 계산: 텍스트에서 패턴의 길이와 동일한 첫 번째 부분 문자열의 해시 값을 계산하는 데 걸리는 시간은 O(m)입니다. 여기서 m은 패턴의 길이입니다.
• 롤링 해시: 이후 각 문자열에서 새로운 부분 문자열로 이동할 때, 롤링 해시를 사용하여 해시 값을 갱신하는 데 걸리는 시간은 O(1)입니다. 따라서 텍스트의 나머지 n−m+1개의 문자열에서 해시 값을 계산하는 데는 O(n−m)이 소요됩니다. 여기서n은 텍스트의 길이입니다.
• 해시 비교: 해시 값이 일치하는 경우에만 패턴과 해당 부분 문자열을 실제로 비교합니다. 해시 값이 일치하지 않는 경우, 문자열 비교 없이 바로 다음 창으로 넘어가므로 시간 복잡도에 큰 영향을 미치지 않습니다. 해시 충돌이 적은 경우 실제로 문자열 비교가 필요한 경우는 매우 드뭅니다.

따라서 평균 시간 복잡도는 O(n+m)입니다.

2. 최악의 경우 시간 복잡도

최악의 경우, 해시 충돌이 빈번하게 발생하면 모든 문자열에서 실제 문자열 비교를 해야 할 수 있습니다. 해시 충돌은 서로 다른 문자열이 동일한 해시 값을 가지는 경우로, 충돌이 발생하면 텍스트의 부분 문자열과 패턴을 문자 하나하나 비교해야 합니다.

• 최악의 경우는 해시 값이 자주 충돌하여 텍스트의 각 문자열에서 패턴의 길이만큼 문자 비교가 필요하게 됩니다.
• 이 경우 문자열 비교는 O(m)의 시간이 소요되며, n−m+1개의 문자열에 대해 비교해야 합니다.

따라서 최악의 경우 시간 복잡도는 O(n⋅m)입니다.