문자열 해싱

String hash 함수

일반적인 자료구조로서의 해쉬, 그중에서도 문자열을 어떤 양의 정수값으로 변환하는 해시 함수이다.

(1) 좋은 해쉬함수의 조건

- Determinism : 같은 수를 넣을 경우 해시함수는 항상 같은 값을 리턴해야 함. 즉 외부상황에 따라 값이 달라지지 않고, 순수 내부 로직으로 작동

- Uniformity : input을 집어 넣었을 때, 어떤 output이 나오는 해시 함수가 있다고 하자.

 이 때 output range에 있는 각각의 값들이 나올 확률은 서로 대략적(roughly)으로 같아야 한다.

 이것은 해시의 충돌 확률을 낮추기 위해서다.

 충돌이 안 일어날 수록 좋은 해쉬 함수.

- 결과값이 Bucket Size를 넘지 않도록 범위를 조정할 것.

(2) String hash 함수의 알고리즘

일반적인 문자열 해시의 구현방법을 검색해 보았다.

그 결과 h = s[0]*k^(n-1) + s[1]*k^(n-2) ... 의 방식으로 구현한다.

또한 기존의 일부 string 해시함수 에서도 위 로직을 사용하고 있다.

왜 이런 형태로 구현할까? 이 구현 방식은 hashing에 사용하는 주요 알고리즘 중 하나인 Additive and Multiple Hashing이다.

이 방법은 해싱 처리할 대상 데이터를 순회하며, 데이터 요소 하나하나에 어떤 연산을 하고, 그 결과값을 초기 hash value에 더해 나간다.

데이터를 순회하면 hash value의 총 결과값이 완성되고 이것이 해쉬 코드가 된다.

문자열 해쉬 코드는, 각 문자의 배열 순서와 문자 요소의 값을 해쉬코드에 반영하여 하나의코드값을 만들어야 하므로, 위와 같은 알고리즘은 괜찮은 방법인 것 같다.

(3) h = s[0]*k^(n-1) + s[1]*k^(n-2) ...

이 알고리즘은 유사 난수(pseudo random number)를 발생시키는 수학 공식 중 하나인 lehmer의 multiplicative congruential algorithm과 형태가 닮았다.

k+1번째 난수 = {a*(k번째 난수) + c} mod N

이렇게 만들면 0~N의 범위 수에 대하여 난수 수열을 얻어낼 수 있다.

( a : 곱하는 상수, c : 더하는 상수, N : 최대 max 값.)

공식에서 a,c,N은 자기가 임의로 정하면 된다. 그러면 0~N 까지 난수 k의 수열을 얻을 수 있다.

 단 동일 범위에 대해 최대한 많은 난수를 뽑아내려면 어떤 세가지 조건을 만족해야 한다.

여기에서는 설명을 생략한다.

a와 N이 서로다른 소수라면 이 세가지 조건을 모두 만족한다고 한다.

위키에서 언급한 좋은 hash function의 요건과 위 수학공식을 비교해보니 적합하다는 생각이 들었다. 

좋은 해쉬함수의 요건 중 하나인 uniformity distribution 을 만족하기 때문이다. (정확한 수학적 원리는 생략한다)

또한 mod N 연산으로 0~N까지 확실한 범위에서 난수를 뽑아 주므로, 정해진 bucket index까지 수를 뽑기에도 좋다.

(4) 알고리즘 상수 정하기(a,c,N)

1. c는 문자열을 순회하며 만난 요소 (=한 문자)의 아스키 값으로 정했다. 

이에 따라 각 문자열을 해싱할 때, 구성하는 문자의 고유한 값이 반영될 것이다.

2.a는 처음에는 크게 상관없다고 생각했으나, 기존 코드 및 인터넷 검색을 해보니 대체로소수 (31) 을 사용하고 있었다. 

31 을 사용하는 이유는 32-1 , 즉 val을 bit-shift 5칸 한 것에서 val을 한 번 빼주면 되어서, 컴퓨터가 더 빠른 연산을 한다.

버킷 테이블의 개수인 N 또한, 소수로 만든다.

우린 1e9+9 를 사용할 것이다.

자 그럼 코딩 해보자.

 BOJ13713) 문자열과 쿼리

가장 긴 공통접미사를 비교하는 과정에서, 문자열 해싱을 통하여 비교연산을 O(1) 의 수행하였다.

#include <cstdio>
#include <algorithm>
#include <vector>
#include <iostream>
#include <string>
 
using namespace std;
typedef long long ll;
ll a = 31;
ll mod = 1e9+9;
 
 
 
string str2;
ll m;
ll tmp;
ll h[1001000];
ll len;
ll apow[1001000];
char str[1001000];
ll val(ll le,ll ri){
    ll ret = h[ri] - h[le-1]+mod;
    ret %= mod;
    return (ret*apow[le-1])%mod;
}
 
bool isequal(ll le,ll ri){
    return val(le,ri)==val(len -(ri-le) ,len);
}
 
ll func(ll pos){
    ll lo = 1;
    ll hi = pos;
    while(lo < hi){
        ll mid = (lo+hi)>>1;
        if(isequal(mid,pos)){
 
            hi = mid;
        }
        else{
            lo = mid+1;
        }
    }
    if(isequal(lo,pos))
         return pos-lo+1;
    return pos-lo;
}
int main(){
    freopen("input.txt","r",stdin);
    cin>>str2;
    len = str2.length();
    for(int i = 1; i <= len; i++){
        str[i] = str2[i-1];
    }
    
    scanf("%lld",&m);
 
    apow[0] = 1;
    for(ll i = 1 ; i <= len;i++){
        apow[i] = (apow[i-1]*a)%mod;
    }
 
    for(ll i =1 ; i <= len;i++){
        h[i] = (apow[len-i]*(str[i]-'a') +h[i-1])%mod;
    }
 
    for(ll i =0 ; i  < m ; i++){
        scanf("%lld",&tmp);
        printf("%lld\n",func(tmp));
    }
 
 
 
}