개요

라빈 카프 알고리즘은 문자열을 빠르게 탐색하기 위해서 문자열을 수치로 변환하는 발상을 사용한다. 이번 글에서는 라빈 카프 알고리즘의 발상과 알고리즘의 수치화 과정에서 사용되는 메모리를 줄이기 위한 나머지 연산(Modular 연산)이 어떤 식으로 동작하는지 알아본다.

누가 알아보는가 하면 바로 글을 적는 필자가 공부를 하면서 알아본다는 말이 되겠다. 독자 여러분은 이 글에서 실수를 찾아내주신다면 주저 없이 메일을 보내주시길 바란다.

문자열의 수치화

문자열은 메모리에 저장된 그 모양 그대로 하나의 수라고 할 수 있다. 예를 들어서 ‘ABCDE’가 있다고 할 경우, 만약 A가 1이라고 한다면(0이라고 하면 직관적으로 와 닿지 않는다.) 이 수는 12345인 것이다. 이렇게 적으면 우리가 흔히 쓰는 10진수처럼 보이지만 만약 각 문자가 8비트라고 가정할 경우 이것은 256진수라고 가정할 수 있다.

문자열 윈도우의 수치화

앞서 예제로 보인 ‘ABCDE’에서 ‘ABC’부분은 123이라고 적을 수 있다. 편의상 이제부터는 10진수라고 생각하자. 윈도우라는 것은 긴 배열에서 정해진 길이의 구역만 보는 것을 말한다. 우리가 3칸 길이의 윈도우의 값만 본다고 하면 앞 부분 윈도우의 값을 그 바로 뒤 구역의 윈도우의 값을 알기 위해서 쓸 수 있지 않을까?

즉 ‘ABC’의 숫자값인 123을 알고 뒤에 있는 문자인 ‘D’의 값인 4도 안다면, ‘BCD’의 값도 알 수 있지 않을까? 물론 여러분은 쉽게 알 수 있을 것이다. 우선 A가 나타내는 값인 100을 123에서 뺀 후, 10을 곱한다. 그리고 4를 더한다. 이것을 수식으로 표현하자면 이렇게 보일 것이다.

\[10(123 - 100) + 4\]

만약 문자열 A가 있고 해당 문자열의 i번째 위치에서 구한 길이 M의 윈도우의 수치화 값을 \(V_i\)라고 한다면 \(V_i\)와 \(V_{i-1}\)의 관계는 이렇게 나타낼 수 있을 것이다. (10진수라고 가정하자.)

\[V_i = 10(V_{i-1}-A[i]*10^{M-1}) + A[i + M - 1]\]

당연히 위 수식에서 10을 임의의 진법을 나타내는 변수로 바꿀 수 있을 것이다.

수치화한 문자열 윈도우를 통한 문자열 탐색

만약 어떤 문자열 A가 있고 찾을 문자열 B가 있다고 하면 우리는 B의 수치화된 값을 계산한 후에 문자열 A에 대해서 B의 길이에 해당하는 윈도우를 계산한 후 그 윈도우를 문자열의 끝까지 이동시키면서 동일한 값을 가진 수를 찾아낼 수 있을 것이다. 이 아이디어는 실행 속도도 O(n)이어서 매우 좋아보인다. 그러나 계산해야 하는 수치가 최소한 찾을 문자열의 길이만큼은 커져야 한다는 문제가 생긴다. 큰 수는 기본적으로 컴퓨터가 처리할 수 있는 레지스터 크기를 넘어간다는 문제가 있고, 이 큰 수를 별도의 특수한 방식으로 처리하는 것은 하나의 수치값 비교로 문자열을 찾아낸다는 알고리즘의 기본 틀을 무너트리게 된다.

라빈 카프 알고리즘

문자열의 수치값을 어떤 특정한 값으로 나눈 나머지를 취해서 그 나머지값을 비교한다면 레지스터에 들어갈 작은 수로 수치값을 유지하면서 문자열을 탐색할 수 있을 것이라는 생각이 라빈 카프 알고리즘을 만든다.

문제는 문자열의 이전 부분의 나머지 값을 가지고 어떻게 현재 윈도우의 나머지 값을 계산할 수 있는가이다. 그것을 위해서 나머지 연산의 분배법칙이 필요하다.

나머지 연산의 분배법칙

나머지 연산에도 분배법칙이 성립한다. 다만 나눗셈에 대해서는 성립하지 않는다고 하는데, 그것은 나눗셈을 역수의 곱셈으로 바꾸면 된다고 한다. 아래와 같이 정리된다.

\[(A + B) \mathbin{mod} C = ((A \mathbin{mod} C) + (B \mathbin{mod} C)) \mathbin{mod} C\] \[(A - B) \mathbin{mod} C = ((A \mathbin{mod} C) - (B \mathbin{mod} C)) \mathbin{mod} C\] \[(A * B) \mathbin{mod} C = ((A \mathbin{mod} C) * (B \mathbin{mod} C)) \mathbin{mod} C\] \[(A \div B) \mathbin{mod} C = ((A \mathbin{mod} C) * ( \frac{1}{B} \mathbin{mod} C)) \mathbin{mod} C\]

이제 이 나머지 연산의 분배법칙으로 문자열의 나머지값 윈도우를 구하는 식을 만들어보자.

문자열 윈도우의 나머지 값 계산

문자열 ‘ABCD’가 있다고 하자. 이 문자열에서 3칸을 크기의 윈도우를 계산한다고 하자.

이제 ‘ABC’부분을 \(A\), ‘D’부분을 \(B\), ‘A’부분을 \(C\)라고 부르자. 이 문자열의 각 문자는 \(d\)진법으로 표현된다. 또 나머지를 구하기 위해서 나누는 제수를 q라고 부르자. 라빈 카프 알고리즘에서 고르는 \(q\)는 진법인 \(d\)에 비해서 훨씬 큰 소수이다. 이것은 뒤에 나오는 식을 정리할 때 중요하다. 윈도우의 길이는 \(m\)이라고 하자.

앞 3글자인 ‘ABC’는 편의상 이미 계산된 나머지값이 있다고 하자. 즉 \(A\mathbin{mod}q\)는 이미 알려진 값이다. 이 값은 \(H_{i-1}\)이라고 부르자.

우리가 새로 구할 나머지는 이렇게 적을 수 있다.

\[(dA + B - d^mC)\mathbin{mod}q = H_{i}\]

나머지 연산의 분배법칙을 써서 다시 적으면 이렇다.

\[\begin{align} &(dA \mathbin{mod} q + B\mathbin{mod}q - d^mC\mathbin{mod}q)\mathbin{mod}q\\ &=((d\mathbin{mod}q * A\mathbin{mod}q)\mathbin{mod}q + B\mathbin{mod}q - d^mC\mathbin{mod}q)\mathbin{mod}q \end{align}\]

\(d\mathbin{mod}q\)는 d가 q보다 작으므로 그냥 d가 되며, \(A\mathbin{mod}q\)는 \(H_{i-1}\) 으로 우리가 이미 알고 있는 값이다. 이후 수식 전개에서 \(C\)도 \(q\)에 비해서 작은 값이란 사실을 활용한다.

\[\begin{align} &=((dH_{i-1})\mathbin{mod}q + B\mathbin{mod}q - d^mC\mathbin{mod}q)\mathbin{mod}q\\ &=((dH_{i-1})\mathbin{mod}q + B\mathbin{mod}q - (d^m\mathbin{mod}q * C\mathbin{mod}q)\mathbin{mod}q)\mathbin{mod}q\\ &=((dH_{i-1})\mathbin{mod}q + B\mathbin{mod}q - (d^m\mathbin{mod}q\ C)\mathbin{mod}q)\mathbin{mod}q\\ &=((dH_{i-1}) + B - (d^m\mathbin{mod}q \ C))\mathbin{mod}q\\ &=(d(H_{i-1} - (d^{m-1}\mathbin{mod}q) \ C) + B)\mathbin{mod}q \end{align}\]

이렇게 정리하면 “쉽게 배우는 알고리즘(문병로 저)”의 403쪽에 나오는 식 12.4가 된다.

라빈 카프 알고리즘의 완성

위에 제시한 식을 통해서 수치값을 구하고 비교하면 그것이 라빈카프 알고리즘의 뼈대가 된다. 다만 수치값의 비교는 나머지 연산의 특성상 충돌이 생긴다. 그래서 수치값이 일치하더라도 거기에서 다시 한 번 간단한 문자열 비교로 직접 동일성을 확인해야 알고리즘이 완성된다. \(q\)를 큰 수로 잡아서 충돌 확률을 낮추면 라빈 카프 알고리즘은 Θ(n)의 시간이 소요된다.(“쉽게 배우는 알고리즘(문병로 저)” 405쪽)