Rabin–Karp 알고리즘이란? Rolling Hash로 문자열 검색하기

Rabin–Karp는 Text 안에서 Pattern을 검색하는 대표적인 문자열 알고리즘입니다.

모든 위치에서 Pattern의 모든 문자를 직접 비교하는 대신 Pattern과 Text Window의 Hash를 비교합니다.

핵심은 다음과 같습니다.

Hash가 다르면 바로 Skip하고, Hash가 같을 때만 실제 문자를 확인한다.

Rolling Hash

현재 Window가:

ABC

이고 다음이:

BCD

라면 BCD 전체 Hash를 다시 계산할 필요가 없습니다.

A의 영향을 제거하고 D를 추가해 다음 Hash를 만들 수 있습니다.

이를 Rolling Hash라고 합니다.

Hash Collision

서로 다른 문자열이 같은 Hash를 가질 수 있습니다.

따라서:

Hash Match
↓
Exact Comparison
↓
Real Match / Collision

과정이 필요합니다.

Polynomial Hash

문자열을 다음과 같은 다항식 형태로 생각할 수 있습니다.

A × base² + B × base + C

그리고 Prime Modulo를 사용해 숫자의 크기를 제한합니다.

TypeScript 구현

function rabinKarp(
  text: string,
  pattern: string
): number {
  const n = text.length;
  const m = pattern.length;

  if (m === 0) return 0;
  if (m > n) return -1;

  const base = 256;
  const prime = 101;

  let patternHash = 0;
  let windowHash = 0;
  let highOrder = 1;

  for (let i = 0; i < m - 1; i++) {
    highOrder = (highOrder * base) % prime;
  }

  for (let i = 0; i < m; i++) {
    patternHash = (
      base * patternHash + pattern.charCodeAt(i)
    ) % prime;

    windowHash = (
      base * windowHash + text.charCodeAt(i)
    ) % prime;
  }

  for (let i = 0; i <= n - m; i++) {
    if (
      patternHash === windowHash &&
      text.slice(i, i + m) === pattern
    ) {
      return i;
    }

    if (i < n - m) {
      windowHash = (
        base * (
          windowHash -
          text.charCodeAt(i) * highOrder
        ) +
        text.charCodeAt(i + m)
      ) % prime;

      if (windowHash < 0) {
        windowHash += prime;
      }
    }
  }

  return -1;
}

복잡도

평균적인 경우:

O(n + m)

많은 Collision이 발생하는 최악의 경우:

O(n × m)

추가 공간은 기본 구현에서:

O(1)

입니다.

KMP와 비교

KMP는 Pattern의 Prefix/Suffix 구조와 LPS 배열을 사용합니다.

Rabin–Karp는 Hash와 Rolling Hash를 사용합니다.

KMP는 O(n + m)을 보장하지만 Rabin–Karp는 Collision이 많으면 Worst Case가 더 나빠질 수 있습니다.

여러 Pattern 검색

같은 길이의 Pattern이 여러 개 있다면 각 Pattern의 Hash를 Set에 저장할 수 있습니다.

각 Text Window의 Hash를 Set에서 검색하고 Candidate만 실제 비교하면 됩니다.

실제 활용

Rolling Hash 개념은 다음에 활용할 수 있습니다.

• 문자열 검색
• Duplicate Detection
• Plagiarism Detection
• Document Fingerprinting
• DNA Sequence Search
• Repeated Substring
• Substring Equality Queries

Double Hashing

서로 다른 두 Prime과 Hash를 함께 사용하면 Collision 가능성을 크게 줄일 수 있습니다.

흔한 실수

• Hash 값만으로 문자열이 같다고 판단하기.
• Window마다 Hash를 처음부터 계산하기.
• Modulo를 빼먹기.
• 적절하지 않은 Hash 파라미터 사용하기.
• Window에서 빠지는 문자의 Weight를 잘못 제거하기.

기술 면접

Rabin–Karp는 다음 개념을 동시에 확인할 수 있는 문제입니다.

• Hashing
• Sliding Window
• Modular Arithmetic
• String Matching
• Collision Handling

가장 중요한 부분은 Rolling Hash가 어떻게 업데이트되는지 이해하는 것입니다.

정리

Rabin–Karp의 구조는 다음과 같습니다.

Pattern Hash

Text Window
↓
Rolling Hash
↓
Compare
↓
Verify

가장 중요한 아이디어는 새 Window의 Hash를 처음부터 만들지 않고 이전 Window의 Hash에서 빠르게 계산하는 Rolling Hash입니다.