라빈 카프 문자열 매칭 알고리즘(Rabin-Karp String Matching Algorithm)은 문자열 S가 있고 찾으려는 패턴 P가 있을때 S문자열에 패턴 P가 있는지 없는지 문자(char)를 하나씩 비교하는 방식이아닌 해싱된 값을 비교하는 방식을 사용한다.
해싱이 무엇인지 잘 모르면 우선 해시테이블(Hash Table) 자료구조를 선행학습해야 한다.
그럼 해싱함수는 무엇이고 어떤 절차로 해싱값을 서로 비교하면서 문자열에 패턴이 있는지 확인할수 있을까?
해싱으로 비교하는 방법은 매우 심플한데 문자열 S와 패턴 P가 아래처럼 있다고 했을 때
문자열(S) = "THISISATESTTEXT"
패턴(P) = "TEST"
P를 해싱한 Hp 값을 먼저 구하고 S문자열을 인덱스(i) = 0부터 순차적으로 증가하면서 패턴 P의 길이만큼 서브문자열을 해싱한 Hs 를 구한다.
예를들어 패턴을 해싱한 Hp = 80 이고 문자열 S에 대한 Hs들은 차례차례 해싱하면 다음과 같다고 가정하자
| 서브문자열 | Hs |
| THIS | 10 |
| HISI | 20 |
| ISIS | 30 |
| SISA | 40 |
| ISAT | 50 |
| SATE | 60 |
| ATES | 70 |
| TEST | 80 |
| ESTT | 90 |
| ..... | .... |
표를 보면 서브문자열 TEST의 Hs = 80 이는 패턴 P의 Hp와 일치하는 것을 알수 있다.
이렇게 해싱된 값을 비교하여 문자열에 패턴이 있는지 없는지 확인할수 있다.
위에 설명한 알고리즘의 의사코드와 과정이 그림1이다.
|
1
2
3
4
5
6
7
8
|
function RabinKarp(string s[1..n], string pattern[1..m])
hpattern := hash(pattern[1..m]);
for i from 1 to n-m+1
hs := hash(s[i..i+m-1])
if hs = hpattern
if s[i..i+m-1] = pattern[1..m]
return i
return not found
Colored by Color Scripter
|
[출처] https://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_algorithm
그렇다면 어떤 해싱함수를 사용하는걸까?
라빈 카프 알고리즘에서 해시 함수(hash function)은 rolling hash라는 것을 사용하는데 함수의 공식은 다음과 같다.
공식만 봐서 잘 이해가 안갈수 있으니패턴(P) = "TEST" 를 공식에 적용한 것으로 예를들어보자.
(=84) 괄호안의 숫자는 T, E, S, T 문자의 아스키(ascii)값이다.
2는 라빈카프알고리즘에서 radix 라 하는데 항상 고정되어 있는것은 아니고 문자열에 들어오는 문자의 종류 개수를 설정하면된다.
숫자만 쓴다면 0~9까지 10개니 10으로 하면되고 영어 소문자 알파벳만 들어온다면 26으로 만약 아스키코드가 다 들어올수 있는경우라면 256으로 하면된다. 왜 이렇게 하냐면 문자 종류보다 더 적은 숫자로 해버리면 해싱값이 충돌(collision)이 자주 발생할수 있기 때문이다.
하지만 충돌은 피할수 없기때문에 패턴과 문자열의 해싱값이 같은경우 이게 진짜로 같은 문자열인지 비교하는 단계가 필요하다.
따라서 위 의사코드에서 해시값이 같을때 if hs = hpattern 정말 문자열이 같은지 비교하는 if s[i..i+m-1] = pattern[1..m] 코드가 들어간 것이다.
여기까지 왔으면 라빈카프 문자열 알고리즘을 다 이해했다고 볼수 있으나 몇가지 문제점들이 남아 있다.
Q. [문제점1] 패턴 문자열이 길어지면 해싱함수의 다항식 차수(n-degree)가 늘어나게되서 (ex. 패턴길이가 100이면 99차수의 다항식 계산을해야한다) 계산량(덧셈, 곱셈) 이 많아질게 될텐데 이 것을 줄일 방법은 없을까 ?
A. 다항식을 계산할때 계산량을 줄여줄수 있는 방법이 있는데 호너의 법칙(Horner's method) 을 이용하면된다. 구현코드를 이해하려면 반드시 호너의 법칙을 선행학습해야한다.
Q. [문제점2] 패턴 문자열이 길어질수록 해시값을 integer, long으로 처리하기에 매우 큰 숫자가 나올수 있다. 어떻게 해야하나
A. 예를들어 해시값을 얻기위해 pow(A, B) 연산이 필수일텐데 문제는 B값이 클때가 문제이다.
안타깝게도 B가 그다지 크지 않은 값일 때조차도 pow(A, B)는 굉장히 커질수 있다.
2^90 = 1,237,940,039,290,000,000,000,000,000
7^256 = 2,213,595,400,050,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,00083,794,038,078,300,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000 721,264,246,243,000,000,000,000,000
이런 거대한 값은 계산기나 컴퓨터에서 오버플로우 오류를 발생시키게 된다.
따라서 모듈러(modular) 연산을 사용해야만 한다는 것이다.
그림 1은 호너의 법칙과 모듈러 연산을 사용하여 해시값을 계산하는 과정을 보여준다. 여기서 997이 mod 값으로 한것이다.
모듈려 연산을 위한 mod 값을 설정 할 때는 큰 소수(big prime number)를 구해서 사용하는 것이 효과적이다.
Q. [문제점3] 문자열의 해시값이 패턴과 같은지 확인하기위해 위에서 살펴본 것처럼 매번 패턴 문자열 길이만큼 Hash를 계산해주는 cost 가 든다.
지금까지 살펴본 방법으로 문자열 매칭을 한다면 문자 하나하나 비교했던 나이브 문자열 매칭 알고리즘 (Naive String match algorithm) 에 비해 성능상 크게 개선된것이라고 볼수 없다. 단지, 해싱값을 비교한것과 크게 차이나지 않는다.
그래서 어찌하면 해시 계산 량을 줄일수 있을까?? 고민고민하다가 아래와 같은 유도식이 나왔다.
즉, 다음 해시를 구하기위해 이전 해시에서 - 가장 앞에 문자를 계산했던 값을 빼고 + 마지막 문자 계산값을 더해주면 된다.
따라서 문자의 길이와 상관없이 최초로 구한 해시값만 있으면 항상 2개의 문자에만 접근하면 해시값을 쉽게 구할수 있게 된다.
그럼 구현을 해보자
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
|
import java.math.BigInteger;
public class RabinKarp {
private int radix; // radix
private long mod;
private String pat; // 찾을 문자열 패턴
private int patLen; // 패턴길이
private long patHash; // 패턴 해시값
private long RM; // R^(M-1) % Q
public RabinKarp(String pat) {
this.pat = pat;
// 아스키코드가 다 들어올수 있는경우라 256 으로 한다.
radix = 256;
patLen = pat.length();
// big prime number 를 생성
mod = longRandomPrime();
// 패턴의 해시값을 미리 계산한다.
patHash = hash(pat, patLen);
// 다음 해시값을 계산하기위해 미리 R^(m-1) % q 를 계산해둔다.
RM = 1;
for (int i = 1; i <= patLen-1; i++)
RM = (radix * RM) % mod;
}
private static long longRandomPrime() {
BigInteger prime = BigInteger.probablePrime(31, new Random());
return prime.longValue();
}
// 해시값을 구한다.
private long hash(String key, int m) {
long h = 0;
for (int j = 0; j < m; j++) {
// 호너의 법칙(Horner's method) 을 이용하여 다항식계산
// 결과값이 커질수 있으니 모듈러 연산을 해준다.
h = (radix * h + key.charAt(j)) % mod;
}
return h;
}
// 해시값이 같을때 충돌이 있을수 있으니 최종적으로 진짜 문자열이 같은지 확인용도.
private boolean check(String txt, int offset) {
for (int j = 0; j < patLen; j++)
if (pat.charAt(j) != txt.charAt(offset + j))
return false;
return true;
}
public int matching(String txt) {
// 패턴이 문자열보다 크면 문자열 맨 뒤를 리턴.
int n = txt.length();
if (n < patLen) {
return n;
}
// 최초로 패턴길이만큼 txt의 해시를 구해준다.
long txtHash = hash(txt, patLen);
// 해시값이 같은지 체크한다. 만약 같다면 해시 충돌이 있을수 있으니 정말 문자열이 동일한지 검사한다.
if ((patHash == txtHash) && check(txt, 0))
return 0;
for (int i = patLen; i < n; i++) {
// 이전해시에서 선행 숫자를 제거하고, 후행 숫자를 추가하고, 일치하는지 확인.
txtHash = (txtHash + mod - RM*txt.charAt(i-patLen) % mod) % mod;
txtHash = (txtHash*radix + txt.charAt(i)) % mod;
// or
/*
txtHash = (radix*(txtHash - txt.charAt(i-patLen)*RM) + txt.charAt(i))%mod;
// txtHash 가 음수가 나올수 있다. 양수로 변경
if (txtHash < 0)
txtHash = (txtHash + mod);
*/
int offset = i - patLen + 1;
if ((patHash == txtHash) && check(txt, offset))
return offset;
}
return n;
}
public static void main(String[] ars) {
String txt = "AAAAAAAAAAAAAAAAAAAAAAAAB";
String pat = "AAAAAAAB";
RabinKarp rabinKarp = new RabinKarp(pat);
int position = rabinKarp.matching(txt);
System.out.println(position);
}
}
Colored by Color Scripter
|
Rabin-Karp 알고리즘의 평균(average) 및 최고(best) 사례 실행 시간은 O (n + m)이지만 최악(worst)의 경우 시간은 O (nm)이다.
Rabin-Karp 알고리즘의 최악의 경우는 패턴과 텍스트의 모든 문자가 S []의 모든 부분 문자열의 해시 값이 P []의 해시 값과 일치 할 때
( 예를들어 P [] = "AAA"및 S [] = "AAAAAAA" ) 발생한다.
레퍼런스
'알고리즘(Algorithm) > 문자열' 카테고리의 다른 글
| 나이브 문자열 매칭 알고리즘 (Naive String match algorithm) (0) | 2019.07.16 |
|---|
