문자열 검색 알고리즘 : Rabin-Karp 알아보기
Rabin-Karp 알고리즘은 해시 함수를 사용하여 문자열을 검색하는 알고리즘입니다.
해시 함수를 사용하여 문자열을 숫자 값인 해시 값으로 변경합니다.
ex) hash("hello") = 5.
해시 값이 다르다면 두 문자열은 다르다는 것이 보장됩니다.
하지만 문자열이 달라도 해시 값이 같을 수 있습니다. 우리는 이것을 Spurious Hit라고 부릅니다.
Spurious Hit 때문에 해시 값이 같을 경우 추가로 문자열이 같은지 비교하는 작업이 필요합니다.
이 특징을 사용하여 Rabin-Karp 알고리즘은 패턴의 해시값을 텍스트의 부분 문자열의 해시 값과 일치하는지 비교하는 작업을 합니다.
따라서 Rabin-Karp 알고리즘은 다음 문자열에 대한 해시 값을 계산해야 합니다.
- 길이가 m인 패턴 자체
- 길이가 m인 텍스트의 모든 부분 문자열.
그림 예)
해시 값이 다르면 두 문자열이 다르다는 것을 보장합니다.
해시 값이 같아도 두 문자열은 다를 수 있습니다. 그렇기 때문에 해시 값이 같을 시 문자열 비교를 추가로 수행해 줍니다.
해시 값이 같고 문자열이 같다면 두 문자열은 같다는 것이 보장됩니다.
해시 함수
rabin fingerprint함수는 rabin-karp 알고리즘에서 주로 사용하는 해시함수이고 다음과 같은 형태를 띠고 있습니다.
$$ f(x) = m_0 + m_1x + ... + m_{n-1}x^{n-1} $$
- m = 대응하는 문자의 아스키코드 값
- x = Prime power(소수 거듭 제곱) , 보통 2를 많이 사용함.
- n = 문자열 길이
문자열 S에 대한 부분 문자열 S[i ... M-1]의 해시 값 H[i]를 구한다면 다음과 같이 표현할 수 있습니다.
$$ H[i] = S[i] * 2^{M-1} + S[i + 1] * 2^{M-2} + ... + S[i + M-2] * 2^1 + S[i + M - 1] * 2^0 $$
예)
S = "abcd" 의 해시 값 (각 알파벳의 아스키코드: a = 97, b = 98, c = 99, d = 100)
\( = 97 * 2^3 + 98 * 2^2 + 99 * 2^1 + 100 * 2^0 \)
긴 문자열을 계산할때 해시값이 표현 범위를 초과할 수 있습니다. 그렇기 때문에 해시 값에 나머지(modulo) 연산을 합니다.
H[i]% m (m은 소수 값)
rabin-karp 알고리즘의 성능은 해시함수 성능에 가장 큰 영향을 받습니다.
그렇기 때문에 효율적인 해시함수를 사용하는 것이 핵심입니다.
rolling hash
각 위치에서 해시 함수를 처음부터 다시 계산하는 것은 너무 느립니다. 그렇기 때문에 rolling hash를 사용합니다.
rolling hash는 window 사이즈만큼 이동하면서 입력을 받아 해시값을 구합니다.
rolling hash를 통해 사용했던 결과를 재사용해서 해시 값을 빠르게 계산할 수 있습니다. (메모라이즈 기법 사용)
예)
txt[0...2]의 해시 값 H[0]을 구합니다.
txt[1...3]의 해시 값 H[1]을 구할 때 이전 단계에서 계산한 값들을 재사용한다면 S[3]의 값만 추가하면 됩니다.
(각 문자마다 계산할 필요 없음)
문자열 길이가 n인 해시값 H[0]을 구하는데 O(n)의 시간이 걸리지만 그 이후부터는 재사용을 하기 때문에 O(1)에 시간이 걸리게 됩니다.
rabin fingerprint 함수에 rolling hash를 적용하면 다음 부분 문자열에 대한 해시값을 구하는 공식을 유도할 수 있습니다.
구현
전처리 단계
다음 문자열에 대한 초기 해시 값(H[0])을 구합니다.
- 길이가 m인 패턴 - pattern[0 ... m-1]
- 길이가 m인 텍스트의 첫 번째 부분 문자열 - text[0 ... m-1]
문자열 검색 단계
- text 0 ~ n-m+1까지 이동하며 부분 문자열에 대한 해시 값(t)과 패턴의 해시값(p)을 비교합니다.
- 해시 값이 같을 경우(t==p) 패턴과 부분 문자열을 비교하고 두 문자열이 같다면 찾은 위치를 출력합니다.
- 다음 부분 문자열에 대한 해시값을 구하는 공식은 다음과 같습니다.
t = d(t - text[i] * h) + text[i + m]
- t = text의 해시값
- h = d^(m-1)
- d = a prime power (=2)
- m = 패턴 길이
- 해시 값이나 h값을 계산할 때 정수 범위를 초과할 수 있기 때문에 나머지 연산을 추가해 줍니다.
/*
- p = 패턴의 해시 값
- t = text 의 해시 값
- m = 패턴 길이
- d = a prime power
- q = 모듈러 연산을 위한 소수
- h = d^(m-1)
*/
#define d 2;
#define q 101;
void rabinKarp(char pattern[], char text[]) {
int m = strlen(pattern);
int n = strlen(text);
int i, j;
int p = 0;
int t = 0;
int h = 1;
// d^(m-1) 값을 h에 대입.
for (i = 0; i < m - 1; i++)
h = (h * d) % q;
// 전처리 단계 : 패턴과 텍스트의 첫번째 부분 문자열의 해시값을 구함.
for (i = 0; i < m; i++) {
p = (d * p + pattern[i]) % q;
t = (d * t + text[i]) % q;
}
// 문자열 검색 단계
for (i = 0; i <= n - m; i++) {
if (p == t) {
// 해시 값이 같다면 두 문자열을 하나하나 비교함.
for (j = 0; j < m; j++) {
if (text[i + j] != pattern[j])
break;
}
// 해시값이 같고 두 문자열이 같다면 패턴을 찾음.
if (j == m)
printf("Found pattern at index %d \n", i);
}
// 다음 부분 문자열에 대한 해시값을 구함.
if (i < n - m) {
t = (d * (t - text[i] * h) + text[i + m]) % q;
if (t < 0) // 해시값이 음수라면 양수로 변경해 줌.
t = (t + q);
}
}
}Input & Output
Input:
txt[] = "BCAABAABAACD"
pat[] = "AABAAC"
Output:
Found pattern at index 5성능
pattern의 길이를 M, text의 길이를 N이라고 가정하겠습니다.
best case & average case
- 전처리 단계의 시간 복잡도는 O(M)이고 문자열 검색 단계의 시간 복잡도는 O(N)이기 때문에 시간 복잡도는 O(M+N)입니다.
worst case
- 모든 부분 문자열에서 Spurious Hit가 발생한다면 시간 복잡도는 O(MN)입니다.
