Rabin-Karp 알고리즘

KMP 알고리즘에 이어서 O(n + m)의 시간 복잡도로 문자열 검색을 할 수 있는 알고리즘인 Rabin-Karp 알고리즘에 대해서 알아보겠다.

라빈 카프 알고리즘은 해시(Hash) 기법을 사용하여 문자열에서 특정 패턴과 일치하는지 찾는 알고리즘이다.

여기서 해시 기법이란, 일반적으로 긴 데이터를 상징하는 짧은 데이터인 해시 값으로 바꾸어주는 기법이다. 이때 해시 값을 구하는 연산 속도는 O(1)이기 때문에 시간 소모가 적다.

라빈 카프 알고리즘은 찾고 싶은 문자열, 탐색 문자열을 해시 값으로 변환 후, 원본 문자열을 순회하며 특정 패턴과 해시 값이 일치하는지를 확인한다.

단, 해시 값이 같다고 무조건 같은 패턴인 것은 아니다. (그럴 확률은 적지만) 만약 해시 값이 같은 경우, 문자열의 값과 패턴의 값을 일대일로 비교하는 과정도 필요하다.

해시 값 생성

abaeabcaaba의 해시 값을 구해보겠다.

abaeabcaaba의 해시 값은 49761이다.

위에서 볼 수 있듯이, 해시 값은 각 문자의 아스키 코드 값에 2의 제곱수를 차례대로 곱하여 더해 준 것이다.

해시 값 업데이트

해시 값을 생성하는데 O(n)의 시간이 걸린다. 만약 해시 값을 매번 O(n)의 시간으로 생성해야 한다면, Rabin-Karp 알고리즘을 굳이 사용할 이유가 없다. 그래서 이 알고리즘에서 O(1)의 시간으로 해시 값을 업데이트하는데, 그 방법은 다음과 같다.

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

예를 들어서 문자열 AABABD에서 길이가 3인 문자열 패턴을 찾는 중이다. 가장 처음 검색할 부분은 AAB다. 이때 해시 값은 $A × 2^2 + A × 2^1 + B × 2^0$다. 만약 AAB가 패턴과 일치하지 않는다면 한 칸 움직여서 ABA를 구해야 한다. ABA의 해시 값은 다음과 같다.

$2 × (A × 2^2 + A × 2^1 + B × 2^0 - A × 2^2) + A × 2^0$

가장 먼저 기존 해시 값에서 A의 해시 값을 빼면 AB의 해시 값$(A × 2^1 + B × 2^0)$이 된다. 해당 해시값에 $2$를 곱하면 $A × 2^2 + B × 2^1$이 되고 여기에 A의 해시 값인 $A × 2^0$을 넣으면 새로운 해시 값은 $A × 2^2 + B × 2^1 + A × 2^0$이 된다.

알고리즘 원리

원본 문자열 AABABDACABC에서 ABC를 Rabin-Karp 알고리즘을 통해 탐색해 보겠다.

원본 문자열 해시 값: 680
탐색 문자열 해시 값: 683

두 해시 값이 다르므로 탐색에 실패한다.

원본 문자열 해시 값: 681
탐색 문자열 해시 값: 683

두 해시 값이 다르므로 탐색에 실패한다.

원본 문자열 해시 값: 684
탐색 문자열 해시 값: 683

두 해시 값이 다르므로 탐색에 실패한다.

원본 문자열 해시 값: 684
탐색 문자열 해시 값: 683

두 해시 값이 다르므로 탐색에 실패한다.

원본 문자열 해시 값: 689
탐색 문자열 해시 값: 683

두 해시 값이 다르므로 탐색에 실패한다.

원본 문자열 해시 값: 693
탐색 문자열 해시 값: 683

두 해시 값이 다르므로 탐색에 실패한다.

원본 문자열 해시 값: 683
탐색 문자열 해시 값: 683

두 해시 값은 같은데 문자열은 ACA와 ABC임으로 서로 불일치한다.
만약 해시 값이 서로 일치하면 문자열 값과 패턴 값을 비교해서 완전히 일치하는지 확인한다.
이때 ACA와 ABC는 일치하지 않기 때문에 탐색에 실패한다.

원본 문자열 해시 값: 688
탐색 문자열 해시 값: 683

두 해시 값이 다르므로 탐색에 실패한다.

원본 문자열 해시 값: 683
탐색 문자열 해시 값: 683

두 해시 값이 같고 문자열도 서로 같으므로 탐색에 성공한다.

예시 코드

const hash = function (string, length) {
  let hashValue = 0;
  let power = 1;

  for (let i = length - 1; i >= 0; i -= 1) {
    hashValue += string[i].charCodeAt(0) * power;
    power *= 2;
  }

  return hashValue;
};

const search = function (string, pattern) {
  if (string.length < pattern.length) return -1;
  if (!pattern.length) return 0;

  const power = 2 ** (pattern.length - 1);
  const patternHashValue = hash(pattern, pattern.length);
  let stringHash = hash(string, pattern.length);

  for (let i = 0; i <= string.length - pattern.length; i += 1) {
    if (i !== 0) {
      const removeValue = string[i - 1].charCodeAt(0) * power; // 맨 앞
      const newValue = string[i - 1 + pattern.length].charCodeAt(0); // 맨 뒤
      stringHash = 2 * (stringHash - removeValue) + newValue;
    }

    if (stringHash === patternHashValue) {
      let find = true;

      for (let j = 0; j < pattern.length; j += 1) {
        if (string.charAt(i + j) !== pattern.charAt(j)) {
          find = false;
          break;
        }
      }

      if (find) return i;
    }
  }

  return -1;
};