라빈-카프 알고리즘(Rabin-Karp Algorithm) : 문자열 검색 알고리즘 (String search algorithm)

라빈-카프 알고리즘(Rabin-Karp Algorithm) : 문자열 검색 알고리즘 (String search algorithm)

라빈-카프 알고리즘(Rabin-Karp Algorithm) 은 문자열 검색 알고리즘으로, 해시(Hash) 를 사용하여 주어진 패턴을 텍스트 내에서 찾는 방식이며, 다중 패턴 매칭 문제에도 적합합니다.

알고리즘의 개요

1. 패턴과 텍스트의 부분 문자열에 대해 해시값 을 계산.
2. 해시값이 일치하면 실제 문자열을 비교하여 매칭 확인.
3. 해시값 비교로 대부분의 불필요한 비교를 피함.

시간 복잡도

• 평균: (n = 텍스트 길이, m = 패턴 길이)
• 최악: (해시 충돌이 많을 경우)

---

작동 방식 설명

1. 해시값 계산:

   • 패턴과 텍스트의 초기 윈도우에 대해 해시값 계산.
   • 해시는 아래와 같이 계산됩니다:
     [ ]

2. 슬라이딩 윈도우:

   • 텍스트의 다음 윈도우 해시값은 이전 해시값을 기반으로 빠르게 계산:

     [ \text{new_hash} = (\text{old_hash} - \text{첫 문자 값}) \cdot \text{base} + \text{새 문자 값} ]

3. 해시값 비교:

   • 해시값이 같으면 문자열을 직접 비교해 확인.

---

장점

• 단순 비교 방식보다 빠름(특히 다중 패턴 매칭에 유리).
• 해시값을 사용해 불필요한 비교를 줄임.

단점

• 해시 충돌이 발생할 경우 성능 저하 가능.
• 해시 함수와 소수 선택이 중요.

---

예제 코드 (Python)

python

class RabinKarp:
    def __init__(self, pattern, base=256, prime=101):
        self.pattern = pattern
        self.m = len(pattern)
        self.base = base  # 문자 집합 크기 (ASCII 기반)
        self.prime = prime  # 소수 (해시 충돌 방지)
        self.pattern_hash = self._compute_hash(pattern)  # 패턴 해시값
        self.h = pow(base, self.m - 1, prime)  # 윈도우 이동을 위한 가중치

    def _compute_hash(self, string):
        """ 문자열의 해시값 계산 """
        hash_value = 0
        for char in string:
            hash_value = (hash_value * self.base + ord(char)) % self.prime
        return hash_value

    def search(self, text):
        """ 텍스트에서 패턴을 검색하여 인덱스 반환 """
        n = len(text)
        m = self.m
        if n < m:
            return []

        result = []
        window_hash = self._compute_hash(text[:m])  # 첫 윈도우 해시값 계산

        for i in range(n - m + 1):
            # 해시값이 같으면 실제 문자열 비교
            if window_hash == self.pattern_hash:
                if text[i:i + m] == self.pattern:
                    result.append(i)

            # 다음 윈도우 해시값 업데이트
            if i < n - m:
                window_hash = (window_hash - ord(text[i]) * self.h) * self.base + ord(text[i + m])
                window_hash %= self.prime
                if window_hash < 0:
                    window_hash += self.prime  # 음수 방지

        return result

def main():
    """ 메인 함수 """
    text = "abracadabra"
    pattern = "abra"
    
    rk = RabinKarp(pattern)
    indices = rk.search(text)
    
    if indices:
        print(f"패턴 '{pattern}' 발견 위치: {indices}")
    else:
        print("패턴을 찾을 수 없음")


if __name__ == "__main__":
    main()

설명

1. RabinKarp 클래스

   • __init__: 패턴과 해시 관련 변수 초기화.
   • _compute_hash: 주어진 문자열의 해시값을 계산.
   • search: 슬라이딩 윈도우 방식으로 텍스트에서 패턴을 찾음.

2. main 함수

   • RabinKarp 객체를 생성하여 "abracadabra" 문자열에서 "abra"를 검색.
   • 발견된 인덱스를 리스트로 반환하고 출력.

출력

패턴 'abra' 발견 위치: [0, 7]

(즉, "abra"가 "abracadabra"에서 0번째와 7번째 인덱스에서 발견됨)

view raw Rabin-Karp Algorithm.ko.md hosted with ❤ by GitHub