오늘은 라빈 카프 알고리즘을 배워 보겠습니다. 어떠한 문자열을 수 하나, 혹은 2개, 3개로 압축할 수 있다. 이것은 꽤 엄청납니다. 그렇게 하면, 사실 어떠한 문자열에서 다른 패턴을 찾는 거 또한, 상당히 빠르게 수행할 수 있습니다. 다만, 정확성이 문제라면 문제인데요.

 

 이 부분은 모듈러를 2개, 3개 이상 주는 식으로 해결합니다. 즉, 데이터가 강하지 않을 거라는 믿음을 가지고 수행을 하는 편입니다. 이 알고리즘을 잘 배워놓으면, 문자열 알고리즘을 모를 때, 조금이라도 건드려 볼 수 있습니다. 그러니 알아두시면 나름 좋습니다. 이 포스팅은 부분합 알고리즘을 이해했다는 전제 하에 쓰여졌습니다. 만약에, 그 부분에 대해서 이해를 하지 못하셨다면, 아래 포스팅을 먼저 보시고 오시는 것을 강력하게 권해드립니다.

 

 

[관련글]

전처리를 잘 하면 구간합을 빠르게 계산한다?

 

 


 1차원, 2차원인 경우만 다루겠습니다. 먼저 1차원은 string에서 pat을 찾는 그런 류에요. 먼저, 우리는 b진법과, 자릿수를 정의할 거에요. 길이가 3인 문자열 "abc"를 예로 들어보면 다음과 같이 코드값을 쓸 수 있습니다.

 

 

 

 이 때, b는 적당히 큰 소수로 처리합니다. 저는 그 중, 31로 처리를 해 볼 거에요. java의 hashCode도 내부적으로 이 b의 값을 31로 주기도 하고요. 문자의 자릿수는 아스키 코드 값으로 처리하는 경우가 많아요. 그런데 상식적으로 b를 31로 잡으면, 100만자리 문자열인 경우 31^100만을 어떻게 표현해야 할까요? 너무 큰 숫자입니다. 따라서, 이를 적절히 모듈러로 나누는데요. 10억 7, 10억 9 등으로 처리합니다.

 

 이 모듈러를 2개, 3개를 보아서 처리하면 틀릴 확률이 줄어들 거고요. 먼저 1차원인 경우를 봅시다.

 

 

 먼저, 0번째 문자는 'a', 1번째는 'b', 2번째는 'a', 3번째는 'c'입니다. b = 31이라고 하면, 다음과 같이 누적 배열을 채우기 위한 배열을 만들 수 있습니다.

 

 

 그러면, 여기서 우리는 "ba"라는 패턴이 있는지 검사하려고 합니다. 문자열을 쭉 훑으면서요. 어떻게 하면 좋을까요? 이미 문자열에 대한 누적 값을 채워두었으니, 부분 문자열을 압축한 값을 구해야 할 겁니다. 그런데, [2,3] 구간에 있는 문자열에서, 누적 배열을 통해서 얻어온 값이 31*'b' + 31^2*'a'입니다. 이는 "ba"의 hash 값인 'b' + 31*'a'와는 다른 값입니다.

 

 

 그러면 이러한 문제를 어떻게 해결하면 좋을까요? 다시 문제의 상황을 그림으로 그려 봅시다.

 

 

 nj[3]에서 nj[1]을 뺀 값이 'b'*31 + 'a' * 31^2입니다. 그런가요? 그런데 이것은, 실제 [2,3] 구간의 문자열인, "ba"의 hash 값에 31만큼이 곱해진 겁니다. 그러면 이것은 수식으로 다음과 같이 나타낼 수 있습니다. nj_v의 값을, 누적 배열을 통해서 구한, 다시 말해, 'b'*31 + 'a' * 31^2이라고 하면, 다음과 같은 관계식이 성립합니다.

 

31r = nj_v

 

 

그러면 실제 구간 [2,3]의 문자열의 해쉬값을 구하기 위해서, nj_v에 31을 나눠야 한다는 소리가 됩니다. 그리고 그 값을 패턴의 hash 값과 비교를 해야 할 거고요.

 

 

nj_v/31 == pattern_hash

 

 

 그런데 A/B = C라면 B*C = A입니다. 이것을 잘 이용하면, 위 수식은 아래와 같이 바꿀 수 있습니다.

 

 

nj_v == 31*pattern_hash

 

 

 우리는 나눗셈 없이, nj_v값을 통해서 부분 문자열이 패턴의 해쉬값과 같은지 비교할 수 있게 되었습니다. 그러면 이것을 조금 더 일반화 시켜 봅시다.

 

 

 이번에는 [4,5]구간에 있는 "cd"가 "ab"랑 같은지 검사하려고 합니다. 이 때에는 어떻게 하면 좋을까요?

 

 

 일단 [4,5] 구간에서의 합을 구하는 것이므로 nj[5]에서 nj[3]을 뺍니다. 그 값을 fake_v라고 합시다. 이것은 'c'*31^3 + 'd' * 31^4와 같습니다. 그런데, 실제로 "cd"의 hash는 'c' + 'd'*31입니다. 즉 fake_v는 real_v에 31^3만큼이 곱해진 겁니다. 그러면, 이 real_v가 "ab"의 h값과 같은지를 비교해야 하는데요. 이걸 수식으로 써 봅시다.

 

 

(real_v = fake_v/(31^3)) == h

 

 

 그러면 누적 배열을 통해서 구해진 fake_v의 값이 h*31^3과 같아야 한다는 것은 명백하게 알 수 있는 사실이에요. 이 두 값을 Mod로 나눴을 때 나머지 값이 같은지만 잘 비교해 주면 되겠죠?

 

 


 그러면 2차원 패턴에서 2차원 패턴을 찾는 문제는 어떻게 풀어야 할까요? 백준 10538번, 빅 픽쳐가 이것을 물어보는 문제입니다. 의도된 풀이는 해싱이 아니라, 아호 코라식이였을 거라 생각합니다. 그런데, 이것은 kmp 알고리즘에 Trie라는 자료구조를 끼얹는 구조이고, 저는 아직도 그 알고리즘을 잘 모릅니다. 그러면 어떻게 할 거냐. 간단합니다. 부분합 알고리즘을 응용하는 겁니다. 그런데, 약간 다른 점이 있습니다.

 

 

 먼저 n행 m열의 2차원 배열에서, value는 다음과 같이 적을 수 있습니다. 여기서 우리는 pattern의 크기가 2 by 2라고 해 봅시다. 즉 2행 2열인 셈입니다. (1,1)부터 (2,2)까지 잡아볼까요?

 

 

 누적 배열을 통해서 값을 구하면 'd'*31^(m+1) + 'c'*31^(m+2) + 'd'*31^(2m+1) + 'c'*31^(2m+2)가 뽑힐 겁니다. 다음에, (0,0)부터 (1,1)까지 2 by 2 배열을 뽑아 볼까요?

 

 

 보라색 부분의 합을 누적 배열을 통해서 뽑아 내면, 'a' + 'b'*31 + 'c'*31^m + 'd'*31^(m+1)이 될 겁니다. 뭔가 공통점이 보이실 건데요. (0,0)은 문자의 값에다가 31^0을 곱했습니다. (1,0)은 문자의 값에다가 31^m을 곱했어요. (0,1)은 문자의 값에다가 31^1을 곱했어요. (1,1)은 문자의 값에다가 31^(1+m)을 곱했어요. 그러면 find의 대상체가 n행 m열 배열이고, 타겟이 2 by 2라면, 패턴의 해시값을 어떻게 만들면 좋겠나요?

 

 

 요렇게 만들면 됩니다. init_zip은 그렇게 패턴을, 제가 말한 방식으로 압축을 하는 함수입니다.

 

 

 그러면 이렇게 압축을 했다면 어떻게 해야 할까요?

 

 

 보시면 (1,1)에서 (2,2)까지를 잡았을 때 부분 패턴을 보라색으로 칠했을 때, 보라색으로 칠한 부분의 합을 누적 배열을 통해서 구하면, 'd'*31^(m+1) + 'c'*31^(m+2) + 'd'*31^(2m+1) + 'c'*31^(2m+2)가 됩니다. 그런데 이것은 ["dc","dc"]의 실제 hash 값이 아닙니다. 이를 fake_v라고 합시다. ["dc","dc"]의 해쉬값은 이 값에 31^(m+1)을 나눠야 합니다. 그러면 real_v가 나옵니다.

 

 즉, 보라색 부분의 실제 hash 값은 fake_v/31^(m+1)이 되는데요. 패턴의 해쉬값에 31^(m+1)을 곱한 값이 fake_v와 같은지만 비교하면 된다는 것을 알 수 있어요. 그러면 nj 배열을 통해 구한 보라색 부분의 합에다가 31^(m+1)을 나눠야, ["dc","dc"]의 실제 hash가 나온다는 것을 어떻게 알 수 있을까요?

 

 

 그림으로 간단하게 도식화 시켜 보았습니다. 보면 원래는 31^0, 31^1, 31^m, 31^(m+1)로 이루어져 있던 것이 31^(m+1), 31^(m+2), 31^(2m+1), 31^(2m+2)로 평행 이동했다는 것을 알 수 있습니다. 즉, 밑으로 1칸, 오른쪽으로 1칸 이동을 했기 때문에, 실제로 real_hash 값에 곱해지는 값 또한 31^(m+1)만큼 곱해진 것입니다.

 

 

 즉, 시작 위치가 (1,1)이였기 때문에, nj에서 어떻게 잘 계산한 값은, 실제 압축된 값에 31^(m+1)만큼 곱해진 셈이 됩니다. 그러면, (x,y)에서 시작했다면요? m열이기 때문에, 실제 압축된 값에, 31^(mx+y)가 곱해질 겁니다.

 

 

 zip[s]는, h행 w열의 패턴을 압축한 값을, res[s]는 현재 (x,y)부터 r행 c열을 보았을 때, 그러니까 누적 값을 통해 구한 값입니다. 이 값에다가 31^(wx+y)를 나눠야 실제 h값이 나오고, 이것이랑 zip[s]가 같은지 비교하면 될 거에요. 그런가요? 역으로, zip[s]에 31^(wx+y)의 값과 무엇이랑 같으면 될까요? res[s]가 같으면 될 겁니다.

 

 이렇게, 어려운 문제를 라빈 카프 알고리즘으로 풀어보았습니다. 그냥 이것만 이용해서 풀어도 충분히 풀 만한 문제가 나옵니다. 물론 여기에 hash 자료구조를 이용해야 하는 문제도 종종 보이는 편이긴 합니다. 그렇지만 이것은 오늘 배운 것을 조금만 응용하면 그리 어렵지 않습니다. 그러니 이번에 배운 것만 잘 이해하셔도 좋을 듯 싶습니다.