라빈-카프 알고리즘
특이한 문자열 매칭 알고리즘이다.
항상 빠르지는 않지만 일반적인 경우 빠르게 작동하는 간단한 구조의 문자열 매칭 알고리즘이다.
📝 정의
문자열에 해싱 기법을 사용하여 해시 값으로 비교하는 알고리즘이다.
문자열의 해시 값을 비교하여 그 일치 여부를 검사하는 알고리즘이다는 것이다.
🛠 특징
앞서 말한대로 라빈-파크 알고리즘은 Hash 기법을 사용한다.
- Hash 기법
간단하게 해시 값을 만들려면 문자열의 각 문자(ASCII TABLE 값)에 특정 수의 제곱 수를 차례대로 곱하여 모두 더하면 된다.
이러한 방식을 사용하면 두 문자열이 서로 다를 때 두 문자열의 해시 값이 다르게 나오게 된다.
또한 Hash 는 상징하는 데이터로 바꾸어 처리한다는 점에서 단순 해시 알고리즘의 경우 연산 속도가 O(1) 에 달한다는 엄청난 장점이 존재한다.
사실 Hash 알고리즘은 굉장히 많은 숫자의 알고리즘이 있을 뿐만 아니라 각기 다르게 구현될 수 있다.
하지만 문자열 매칭은 '연속적인 문자열이 이어지는' 경우에 기반하기 때문에 Hash 알고리즘 또한 연속적인 경우에 더 빠르게 구할 수 있는 알고리즘을 채택하여 적용한다면 매우 빠르게 연산할 수 있다.
그리고 그 대표적인 예시가 라빈-카프 알고리즘이라는 것을 알면 된다.
예시
Hash 에 대하여 앞서 서술한 대로 각 문자의 아스키 코드 값에 2의 제솝수를 차례대로 곱하여 더해줌.
| 문자열 | abacaaba | abacaabb |
|---|---|---|
| 각 문자 | 97 * 2^7 + | 97 * 2^7 + |
| 98 * 2^6 + | 98 * 2^6 + | |
| 97 * 2^5 + | 97 * 2^5 + | |
| 99 * 2^4 + | 99 * 2^4 + | |
| 97 * 2^3 + | 97 * 2^3 + | |
| 97 * 2^2 + | 97 * 2^2 + | |
| 98 * 2^1 + | 98 * 2^1 + | |
| 97 * 2^0 + | 98 * 2^0 + | |
| 결과 | 24,833 | 24,834 |
이때 해쉬 값의 충돌 발생률은 굉장히 낮기 때문에 무시하고 넘어가지만 혹시 충돌이 발생하는 경우는 Chaining 혹은 Linear Probing 를 사용하여 해결한다.
즉, 라빈 카프 알고리즘은 여러 개의 문자열을 비교할 때 항상 해시 값을 구하여 비교하고, 해시 값은 거의 일치하는 일이 없기 때문에 'parent' 과 '부pattern'의 해시 값이 일치하는 경우에만 문자열을 재검사하여 정확히 일치하는지 확인하는 알고리즘이다.
⚙ 동작
- parent Hash: 24824
pattern Hash: 24833
2 parent Hash: 24913
pattern Hash: 24833
- parent Hash: 24833
pattern Hash: 24833
그럼 parent 의 개수 만큼 다시 계산하나? 당연 아니다.
parent 의 가장 앞의 수만큼 뺀 다음 뒤의 수만큼 더하면 된다.
이때 2를 곱해줘야하는데 2를 곱해줘야 parent 선택 대상 전체적으로 오른쪽으로 한 칸 욺직이기 때문이다.
int newParentHashValue = 2 * (parentHashValue - 나갈 문자의 수치 ) + 들어올 문자의 수치⏰시간 복잡도
이렇게 하면 O(N) 의 시간 복잡도를 갖게 된다.
💻 코드
public class RabinKarp {
public static void main(String[] args) {
rabinKarp("ababacabacaabacaaba", "abacaaba");
}
public static void rabinKarp(String parent, String pattern) {
int parentSize = parent.length();
int patternSize = pattern.length();
int parentHash = 0;
int patternHash = 0;
for (int i = 0; i <= parentSize - patternSize; i++) {
if (i == 0) {
for (int j = patternSize - 1; j >= 0; j--) {
parentHash += (int) (parent.charAt(j) * (Math.pow(2, patternSize - 1 - j)));
patternHash += (int) (pattern.charAt(j) * (Math.pow(2, patternSize - 1 - j)));
}
} else {
parentHash = (int) (2 * (parentHash - parent.charAt(i - 1) * (Math.pow(2, patternSize - 1))) + (parent.charAt(i + patternSize - 1)));
}
if (parentHash == patternHash) {
boolean found = true;
for (int j = 0; j < patternSize; j++) {
if (parent.charAt(i + j) != pattern.charAt(j)) {
found = false;
break;
}
}
if (found) {
System.out.println(i + 1 + "번 째에서 일치합니다.");
}
}
}
}
}참고로 간단하게 구현하였지만 정확하게 해시 값의 일치 여부를 검증하기 위해 나머지 연산(MOD)를 사용하는 경우가 많다.
하지만 일반적으로 Over Flow 가 발생해도 해시 값 자체는 동일하기 때문에 나머지 연산을 굳이 사용하지 않아도 된다.
왜냐하면 일반적인 CPU 의 경우 동일한 간격으로 음의 부호와 양의 부호를 왔다갔다 함으로 해시 값이 일치하는 것이다.
또 하지만 더 안정적인 프로그램을 작성해야하는 경우에는 MOD 를 입혀주는 것을 추천한다.
