Monday, December 22, 2014

해싱(Hashing)

1. 개요

해싱(Hashing)은 긴 길이의 문자열이나 큰 크기의 값을 어떤 작은 값으로 치환하는 방법입니다. 특히 문자열 관련 문제에서 강력한 힘을 발휘하며, 매우 높은 정확도로 해싱한 값이 중복되지 않게 할 수 있기 때문에 효율적입니다. 보통 일반적인 시간복잡도에서 꽤나 큰 상수로 나눈 시간복잡도로 최적화시키기 때문에 실제 대회에서 많이 사용됩니다.

2. 기본 방법

1) 문자열을 정수값으로 치환하기

dad라는 단어가 있다고 생각합시다. 이 단어를 하나의 정수로 치환하려고 합니다. 기본적인 아이디어는 (문자의 종류) 진법으로 생각하여 정수로 치환하는 것입니다. 'a'는 0, 'b'는 1, … , 'z'는 25가 된다고 가정할 수 있습니다. dad는 3*(26^2)+0*(26^1)+3*(26^0)이 됩니다.
만약 문자열이 너무 길다면, 10글자씩 정도로 끊어서 저장할 수 있습니다. 아니면 전체 길이에 대해서 위의 방법대로 해싱을 하다가 큰 값(M)으로 나눈 나머지를 가지고 그 문자열의 해싱값으로 생각할 수 있겠습니다.
이 때, 한 M에 대해서 같은 값을 가지는, 서로 다른 문자열들이 생길까봐 걱정하실 수 있습니다. 그러면 서로 다른 큰 값 M1과 M2, … , Mk로 나눈 나머지들을 가지고 있다면 그 문제가 어느 정도 해결됩니다. 프로그램 수행시간은 k배 정도 증가하겠지만… 길 가다가 벼락 맞을 확률로, 해싱값들이 모두 일치하는데 정작 문자열은 다를 수 있겠다고 할 수 있겠습니다.
아! 참고로 M은 소수인 게 좋습니다. 왜냐하면 M으로 나누어 떨어진다면 해싱값이 0으로 되는 경우가 상대적으로 많기 때문입니다.

2) 정수값을 정수값으로 치환하기

정수를 정수로 치환하는 게 무슨말이냐 싶으시죠? 예제로 다음 문제를 가져와서 설명드려보겠습니다. 1920번 수 찾기 문제 이 문제의 정해는 A 배열의 원소들을 O(N log N)에 정렬하고 M개의 수들을 하나씩 이분탐색하는 것입니다. 하지만! 해싱으로 풀 수 있습니다.
우선 주어지는 정수들이 int 범위이기 때문에 적당히 1000007 정도로 해싱을 해봅시다. 음수인 경우는 나누었을 때의 나머지를 양수로 바꾸어주는 것에 주의합니다. A(i)의 해싱 값이 h(i)라면 어떤 vector <int>의 h(i)번째 방에 A(i)를 넣어줍니다. 이런 식으로 A[]들을 처리하고, M개의 수에 대해서 M(i) % 1000007한 값을 M`(i) 합시다. M`(i)번째 방의 원소들을 일일이 보면서 M(i)와 일치하는지 판별합니다. 확률적으로 vector <int>에 골고루 A(i)들이 들어갔다면 대략 O(N^2 / 1000007) 정도의 시간복잡도를 가질 것이며 실제로 이 방법으로 넉넉한 시간으로 Accepted를 받을 수 있습니다.

3. 응용 문제

1. 2014년 ACM-ICPC 한국 예선 G번

2014년 ACM-ICPC 한국 예선 G번 문제를 해싱으로 풀어보겠습니다.
참고로 이 문제의 정해는 Aho-Corasick 알고리즘을 사용하는 것입니다.
문제를 요약해보겠습니다. 각각 길이가 n과 m인 두 문자열 P와 Q가 주어집니다. Q를 3부분(각 부분은 크기가 0일 수도 있습니다.)으로 나누어서 가운데에 해당하는 부분은 뒤집어서 다시 순서대로 합한 문자열들의 집합을 S라고 하겠습니다.(예를 들어 Q가 AGCAT이고, A/GCA/T로 나누었다면 GCA를 뒤집으면 ACG가 됩니다. 이를 순서대로 합하면 AACGT가 됩니다.)
집합 S의 원소 중, P의 연속부분문자열과 일치하는 것의 개수를 출력하는 것이 문제에서 요구하는 것입니다.
이 문제를 해싱으로 풀기 위해서는, S 집합을 우선 구한 후에 그들을 Hashing Table에 저장해두고, P의 연속 부분 문자열 n-m+1개(이 집합을 T라 하겠습니다.)와 비교해보아야 할 것입니다.
전자의 경우는 위에서 설명한 방법을 쓰면 되고, 후자의 경우를 설명드리겠습니다. n이 10이고 P가 ACGGGTCAAG라고 합시다. 그리고 m은 3이라고 가정해봅시다. 그러면 ACG, CGG, … , AAG와 S의 원소들을 비교해야합니다. 그런데 T의 원소들을 O(n*m)에 해싱하면 TLE가 발생하게 됩니다. T의 원소들을 O(n)에 해싱할 수 있습니다. ACG에서 CGG로 넘어갈 때, CG는 유지되고 앞의 A는 빠지고, G가 삽입됩니다.
ACG에서의 해싱값을 x라 하면, (x - 0(='A'의 치환값) * 4(=문자의 종류 A,C,G,T)^(m-1))*4 + 2(='G'의 치환값)를 해주면 CGG의 해싱값이 나오게 됩니다. m은 불변값이므로 k*4^(m-1)(k는 0,1,2,3)을 사전에 계산해주었다면 O(n)에 이 작업들이 마무리 될 수 있게 됩니다.
아래는 제가 작성한 풀이입니다. 해싱값이 같다면 문자열들을 O(m^2)으로 일일이 비교해주었음에도 불구하고(?) 1.9초로 2초 내에 아슬아슬하게 AC를 받았습니다. Hash값 3개를 구한 후, 3개가 모두 같다면 같은 문자열이라고 판단한다면 훨씬 빨라질 수 있겠습니다.
아래의 소스는 해싱을 할 때 mod 연산을 쓰지 않았습니다. long long 범위를 넘어가면 자동으로 오버플로우 처리되어 mod 연산을 쓴 것과 같은 효과를 내는 것을 이용했습니다. 위의 소스가 1.8~1.9초의 수행시간을 보여주었지만, 아래의 소스는 1.06초의 수행시간을 보여줍니다. 확실히 더 빨라진 것을 알 수 있습니다. long long으로 해싱을 하면 mod 2^64와 같으므로, 2^64와 서로소인 수의 진법으로 해야 최소한의 안전을 보장할 수 있다고 합니다.

2. COCI 2006/2007 Contest #5 6번

COCI 2006/2007 Contest #5 6번 문제를 해싱으로 풀어보겠습니다.
길이가 20만 이하인 문자열이 주어졌을 때, 두 번 이상 등장한 부분 문자열 중 가장 길이가 긴 것의 길이를 구하는 문제입니다. 여기서 관찰할 수 있는 것은 어떤 부분 문자열 S가 k번 등장했다면, S의 부분 문자열 또한 k번 이상 등장한다는 사실입니다.
따라서 Parametric Search를 하면서 해싱을 이용하여 답이 존재하는지 확인할 수 있습니다. 제가 작성한 소스에는 해싱값을 3개 구하여서, 첫 번째 해싱값번째 vector에 페어로 저장하여 비교하는 방법이 사용되어 있습니다. g[i][j][k]는 i^j(i의 j 거듭제곱) mod Hash[k]입니다. 이웃한 부분 문자열로 넘어가면서 해싱값을 구할 때 사용됩니다

4. 실습 문제

1 comment: