Zobrist Hash / XOR hash

非常簡單的一篇文章，只是看到沒有什麼中文材料就來科普（？）一下。

Description

Zobrist hash 的用處是快速比較集合之間是否一樣。先令 $U$ 是我們所關心的物件的集合，對於每個物件 $u \in U$，我們都指定一個隨機的 $w$-bit 的二進位數字 $h(u)$ 給他，接著我們在比較兩個集合 $S, T \subseteq U$ 是否一樣的時候，我們直接當作比較 $\bigoplus _ {u \in S} h(u)$ 和 $\bigoplus _ {u \in T} h(u)$ 是否一樣，這樣只要 $w$ 夠大的話就有夠高的機率正確了。
兩者一樣等價於 $\bigoplus _ {u\in S\oplus T} h(u)$ 為 $0$，其中 $S\oplus T$ 是對稱差集。兩個集合不一樣若且唯若對稱差集非空，而由於我們每個數字每個 bit 都是隨機的，所以當對稱差集非空的時候，這個 hash 的這個 bit 為 0 的機率是 $1/2$。
因為要 $w$ 個 bit 都是 $0$ 才會把不一樣誤判成一樣，我們可以知道一次比較只有 $2^{-w}$ 的機率錯誤。常取的值會是 $w=64$。

例題

給定一個長度 $N$ 的序列 $a_1,\dots,a_N$，有 $Q$ 個詢問每次問一個區間 $[l, r]$ 是不是一個 $1$ 到 $r-l+1$ 的排列。
保證 $N, Q \leq 10^6, 1 \leq a_i \leq N$

取 $w = 64$，也就是用 mt19936_64 對每個 $1 \leq x \leq N$ 的 $x$ 生成一個隨機的數字 $h(x)$，每次詢問的時候我們直接比較 $\bigoplus _ {l \leq i \leq r} h(a_i)$ 是不是等於 $\bigoplus _ {1 \leq x \leq r-l+1} h(x)$ 就可以了。兩者都可以前綴和快速算，因此勉強可以算是個 $\mathcal{O}(N + Q)$ 的演算法吧。

來分析一下正確率吧。因為一個區間內的所有數字不一定是集合，前面的論證不一定適用，所以重新來一遍。
如果真的是排列的話算出來的 hash 一定相同，所以我們要算的是詢問的區間不是一個排列的時候恰好 hash 一樣的機率。這樣，一定存在一個 $1 \leq x \leq r-l+1$ 使得 $x$ 不在區間裡面，也就是說在算 $\bigoplus _ {l \leq i \leq r} h(a_i)$ 時完全不會算到 $h(x)$，且 $\bigoplus _ {1 \leq x \leq r-l+1} h(x)$ 當中剛好算到 $h(x)$ 一次。然而 $h(x)$ 的特定一個 bit 是 $0$ 的機率和是 $1$ 的機率一樣都是 $1/2$，因此 hash 在這個 bit 不一樣的機率確實是 $1/2$。

於是一次詢問的錯誤率是 $2^{-w}$，可以知道 $Q$ 次詢問有任何一次錯誤的機率會小於等於 $Q2^{-w} \approx 10^{-12}$（union bound），可以說幾乎不可能（每毫秒跑一筆測資的話，$10^{12}$ 毫秒約 31 年才會錯一筆）。通常競賽中每筆測資的正確率有 $10^{-3}$ 到 $10^{-4}$ 就可以傳了，畢竟通常測資的數量級大概頂多就一兩百筆。

另一個例題

給定一個長度 $N$ 的序列 $a_1,\dots,a_N$，問有幾個區間使得區間裡面所有數字在區間裡面出現的次數都是偶數次。
保證 $N \leq 10^6, 1 \leq a_i \leq N$

一樣先做隨機的 mapping，接著只要回答有幾個區間 $[l, r]$ 使得 $\bigoplus _ {l\leq i\leq r} h(a_i) = 0$ 就可以了，可以用前綴和以及 hashmap 勉強算是做到 $\mathcal{O}(N)$。

「所有數字出現偶數次」等價於「出現奇數次的數字的集合是空集」。根據開頭的論證，對於每個區間 $[l, r]$，「出現奇數次的數字的集合是空集」和「$\bigoplus _ {l\leq i \leq r} h(a_i) = 0$」不同值的機率可以被壓在 $2^{-w}$ 以下。總共有 $N(N+1)/2$ 個區間，所以一樣有任何一個區間錯的機率低於 $N(N+1)/2 \cdot 2^{-w} \approx 10^{-6}$。

這裡必須要小心的是，雖然我們的演算法只有 $\mathcal{O}(N)$，但其實上述的論證會需要所有區間的「集合一樣」和「hash 一樣」都同值，而總共有 $\mathcal{O}(N^2)$ 個區間，「任何一個區間錯」的機率直接用 union bound 只能壓到「特定一個區間錯」的機率的 $\mathcal{O}(N^2)$ 倍，這樣的話取 $w=32$ 會不夠。

對於不同的題目使用 union bound 的時候更是要小心，例如我們可以將這題的區間改成 subsequence，那麼雖然每個事件只有 $2^{-w}$ 的機率錯，但計算整個問題的正確性依賴於 $2^N$ 個不同的事件，所以使用這樣的 hash 可能會錯得很離譜。

參考資料與額外閱讀

• https://codeforces.com/blog/entry/129907
• https://trap.jp/post/1594/
  • 如果第二個例題不是問偶數而是問 $3$ 的倍數？又或者是 $k$ 的倍數？
• https://blog.hamayanhamayan.com/entry/2017/05/24/154618
  • 雖然在第一個例題中，我們看似可以用 zobrist hash 維護 multiset 的 hash，但有些問題是需要別的方法的。

結

下一篇文章不知道有什麼材料。BWT？
不過明天國文要段考。