다항식 기반 롤링 해시, 직접 만들어 써보기

어떤 집합에서 결합법칙을 만족하는 이항연산 $+$와 역연산 $-$가 있고, $f(x + y) = f(x) + f(y)$를 만족하는 함수 $f$가 있을 때, $f^n(x)$를 빠르게 계산할 수 있다면 길이 $N$의 문자열 $S$에 대해 $h = \sum_{k=1}^{N}{f^{N-k}(S[k])}$를 롤링 해시로 활용할 수 있다.

$f(h) + S[N + 1]$로 뒤에 문자를 추가할 수 있고, $h - f^{N-1}(S[1])$로 앞에서 문자를 삭제할 수 있다. 당연히 중간에서 삭제 및 대체도 가능하지만, 앞뒤 추가 및 삭제에 비해 거의 안 쓰이는 편이다.

예시

위키피디아의 롤링 해시 문서에선 다음 두 가지 다항식 기반 롤링 해시를 소개한다.

다항식 롤링 해시

적당한 상수 $p$, $q$가 있을 때, modulo $p$에서 $f(x) = qx$인 경우다.
Rabin fingerprint랑은 다르다고 하는데, 비슷하게 생겨서 다들 이걸 Rabin fingerprint, Rabin-Karp 알고리즘이라고 부른다. 근데 솔직히 중요한 사항은 아닌 것 같다.

롤링 해시라고 하면 십중팔구는 이를 가리키고, 그만큼 상당히 안정적인 품질을 보여준다.
허나 $p$를 $2^w$로 잡으면 적대적 입력에 매우 취약하다. $p$를 소수로 잡고 약간의 처리 시 꽤 완화 가능하나 속도와 구현 면에서 복잡성이 있다.

Cyclic Polynomial (Buzhash)

사용할 자료형의 비트수 $w$에 대해, $[0, 2^w)$에서 덧셈이 XOR, $f$가 ROTL(비트 왼쪽 회전)인 경우다.

$w < N$이 되는 순간, 처음 문자가 한 바퀴를 완전히 돌게 돼 품질이 급격히 나빠지는 단점이 있어 $N$이 작은 경우에만 사용 가능하다.

해시 함수 직접 만들어 쓰기

원래는 덧셈과 뺄셈 기반의 해시를 변형해 쓰려 했으나, 수학적 지식이 부족해 곱셈 말곤 분배법칙을 만족하는 괜찮은 연산을 찾지 못했다. modulo 기반인데다 $p$, $q$같은 상수 정하기 까다로운 게 썩 마음에 안 들기도 하고...

덧셈과 뺄셈 대신 XOR을 쓰는 경우, 고정된 순열 $P$를 적당히 잡고 해당 순서대로 비트를 섞는 연산을 $f$로 쓸 수 있다. Cyclic Polynomial 해시의 ROTL도 이에 속하는데, 주기가 $w$로 너무 짧은 게 문제였다.

순열의 주기는 사이클에 의존한다. 조금 고민해보면 각 사이클 길이의 $\mathrm{lcm}$임을 알 수 있다. 비트 회전은 사이클이 그냥 한 덩어리라 주기가 극히 짧았던 것...
$\mathrm{lcm}$ 값을 키우려면 사이클을 소수 기준으로 쪼개야 한다. 이렇게 해서 만들 수 있는 최댓값은 OEIS에 나열되어 있는데, 길이 64에선 주기가 최대 $2^3 \times 3 \times 5 \times 7 \times 11 \times 13 \times 17 = 2042040$인 것을 볼 수 있다. 아주 크진 않지만, 기존보단 훨씬 큰 것을 알 수 있다.
또한 주기와 별도로, 사이클의 개수는 대략 $O(\sqrt{w})$ 혹은 그보다 작은 것으로 보인다.

구현

어떻게 쪼개야 주기가 최대가 되는진 알았으니, 실제 순열을 만들어야 한다. 가장 간단하게는 다음과 같이 할 수 있다.

1 2 3 4 5 6 7 0 9 10 8 12 13 14 15 11 17 18 19 20 21 22 16 24 25 26 27 28 29 30 31 32 33 23 35 36 37 38 39 40 41 42 43 44 45 46 34 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 47

이는 우선 x & 0x7FFFBFFDFFBF7B7F으로 왼쪽으로 한 칸 보낼 비트들을 추출한 뒤 << 1을 해주고, 나머지 0x8000400200408480에 포함되는 비트들을 각각 0x800400810901로 보내줘야 한다.
전자는 쉽지만, 후자를 효율적으로 처리하려면 인텔 BMI2 명령어셋의 PEXT와 PDEP 연산이 필요하다. 이를 활용한 구현은 다음과 같다.

using ull = unsigned long long;
const ull SHR = 0x8000400200408480, SHL = SHR << 1 | SHR >> 63;
ull shl(ull x) { return _pdep_u64(_pext_u64(x, SHR), SHL) | (x & ~SHR) << 1; }

이제 $f^n(x)$, 그러니까 순열을 $n$번 적용한 값을 구해야 한다. 조금 느린 걸 감수하고 각 사이클을 독립적으로 고려하면, 그냥 mod 사이클 길이를 한 다음 해당 비트를 뽑아서 잘 ROTL해주면 된다. 이를 단순하게 구현하면 다음과 같다.

template<ull m, ull k> ull rotl(ull x, ull n) {
    ull constexpr t = (1ULL << m) - 1 << k;
    x &= t; n %= m;
    return (x << n | x >> m - n) & t;
}

ull shl(ull x, ull n) {
    return rotl<8, 0>(x, n) | rotl<3, 8>(x, n) | rotl<5, 11>(x, n) | rotl<7, 16>(x, n)
        | rotl<11, 23>(x, n) | rotl<13, 34>(x, n) | rotl<17, 47>(x, n);
}

이제 비트 회전에 PEXT와 PDEP를 적용해보자. 이번엔 첫 shl 함수 구현과는 달리 단일 시프트로 ROTL을 처리할 수 없다. 때문에 ROTL에 한 번, ROTR에 한 번 해서 각 연산을 두 번씩 쓰게 된다.
하지만 이 최적화를 해도 PEXT와 PDEP에 넣을 mask 처리가 굉장히 까다로워 실질적인 이득은 크지 않다.

그렇다면 mask를 n에 대해 전처리해두는 건 어떨까? 이 경우 직전인 n - 1일 때의 결과를 활용 가능해서, modulo 연산이 필요치 않다. 코드로 보면 다음과 같다.

ull shr(ull x) { return _pdep_u64(_pext_u64(x, SHL), SHR) | (x & ~SHL) >> 1; }
ull shl(ull x, ull n) {
    static std::vector<std::pair<ull, ull>> P = { {} };
    while(P.size() <= n) {
        auto [ a, b ] = P.back();
        P.push_back({ shr(a) ^ SHR, shl(b) ^ SHL });
    }
    auto [ a, b ] = P[n];
    return _pdep_u64(_pext_u64(x, a), b) | _pdep_u64(_pext_u64(x, ~a), ~b);
}

사실 그리 완전히 최적화된 구현은 아니라, 이를 그대로 적용하면 성능 향상이 미미하다. 그냥 예시로 봐주길 바라며, 내가 실제로 사용하는 코드는 글 끝에 첨부해두었다.

ARM

안타깝게도, 내 노트북 M1 맥북에선 이 코드가 돌아가지 않는다. BMI2 명령어셋이 없어 PEXT와 PDEP 연산이 돌아가지 않기 때문이다. 때문에 테스트해보려면 다음과 같은 코드를 작성해야 한다. (물론 매우 느리다!)

ull _pext_u64(ull x, ull m) {
    ull n=0, y=0;
    for(ull i=0; i<64; i++) if(m>>i&1) y|=(x>>i&1)<<n++;
    return y;
}
ull _pdep_u64(ull x, ull m) {
    ull n=0, y=0;
    for(ull i=0; i<64; i++) if(m>>i&1) y|=(x>>n++&1)<<i;
    return y;
}

최종 코드

https://gist.github.com/cgiosy/63757207a235095821ef9fb61fd4df3a

성능

단순 문자열 검색의 경우, $N = 10^6$ 정도에서 KMP보다 조금 느린 속도를 보여준다.
특이하게도 전처리를 할 경우, 별 차이가 없거나 기존보다 미세하게 느렸다. shl을 $O(N)$번만 호출해서 그런 듯하다.

해싱 + LCP 비교 기반 문자열 정렬은 문자열 길이의 합이 $M$일 때, 대략 $O(N \lg N \lg {\frac{M}{N}})$이 시간이 소요된다. 정렬에 기본적으로 $O(N \lg N)$이 소모되고, 각 비교 연산마다 LCP 계산이 필요하다. LCP는 이분탐색을 사용해 $O(\lg \min(|X|, |Y|))$에 구할 수 있고, 이를 정렬에 적용 시 해당 시간복잡도가 나온다.
즉 $M = O(N)$이면 $O(N \lg N)$, $M = O(N^2)$ 정도면 $O(N \lg^2 N)$이 됨을 알 수 있다.

접미사 배열 계산의 경우 $O(N \lg^2 N)$이며, 실성능 테스트 시 기존 접미사 배열 알고리즘의 $O(N)$ 구현체에 비해 6배정도, $O(N \lg N)$에 비해 2~3배정도 느리다. 일반 $O(N \lg^2 N)$ 접미사 배열 구현보단 좀 더 빠른 성능을 보여준다(!)
일반 정렬보다 stable_sort가 30%정도 더 빠름에 주의하라.