문자열 hashing function 빠르게 계산하는 방법

1. 왜 문자열의 hashing이 필요한가?

 

https://deepdata.tistory.com/960

문자열 해싱(hashing) 기본 개념 배우기

 

 

두 문자열 S1, S2가 서로 같은지 다른지 비교하고 싶을 때가 있다.

 

단순하게 S1, S2의 각 위치에서 서로 문자가 같은지 비교한다면 O(len(S1)) 정도 걸린다.

 

그런데 문자열의 길이가 매우 긴데, 문자열이 서로 같은지 다른지 자주 비교해야한다면 시간이 매우 오래걸릴 것이다.

 

여기서 문자열을 hashing해두면 두 정수가 서로 같은지 다른지만 비교하면 되므로,

 

두 문자열을 O(1)에 비교할 수 있게 만들어준다.

 

 

2. polynomial rolling hashing function

 

문자열 s = [s[0],s[1],s[2],...,s[n-1]]이라고 할 때, 어떤 정수 p,m에 대하여 polynomial rolling hashing function을 다음과 같이 정의했다.

 

 

 

 

여기서 s[i]는 문자 a,b,c,..,z에 대해 대응하는 수로 보통 1,2,3,...,26

 

 

3. hashing collision

 

만약 m으로 나눈 나머지를 취하는 것이 아니라 $\sum_{i = 0}^{n-1} s[i]*p^{i}$로 정의한다면,

 

p가 사용하는 문자의 개수 이상일 때 문자열에 따라 hash가 1:1 대응하고, 절대로 충돌이 발생하지 않는다.

 

----------------------------------------------------------------------------------------------------------

p = 2로 했을 때 충돌시키는 반례

abc

2 + 8 + 24 = 34

 

ccb

6 + 12 + 16 = 34 

------------------------------------------------------------------------------------------------------------

 

하지만 이렇게 정의하면 hash가 n이 커질수록 무한히 커지므로 m으로 나눈 나머지를 취해서 그 범위를 제한한다.

 

문자열의 조합은 무수히 많은데, hash(s)는 0~m-1로 고정되어있으므로 반드시 서로 다른 문자열이 동일한 hash를 가지는 경우가 있다.

 

이러한 hash 충돌을 피하기 위한 일반적인 전략이 있다.

 

1) p,m은 서로소로 정하는 것이 좋다.

2) p는 사용하는 문자의 종류 이상이 되는 소수로 정하는 것이 좋다.(26자라면 31)

 

3) m은 $10^{9}$ 이상의 소수를 선택하는 것이 좋다.(보통 $10^{9} + 9$)

 

 

4. polynomial rolling hashing function의 성질

 

hash function f(i)가 s[0,1,2,...,i]의 hash값으로 다음과 같이 정의한다면...

 

(당연히 m으로 나눠야하지만 m으로 나누는 것은 표기에서 생략함)

 

$$f(i) = s[0]p^{i} +  s[1]p^{i-1} + s[2]p^{i-2} + ... + s[i-1]p + s[i]$$

 

$f(i-1) = s[0]p^{i-1} + s[1]p^{i-2} + ... + s[i-1]$이므로,

 

$$f(i) = f(i-1)p + s[i]$$

 

이전의 hash값 f(i-1)을 알고 있다면, 현재 hash값은 f(i-1)에 p를 곱하고 현재 문자열의 hash s[i]를 더해주기만 하면 된다.

 

사실 p의 거듭제곱*s[i]를 누적합 해줘도 괜찮게 빠르긴 한듯

 

 

 

5. 부분문자열 s[l,...,r]의 hash

 

f(i) = f(i-1)p + s[i]이므로 모든 i = 1,2,3,..,n에 대하여 h[i] = hash(s[0,1,2,..,i])를 위와 같이 미리 구해놓는다.

 

 

만약 문자열 s의 [l,r] 구간의 부분문자열의 hash를 알고 싶다면?

 

$$h(r) = s[0]p^{r} + s[1]p^{r-1} + ... + s[l-1]p^{r-(l-1)} + s[l]p^{r-l} + ... + s[r]$$

 

$$h(l-1) = s[0]p^{l} + s[1]p^{l-1} + ... + s[l-1]$$

 

 

h(l-1)에 $p^{r-l+1}$을 곱하고 $h(r) - h(l-1)p^{r-l+1}$을 해준다면..?

 

$$s[l]p^{r-l} + ... + s[r] = hash(s[l,...r])$$

 

h[i]랑 p의 거듭제곱을 미리 구해놓는다면, 부분문자열의 hash를 $h(r) - h(l-1)p^{r-l+1}$로 O(1)에 구할 수 있다.