Rabin-Karp Algorithm
라빈-카프 알고리즘
* String Matching Algorithms (문자열 매칭 알고리즘) (URL)
- 전체 문자열 \(\texttt{string}\) 내에서 부분 문자열 \(\texttt{pattern}\)을 찾아내는데,
Hash Algorithm을 이용하여 \(\texttt{string}\)과 \(\texttt{pattern}\)의 해시값을 비교하는 방법이다.
Mechanism (원리)
1. 부분 문자열 \(\texttt{pattern}\)에 해당되는 수치값(해시값)을 계산한다.
- \(\texttt{pattern}\)을 구성하는 Alphabet Set을 \(\Sigma\) 라 하면,
\(\texttt{pattern}\)에 해당되는 해시값 \(\mathrm{hpat}\)은 \(|\Sigma|\)-진수로 표현된다.
- 특히, 아래와 같은 해시 함수를 Rabin Fingerprint라 한다.
* Rabin Fingerprint to Get Hash Value(\(\mathrm{hpat}\)) of Substring \(\texttt{pat[0...m-1]}\)
\(\mathrm{hpat =} (|\Sigma|^0 * \texttt{pat[m-1]}) + (|\Sigma|^1 * \texttt{pat[m-2]}) + |\Sigma|^2 * \texttt{pat[m-3]} + \cdots + |\Sigma|^{m-2} * \texttt{pat[1]} + |\Sigma|^{m-1} * \texttt{pat[0]}\)
* Advanced Form (using Nested Multiplication)
\(\mathrm{hpat =} \texttt{pat[m-1]} + |\Sigma| * (\texttt{pat[m-2]} + |\Sigma| * (\texttt{pat[m-3]} + |\Sigma| * (\cdots + |\Sigma| * \texttt{pat[0]})\cdots))\)
Example. 영어 대소문자로 구성되는 부분 문자열 \(\texttt{pat[0...9]}\)의 \(\mathrm{hpat}\)(해시값) 계산
- 영어 대소문자는 52개로 구성되어 있으므로, \(|\Sigma| = 52\)이다.
\(\mathrm{hpat =} (52^0 * \texttt{pat[9]}) + (52^1 * \texttt{pat[8]}) + (52^2 * \texttt{pat[7]}) + \cdots \\ + (52^i * \texttt{pat[9-i]}) + \cdots + (52^8 * \texttt{pat[1]}) + (52^9 * \texttt{pat[0]})\)
2. 전체 문자열 \(\texttt{string}\)에서 \(\texttt{pattern}\)의 길이만큼의 첫부분에 대한 수치값(해시값)을 계산한다.
- 즉, \(\texttt{string[0...m-1]}\)에 대한 \(\mathrm{hstr_0}\)(해시값)을 계산한다.
(여기서, \(\texttt{m}\)은 전체 문자열 \(\texttt{str}\)이 아닌, 부분 문자열 \(\texttt{pat}\)의 길이임에 유의하자.)
* Rabin Fingerprint to Get Hash Value(\(\mathrm{hstr_0}\)) of Substring \(\texttt{str[0...m-1]}\)
\(\mathrm{hstr_0 =} (|\Sigma|^0 * \texttt{str[m-1]}) + (|\Sigma|^1 * \texttt{str[m-2]}) + (|\Sigma|^2 * \texttt{str[m-3]}) + \cdots + (|\Sigma|^i * \texttt{str[m-i]}) + \cdots \\ + (|\Sigma|^{m-2} * \texttt{str[1]}) + (|\Sigma|^{m-1} * \texttt{str[0]})\)
Example. 영어 대소문자로 구성되는 전체 문자열 \(\texttt{str[0...n-1]}\)에서
부분 문자열 \(\texttt{pat[0...m-1]}\)에 처음으로 대응되는 \(\texttt{str[0...m-1]}\)의 \(\mathrm{hstr_0}\) (해시값) 계산
\(\mathrm{hstr_0 =} (52^0 * \texttt{str[9]}) + (52^1 * \texttt{str[8]}) + (52^2 * \texttt{str[7]}) + \cdots \\ + (52^i * \texttt{str[9-i]}) + \cdots + (52^8 * \texttt{str[1]}) + (52^9 * \texttt{str[0]})\)
3. \(\mathrm{hpat}\)값과 \(\mathrm{hstr_i}\)값을 비교하여 일치 여부를 확인한다.
4-1. \(\mathrm{hstr_i}\)와 \(\mathrm{hpat}\)이 일치하면 \(\texttt{str[i...i+m-1]}\)과 \(\texttt{pat[0...m-1]}\)를 직접 비교하여 정확히 일치하는지를 확인한다.
- 문자열은 다른데, 해시값만 같다고 하여 같은 문자열이라 판단하는 오류를 막기 위한 작업이다.
(즉, Hash Colision이 발생했을 경우를 대비하는 과정이다.)
4-2. \(\mathrm{hstr_{i}}\)이 \(\mathrm{hpat}\)과 일치하지 않는 경우, \(\mathrm{hstr_{i+1}}\)를 계산한다.
* Recurrence Formula of \(\mathrm{hstr_i}\) (Rolling Hash)
\(\mathrm{hstr_{i+1}} = |\Sigma| * (\mathrm{hstr_{i}} - |\Sigma|^{m-1} * \texttt{str[i]}) + \texttt{str[m+i]}\)
for \(\texttt{str[0...n-1] and pat[0...m-1]}, n >> m\)
※ Restriction
- Alphabet Set \(\Sigma\)의 크기 \(|\Sigma|\)와 Substring \(\texttt{pat}\)의 길이 \(m\)에 의해
해시값 \(\mathrm{hstr_i}\)가 매우 큰 수가 되면 컴퓨터 레지스터의 용량을 초과하여 Overflow 문제를 야기할 수 있다.
- 이에 대한 해결책으로, \(\texttt{str[i]}\)에 곱하는 \(|\Sigma|^k\) 대신, \(|\Sigma|^k\mathrm{ mod }P\) 를 곱하는 방법이 있다.
- 여기서, 상수 \(P\)는 컴퓨터 시스템이 감당가능한 범위 내(\(|\Sigma| * P\)를 감당할 수 있는 범위)에 있는 충분히 큰 Prime Number(소수)이다.
- 즉, \(\mathrm{hstr_0}\) 과 \(\mathrm{hpat}\)는 아래와 같이, \(P\) 이하의 값으로 나오게끔 다시 계산할 수 있다.
\(\mathrm{hstr_0 =} (|\Sigma|^0 \;\mathrm{mod}\; P * \texttt{str[m-1]}) + (|\Sigma|^1 \;\mathrm{mod}\; P * \texttt{str[m-2]}) + (|\Sigma|^2 \;\mathrm{mod}\; P * \texttt{str[m-3]}) + \cdots \\+ (|\Sigma|^i \;\mathrm{mod}\; P * \texttt{str[m-i]}) + \cdots + (|\Sigma|^{m-2} \;\mathrm{mod}\; P * \texttt{str[1]}) + (|\Sigma|^{m-1} \;\mathrm{mod}\; P * \texttt{str[0]})\)
\(\mathrm{hpat =} (|\Sigma|^0 \;\mathrm{mod}\; P * \texttt{pat[m-1]}) + (|\Sigma|^1 \;\mathrm{mod}\; P * \texttt{pat[m-2]}) + |\Sigma|^2 \;\mathrm{mod}\; P * \texttt{pat[m-3]} + \cdots \\+ |\Sigma|^{m-2} * \;\mathrm{mod}\; P * \texttt{pat[1]} + |\Sigma|^{m-1} * \;\mathrm{mod}\; P * \texttt{pat[0]}\)
- 또한, \(\mathrm{hstr_{i+1}}\)과 \(\mathrm{hstr_i}\) 사이의 Recurrence Formula는 아래와 같이 다시 쓸 수 있다.
\(\mathrm{hstr_{i+1}} = (|\Sigma| * (\mathrm{hstr_{i}} - (|\Sigma|^{m-1} \; \mathrm{ mod } \; P) * \texttt{str[i]}) + \texttt{str[m+i]}) \; \mathrm{ mod } \; P\)
(for \(\texttt{str[0...n-1] and pat[0...m-1]}\))
* \(\texttt{str[i...i+m-1]}\)과 \(\texttt{pat[0...m-1]}\)가 다른데도 \(\mathrm{hstr_i}\)과 \(\mathrm{hpat}\)가 같을 확률은 \({1 \over P}\)이다.
그러므로 소수 \(P\)를 충분히 크게 잡도록 하여 Colision을 줄이도록 하자.
Implementation
* GitHub (URL)
Performance
Worst Case Time Complexity: \(\Theta(n^2)\)
Average Time Complexity: \(\Theta(n+km)\)
(\(n\) is Length of String \(\texttt{str}\))
(\(m\) is Length of String \(\texttt{pat}\))
(\(k\) is # of Hash Value Matching Count)
Reference: 쉽게 배우는 알고리즘
(문병로 저, 한빛아카데미, 2018)
Reference: 모듈로 거듭제곱법
(Khan Academy, URL)
