Rabin-Karp 알고리즘

Rabin-Karp 알고리즘은 문자열 내에서 특정 패턴을 찾는 해시 기반 문자열 검색 알고리즘으로, 효율적이고 빠른 검색이 가능하다는 점에서 널리 사용됩니다. 특히, 텍스트에서 다수의 패턴을 동시에 찾거나 문자열이 매우 긴 경우에 유용합니다. 이번 포스팅에서는 Rabin-Karp 알고리즘의 기본 개념과 동작 방식, 구현 방법, 그리고 사용 사례를 자세히 알아보겠습니다.

---

1. Rabin-Karp 알고리즘이란?

Rabin-Karp 알고리즘은 해시 함수(Hash Function)를 활용하여 텍스트와 패턴을 숫자값으로 변환한 후 빠르게 비교하는 방식으로 동작합니다. 이때 패턴을 찾고자 하는 텍스트의 각 부분 문자열에 대해 해시 값을 계산하고, 이 값이 패턴의 해시 값과 일치할 때만 실제로 문자열을 비교합니다.

주요 개념

1. Rolling Hash: 슬라이딩 윈도우 기법을 통해 텍스트의 부분 문자열을 빠르게 해싱합니다.
2. 충돌 처리: 해시 값이 일치할 때 실제 문자열을 비교하여 오탐(false positive)을 방지합니다.

Rabin-Karp 알고리즘은 해시 함수를 이용해 모든 문자를 개별적으로 비교하지 않으므로, 특히 대용량 텍스트 데이터에서 효과적입니다.

---

2. Rabin-Karp 알고리즘 동작 원리

Rabin-Karp 알고리즘은 다음 단계를 통해 작동합니다.

1. 해시 계산: 검색하고자 하는 패턴과 텍스트의 첫 번째 윈도우에 대해 해시 값을 계산합니다.
2. 해시 비교: 패턴의 해시 값과 텍스트의 부분 문자열 해시 값을 비교합니다.
3. 해시 재계산 (Rolling Hash): 윈도우를 한 칸씩 오른쪽으로 이동하며 해시 값을 업데이트합니다.
4. 문자열 비교: 해시 값이 일치할 때만 실제 문자열을 비교하여 패턴을 확인합니다.

---

3. Rabin-Karp 알고리즘의 예시

예를 들어, "ABABAC"이라는 패턴을 "ABABABAC"이라는 텍스트에서 찾고자 할 때의 과정을 살펴보겠습니다.

1. 패턴 해시 계산: "ABABAC"의 해시 값을 계산합니다.
2. 텍스트 윈도우 해시 계산: 텍스트에서 첫 번째 부분 문자열 "ABABAB"의 해시 값을 계산하고, 패턴 해시 값과 비교합니다.
3. 슬라이딩 윈도우 해시 업데이트: 해시 값이 일치하지 않는 경우, 텍스트의 윈도우를 오른쪽으로 이동하며 새 해시 값을 계산합니다.
4. 문자열 비교: 해시 값이 패턴과 일치하는 경우, 해당 위치에서 실제 문자열 비교를 수행하여 패턴을 확인합니다.

---

4. Rabin-Karp 알고리즘 구현 (C# 예시)

다음은 C#으로 Rabin-Karp 알고리즘을 구현한 코드 예시입니다.

using System;

public class RabinKarpAlgorithm
{
    private const int d = 256; // 알파벳 개수 (ASCII 기준)
    private const int q = 101; // 소수 (해시 모듈)

    public static void RabinKarpSearch(string text, string pattern)
    {
        int M = pattern.Length;
        int N = text.Length;
        int patternHash = 0; // 패턴의 해시 값
        int textHash = 0;    // 텍스트의 해시 값
        int h = 1;

        // h 값 계산: d^(M-1) % q
        for (int i = 0; i < M - 1; i++)
            h = (h * d) % q;

        // 패턴과 텍스트의 첫 윈도우 해시 값 계산
        for (int i = 0; i < M; i++)
        {
            patternHash = (d * patternHash + pattern[i]) % q;
            textHash = (d * textHash + text[i]) % q;
        }

        // 윈도우를 텍스트 전체에 슬라이딩
        for (int i = 0; i <= N - M; i++)
        {
            // 해시 값이 일치할 경우 문자열 확인
            if (patternHash == textHash)
            {
                bool match = true;
                for (int j = 0; j < M; j++)
                {
                    if (text[i + j] != pattern[j])
                    {
                        match = false;
                        break;
                    }
                }
                if (match)
                    Console.WriteLine($"패턴이 텍스트의 인덱스 {i}에 있습니다.");
            }

            // 윈도우를 오른쪽으로 이동 (해시 값 재계산)
            if (i < N - M)
            {
                textHash = (d * (textHash - text[i] * h) + text[i + M]) % q;

                // 음수 해시 값 처리
                if (textHash < 0)
                    textHash = (textHash + q);
            }
        }
    }

    public static void Main()
    {
        string text = "ABABABAC";
        string pattern = "ABABAC";
        RabinKarpSearch(text, pattern);
    }
}

코드 설명

1. 해시 값 계산: patternHash와 textHash를 초기 윈도우에 대해 계산합니다.
2. 해시 값 비교: 패턴 해시 값과 텍스트 해시 값이 일치할 경우, 실제 문자열을 비교합니다.
3. 해시 업데이트: 윈도우를 오른쪽으로 이동하며 텍스트 해시 값을 빠르게 재계산합니다.

실행 예시

위 코드를 실행하면 "ABABAC" 패턴이 "ABABABAC" 텍스트 내에서 발견되는 인덱스를 출력합니다.

---

5. Rabin-Karp 알고리즘의 시간 복잡도

Rabin-Karp 알고리즘의 시간 복잡도는 다음과 같습니다.

• 평균 시간 복잡도: O(n + m)
• 최악의 경우 시간 복잡도: O(n * m) (해시 충돌이 빈번하게 발생할 때)

알고리즘은 해시를 이용해 비교 연산을 최적화하므로 일반적으로 매우 빠르게 동작하지만, 해시 충돌이 빈번하면 성능이 저하될 수 있습니다.

---

6. Rabin-Karp 알고리즘의 활용 사례

1. 대량 텍스트에서 특정 키워드 검색: 대규모 텍스트 데이터에서 특정 패턴을 빠르게 검색하는 데 유용합니다.
2. 문서 비교: 문서 내에서 특정 문자열이 포함된 구간을 찾을 때 효과적입니다.
3. 악성 코드 탐지: 패턴 기반 검색을 통해 악성 코드나 바이러스 서명을 빠르게 탐지하는 데 사용됩니다.

---

7. Rabin-Karp 알고리즘 사용 시 유의점

1. 해시 충돌: 해시 함수 충돌이 발생할 수 있으므로 패턴 해시 값과 실제 문자열을 비교하는 과정이 필요합니다.
2. 해시 함수 선택: 해시 값이 고르게 분포되도록 소수 q와 해시 기수 d의 선택이 중요합니다.
3. 텍스트와 패턴이 매우 길 때: 해시 값 충돌을 최소화하고 빠르게 검색할 수 있도록 적절한 해시 함수를 사용하는 것이 좋습니다.

---

Rabin-Karp 알고리즘은 해시 함수를 통해 문자열 비교 연산을 빠르게 수행할 수 있도록 해주며, 텍스트에서 특정 패턴을 빠르게 찾는 데 매우 유용한 도구입니다.
다양한 해시 함수를 실험해 보며 더 빠르고 효율적인 문자열 검색을 경험해봅시다.