[바미] Pattern matching algorithms - Rabin-Karp 알고리즘 구현하기

Rabin-Karp?

Rabin-Karp 알고리즘은 문자열 매칭 알고리즘 중 하나로, 주어진 문자열에서 패턴 문자열을 찾는데 사용되는데

문자열을 해시값으로 변환하여 패턴 문자열의 해시값과 일치하는 부분을 찾아내는 방법을 사용해요.

 

그럼 구현 해볼까요?

---

코드 구현

function RabinKarp(text, pattern) {
  const n = text.length;
  const m = pattern.length;
  const base = 26; // 사용할 기수
  const prime = 101; // 사용할 소수

  // 패턴 문자열과 전체 문자열의 해시값을 계산합니다.
  let patternHash = 0;
  let textHash = 0;
  let power = 1;

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

  for (let i = 0; i <= n - m; i++) {
    // 전체 문자열에서 패턴 문자열과 해시값이 일치하는 부분을 찾습니다.
    if (patternHash === textHash) {
      let found = true;
      for (let j = 0; j < m; j++) {
        // 문자열을 비교하여 일치하지 않으면 found 변수를 false로 변경합니다.
        if (text[i + j] !== pattern[j]) {
          found = false;
          break;
        }
      }
      // 패턴 문자열이 전체 문자열에 있는 경우 i를 반환합니다.
      if (found) {
        return i;
      }
    }
    // 다음 부분 문자열의 해시값을 계산합니다.
    textHash =
      ((textHash - text.charCodeAt(i) * power) * base +
        text.charCodeAt(i + m)) %
      prime;
    // 음수가 나올 경우, prime을 더해주어 양수로 변환합니다.
    if (textHash < 0) {
      textHash += prime;
    }
  }

  // 패턴 문자열을 찾지 못한 경우 -1을 반환합니다.
  return -1;
}

코드 설명

먼저, 패턴 문자열과 전체 문자열의 해시값을 계산해요. 해시값을 계산할 때는 base와 prime을 사용하는데

이 때, power는 base의 m-1승을 prime으로 나눈 나머지를 계산한 값이고, power는 다음 부분 문자열의 해시값을 계산할 때 사용되고 있어요.

그리고 전체 문자열에서 패턴 문자열과 해시값이 일치하는 부분을 찾게 되는데

비교하여 일치하는 경우

현재 윈도우에 있는 부분 문자열의 해시값과 패턴 문자열의 해시값이 일치하는 경우, 현재 윈도우에 있는 부분 문자열과 패턴 문자열이 일치하는지 비교해줘요.

if (textHash === patternHash) {
  // 현재 윈도우에 있는 부분 문자열과 패턴 문자열이 일치하는지 비교
  let isEqual = true;
  for (let j = 0; j < m; j++) {
    if (text[i - m + j] !== pattern[j]) {
      isEqual = false;
      break;
    }
  }
  if (isEqual) {
    return i - m; // 일치하는 시작 인덱스 반환
  }
}

일치하지 않는 경우 윈도우를 한 칸 이동하여 다시 검색을 진행하죠.

if (i < n - m) {
  textHash = recalculateHash(text, textHash, i, i + m);
}

일치하지 않는 경우

현재 윈도우에 있는 부분 문자열의 해시값과 패턴 문자열의 해시값이 일치하지 않는 경우, 윈도우를 한 칸 이동하여 

다시 검색을 진행하게 돼요.

if (i < n - m) {
  textHash = recalculateHash(text, textHash, i, i + m);
}

이와 같은 방식으로 문자열을 순회하며 패턴 문자열을 검색하고 있어요.

일치하는 경우 시작 인덱스를 반환하고, 검색을 실패한 경우 -1을 반환해주죠.