라빈 카프
라빈 카프란?
라빈 카프(Rabin-Karp) 알고리즘은 특이한 문자열 매칭 알고리즘입니다. 항상 빠르지는 않지만 일반적인 경우 빠르게 작동하는 간단한 문자열 매칭 알고리즘이라는 점에서 자주 사용됩니다. 라빈 카프 알고리즘은 해시(Hash) 기법을 사용합니다. 해시는 일반적으로 긴 데이터를 그것을 상징하는 짧은 데이터로 바꾸어 주는 기법입니다. 상징하는 데이터로 바꾸어 처리한다는 점에서 단순 해시 알고리즘의 경우 연산 속도가 O(1)에 달한다는 엄청난 장점이 있습니다.
사실 해시(Hash)만 해도 굉장히 많은 숫자의 알고리즘이 있을 뿐만 아니라 각기 다르게 구현 될 수 있습니다. 하지만, 문자열 매칭은 ‘연속적인 문자열이 이어지는’ 경우에 기반하기 때문에 해시 또한 연속적인 경우에 더 빠르게 구할 수 있는 알고리즘을 채택하여 적용한다면 매우 빠르게 연산할 수 있습니다.
단순히 문자열을 비교하는 Native Search의 경우, 시간 복잡도가 O(NM)이 발생합니다. 하지만, 라빈 카프 알고리즘을 활용하면 평균 O(N)으로 시간 복잡도를 단축시킬 수 있습니다.
구현 방식
먼저 해시 계산법은 다음과 같습니다.
ABD의 해시 값은 65 3^2 + 66 3^1 + 68 * 3^0 = 851
예시를 통해서 살펴보겠습니다.
문자열 AABDCDABD에서 패턴 ABD에 발견되는지 라빈-카프 알고리즘을 통해 탐색해보겠습니다.
| 검색 대상 | A | A | B | D | C | D | A | B | D |
|---|---|---|---|---|---|---|---|---|---|
| 패턴 | A | B | D |
검색 대상 문자열 해시값(AAB) : 846
문자열 패턴 해시 값(ABD) : 851
두 해시 값이 다르므로 탐색에 실패합니다.
| 검색 대상 | A | A | B | D | C | D | A | B | D |
|---|---|---|---|---|---|---|---|---|---|
| 패턴 | A | B | D |
검색 대상 문자열 해시값(ABD) : 851
문자열 패턴 해시 값(ABD) : 851
두 해시 값이 같으므로 탐색에 성공합니다.
검색 대상 문자열의 해시 값이 구해지는 원리는 지정한 수 x (검색 대상 문자열 해시 값 - 맨 앞의 문자열 값 x 지정한 수^제곱 수) + 새로 탐색된 문자열 값입니다. 예를 들어 위 예시의 검색 대상 문자열에서 AAB의 해시 값은 846입니다. 탐색에 실패하여 한 칸 이동하여 ABD가 될때 해시 값은 3 x (846 - 65 x 32) + 68 = 851이 됩니다. 32를 곱하는 이유는 문자열 패턴의 길이가 3자리이므로 제곱 수가 2이기 때문입니다. 만약 문자열 패턴의 길이가 5자리라면 제곱 수는 4가 됩니다.
이러한 원리 때문에 라빈-카프 알고리즘은 문자열을 빠르게 탐색할 수 있는 알고리즘입니다.
물론 해시 값을 사용하기 때문에 다른 문자열인데도 같은 해시 값이 나오는 경우도 존재합니다. 이와 같은 현상을 충돌(Collision)현상이라고 합니다.
또한, 해시 값을 구하는 과정에서 문자열이 너무 길어서 자료형의 범위값을 넘어서는 경우도 존재합니다. 이와 같은 경우 MOD(모듈러 연산)을 활용합니다. 물론 MOD없이 진행하여도 동일한 간격으로 음수와 양수를 왔다갔다하므로 해시 값 자체는 동일합니다.
동작 순서
라빈-카프 알고리즘 동작 과정은 다음과 같습니다.
- 탐색 대상 문자열의 길이를 M, 패턴 문자열의 길이를 N이라고 합니다.
- 탐색 대상 문자열의 처음부터 패턴 문자열의 길이만큼 문자열을 잘라 해시 값을 계산합니다.
- 패턴 문자열의 해시 값을 계산합니다.
- 두 해시 값을 비교합니다. 만약 같다면 패턴 문자열이 탐색 대상 문자열에 존재하는 것으로 간주합니다.
- 만약 같지 않다면 탐색 대상 문자열에서 한 칸씩 이동하여 다시 해시 값을 계산하고 4번 과정을 반복합니다.
- 탐색 대상 문자열의 끝까지 탐색했는데도 패턴 문자열이 존재하지 않는다면 패턴 문자열이 탐색 대상 문자열에 존재하지 않는 것으로 간주합니다.
이렇게 해시 값을 사용하여 문자열을 비교하는 방식을 채택함으로써 일반적으로 문자열 매칭 알고리즘의 시간 복잡도를 개선할 수 있습니다.
특징
- Rolling Hash를 통해서 이전에 구했던 값을 재사용
- 해시값을 빨리 계산하기 위해 사용하는 해시 함수 Rabin fingerprint
코드
라빈-카프 알고리즘은 MOD연산을 사용하나, 안하냐에 따라서 두 가지 방식으로 코드가 짜진다.
MOD연산을 사용하지 않는 경우
public List<Integer> find(String parent, String pattern) {
int parentHash = 0, patternHash = 0, power = 1;
int parentLen = parent.length();
int patternLen = pattern.length();
// 패턴이 일치하는 위치를 저장할 리스트
List<Integer> idxList = new ArrayList<>();
for(int i = 0; i <= parentLen - patternLen; i++) {
if(i == 0) {
// 전체 문자열에 첫 파트의 Hash 코드 구하기, 패턴 문자열 Hash 코드 구하기
for(int j = 0; j < patternLen; j++){
// charAt안의 숫자는 둘 다 동일해야 하므로 patterLen을 써줘야 하는 것에 주의하자.
// 또한 오른쪽 숫자부터 왼쪽으로 power를 높게 적용해야 아랫식이 적용되므로 이 또한 유의하자.
parentHash = parentHash + parent.charAt(patternLen - 1 - j) * power;
patternHash = patternHash + pattern.charAt(patternLen - 1 - j) * power;
// power: 가장 앞에 있는 문자의 해시 값을 구할 때의 power 값으로 고정
if(j < patternLen - 1) {
power *= 2;
}
}
} else {
// 긴글 Hash 값 = 2 * (이전 파트 Hash 값 - 이전 파트에서 가장 앞에 있는 문자) + 새롭게 들어운 문자
parentHash = (parentHash - parent.charAt(i - 1) * power) * 2
+ parent.charAt(i + parentLen - 1);
}
// Hash 코드 일치
if(parentHash == patternHash) {
boolean found = true;
// 다시 한번 문자열이 맞는지 검사
for(int j = 0; j < patternLen; j++) {
if(parent.charAt(i + j) != pattern.charAt(j)) {
found = false;
break;
}
}
if(found) {
idxList.add(i + 1);
}
}
}
return idxList;
}MOD연산을 사용한 경우
List<Integer> findStringPattern(String parent, String pattern) {
final int MOD = 100000007;
List<Integer> idxList = new ArrayList<>();
int parentSize = parent.length();
int patternSize = pattern.length();
long parentHash = 0, patternHash = 0, power = 1;
for(int i = 0; i <= parentSize - patternSize; i++) {
if(i == 0) {
for(int j = 0; j < patternSize; j++) {
parentHash = (parentHash + (parent.charAt(patternSize - 1- j) * power)) % MOD;
patternHash = (patternHash + (pattern.charAt(patternSize - 1- j) * power)) % MOD;
if(j < patternSize - 1) {
power = (power * 31) % MOD;
}
}
} else {
parentHash = 31 * (parentHash - 31 * parent.charAt(i - 1) * power % MOD) + parent.charAt(i + patternSize - 1);
parentHash %= MOD;
}
if(parentHash == patternHash) {
boolean find = true;
for(int j = 0 ; j < patternSize; j++) {
if(parent.charAt(i + j) != pattern.charAt(j)) {
find = false;
break;
}
}
if(find) idxList.add(i + 1);
}
}
return idxList;
}시간 복잡도
참고한 사이트
