順列の最小完全ハッシュ関数

この記事は文字列アルゴリズム Advent Calendar 2017 24日目の記事です.

今日 12/24 が何の日か，みなさんもちろん知っていますよね？そう，アッカーマン関数で有名な Wilhelm Friedrich Ackermann¹の没日です．計算理論に多大な貢献をしたアッカーマンに縁のある日に記事を書くということで，身が引き締まる思いです．

さて，この記事では同じ文字が二度現れない文字列とみなすこともできる順列に関して，その最小完全ハッシュ関数のお話をします.

TL;DR

• 順列の辞書順最小完全ハッシュ関数・逆関数の計算は $O(N \log N)$ でできる．(計算モデルを仮定すると高速化可能)
• 辞書順を諦めると，順列の最小完全ハッシュ関数・逆関数の計算は $O(N)$ でできる．

定義

順列 (Permutation)

順列，あるいは置換 (Permutation) とは集合 $S$ から同じ集合 $S$ への全単射関数 $\pi: S \to S$ です²．以降では $n$ 個の整数 $0, 1, \dots, n-1$ の集合 $[n] = \{0, 1, \dots, n-1\}$ 上の順列について考えます．順列の表記としては写像元を上段，写像先を下段にした二段表記がよく用いられます．例えば，$\pi(0) = 1, \pi(1) = 2, \pi(2) = 0$ である順列 $\pi$ に対して，
$\ \ \pi = \left(
\begin{array}{ccc}
0 \ 1 \ 2 \
1 \ 2 \ 0 \
\end{array}
\right)$
と書きます．いちいち二段で書くのはめんどうなので $\pi = (\pi(0), \dots, \pi(n-1))$ のように1段の数列として書くことにします．すると先の例は $\pi = (1, 2, 0)$ となります．この数列はアルファベット $[n]$ 上の文字列とみなすことができ，さらに　$\pi_i \neq \pi_j \ (0 \le i < j \le n-1)$ を満たす特殊な文字列だと考えることができます． $[n]$ 上の順列は $n!$ 通りあります．

ハッシュ関数 (Hash function)

ハッシュ関数は集合 $S$ から整数集合 $[n]$ への関数 $h: S \to [n]$ です．つまるところ値域が正整数なだけのただの関数なんですが，一般には性質として計算機で扱う上での計算時間が考えられていることが多いです．例えば関数の計算が容易だとハッシュテーブル上のインデックス計算，逆関数の計算が容易だと圧縮，困難だと暗号に用いることができます．写像先の整数値をハッシュ値と呼びます．

ここで，ハッシュ関数はただの関数なので，全射とも単射とも限らないことに注意しましょう．このため例えばハッシュテーブルへの応用ではオープンハッシュやクローズドハッシュなどの工夫でハッシュ衝突 (= 2つ以上の $S$ の要素のハッシュ値が等しくなること) を処理します．ハッシュ衝突が少ないような関数であることもよいハッシュ関数の条件だと暗に考えている人が多い気がしますし，実際の応用でもハッシュ衝突が少ない方が嬉しい場面が多いと思います．

完全ハッシュ関数 (Perfect hash function)

完全ハッシュ関数とはハッシュ衝突が絶対に起こらないようなハッシュ関数のことであり，要は単射であるハッシュ関数のことです．このとき $h: S \to [n]$ における $n$ は $n \ge |S|$ を満たします．単射なので逆関数が存在することが保証されている点が嬉しいポイントです．

最小完全ハッシュ関数 (Minimal perfect hash function)

最小完全ハッシュ関数とは，完全ハッシュ関数の中で値域の取りうる範囲が最小であるような関数です．このとき最小の $n$ は $n = |S|$ なので $h: S \to [|S|]$ となり，これは定義域と値域の濃度が同じ単射関数なので，すなわち全単射関数です³．最小完全ハッシュ関数を設計できるとハッシュテーブルは何も考えずに長さ $|S|$ の配列にすればよいので，時間計算量・空間計算量・実装の容易さ・定数倍・キャッシュヒット率 etc. と多くの観点からとても嬉しいです．もちろん，最小完全ハッシュ関数の計算にかかる計算リソースとトレードオフになることもあります．

辞書順最小完全ハッシュ関数 (Lexicographic minimal perfect hash function)

名前長すぎワロタw

集合 $S$ が全順序集合である，すなわち $S$ の任意の2要素 $a, b \in S$ 間に全順序$\prec$が定義されているとき，$a \prec b \Leftrightarrow h(a) \le h(b)$ を満たす $h$ を辞書順最小完全ハッシュ関数と定義します．つまり，要素 $a \in S$ が全順序$\prec$において $S$ の中で $i$ 番目 (0-origin) ならば，$h(a) = i$ となるような関数のことです．ハッシュ関数を辞書順にしない場合，全単射性を満たすような関数をどのようにすれば構成できるのかよくわからなかったりするので，最小完全ハッシュ関数を設計したいときにまず最初に (自然な全順序における) 辞書順最小完全ハッシュ関数を考える人も多いでしょう．

逆に，任意の最小完全ハッシュ関数は定義域の集合に勝手に新たな全順序を定義することで，その全順序集合上での辞書順最小完全ハッシュ関数であると見ることもできます．このためか，(自然な辞書順でなくても) 最小完全ハッシュ関数 $h: S \to [|S|]$ についてハッシュ値 $h(x)$ を計算することを rank (動詞)，逆関数 $h^{-1}(y)$ を計算することを unrank と言ったりします．

順列の最小完全ハッシュ関数

$[n]$ 上の順列すべてからなる集合を $S_n$ と書くことにします．すると $[n]$ 上の順列の最小完全ハッシュ関数は全単射 $h: S_n \to [n!]$ となります．今まで例示してきたの $S \to [n]$ に見た目が似ていますが，あくまでここでは $[n]$ は順列の台集合であり，ハッシュ関数の写像先ではないことに注意してください．

順列の辞書順最小完全ハッシュ関数の計算アルゴリズム

順列の辞書順を以下の全順序で定義します．
$\ \ \pi \prec \sigma \Leftrightarrow \exists i \ s.t. \ \pi(j) = \sigma(j) \ \text{for} \ j < i, \pi(i) < \sigma(i)$
要は文字列として見たときの普通の辞書順です．このとき，$[n]$ 上の順列の辞書順最小完全ハッシュ関数はそもそももう決まっており，以下の式で計算できます．
$\ \ h(\pi) = v_0 \cdot (n-1)! + v_1 \cdot (n-2)! + \dots + v_{n-2} \cdot 1! + v_{n-1} \cdot 0!$
ここで，$v_i \ (0 \le i \le n-1)$ は inversion vector と呼ばれる数列で，$v_i := |\{ i < j \mid \pi_i > \pi_j\}|$，すなわち整数列としてみたとき，$i$ より後ろにある要素のうち $\pi_i$ より小さい (=反転している) インデックスの個数です．

この式の気持ちを見ていきます．まず $v_0$ について考えると，$\pi_0$ より小さい要素が先頭になるような順列の方が明らかに辞書順が早いです．先頭の要素を固定した順列は $(n-1)!$ 通り，$\pi_0$ より小さい要素は $\pi_0$ 通りなので，$\pi_0$で始まる順列は少なくとも $\pi_0 \cdot (n-1)!$ 番目以降です．あとは $\pi_0$ で始まる順列の中で何番目なのかわかれば，それに $\pi_0 \cdot (n-1)!$ を足せば全体で何番目なのかわかります．最初の要素なので，$v_0 = \pi_0$です．以降も再帰的に同じことを考えていけばいいのですが，以降は $\pi_0$ を除いて考える必要があります．$i-1$ 番目までの要素を除き， $i$番目以降の要素だけ考えたとき， $\pi_i$ が何番目に小さいのかに対応するのが $v_i$ です．よって，$v_i \cdot (n-i-1)!$ を足し続けることにより，順列 $\pi$ が辞書順で何番目なのかが求まります．

上式の形からわかるとおり，順列の辞書順最小完全ハッシュ関数は inversion vector $v$ が得られていれば，上記の計算式から線形時間 $O(N)$ で計算可能です．言い換えると，計算時間のボトルネックは inversion vector を求める部分になります．

inversion vector は愚直なアルゴリズムで計算すると $O(N^2)$ で求められます． これは各要素 $i$ について，自分より後ろにある要素をループで舐めて，自分より小さいかどうか判定して数えることで実現できます．この計算時間はまだ改善可能です．
$i$ より後ろにある要素だけからなる集合を $P_i$ と表記することにします．$i=n-1$ から降順に $v_i$ の値を計算していく際，$v_i$ の計算直前にはすでに $P_i$ が何らかのデータ構造で管理されているとします．$v_i$ の値は $P_i$ に含まれる $v_i$ より小さい要素の個数なので，これをデータ構造に聞き，返り値を $v_i$ とします．その後，次の $v_{i+1}$ の計算に備え，データ構造の管理する集合に $\pi_i$ を加えるようデータ構造にクエリを投げ，$P_{i+1}$ に更新します．つまり，(1) 値の追加，(2) ある値より小さな値の個数の計算，という2つの操作を高速に行えるデータ構造を用いることで，高速化が期待できます．これは例えば平衡二分探索木，セグメントツリー，Fenwick tree などによって$O(\log N)$ で実現できます．操作回数は $O(N)$ なので，これにより全体で $O(N \log N)$ でハッシュ値の計算が可能です．逆関数も同様にして計算できます．

また，順列の台集合が $[n]$ であることと，計算モデルに仮定をおくことで van Emde Boas 木などのデータ構造で計算時間をさらに改善することもできます．ここまでの話は @tmaehara さんのスライド でだいたい触れられています．

最小完全ハッシュ関数の計算アルゴリズム

辞書順にこだわるのをやめると自分で好きにハッシュ関数を決めてよくなるので，高速に rank, unrank が可能な最小完全ハッシュ関数を自分で設計することができます．ここでは， Myrvold & Ruskey 2001⁴ の最小完全ハッシュ関数，およびその rank, unrank アルゴリズムを紹介します．これは線形時間で rank, unrank ができます．アルゴリズムはいたってシンプルで，以下のようになります．ここで，あらかじめ $\pi$ の逆順列 (= 逆関数) $\pi^{-1}$ も求めて配列として持っておきます． (これは線形時間で計算可能です．)

rank ($n$, $\pi$, $\pi^{-1}$):
$\ \ $ if $n = 1$ then return $0$
$\ \ $ $s = \pi_{n-1}$
$\ \ $ swap($\pi_{n-1}$, $\pi_{\pi^{-1}_{n-1}}$)
$\ \ $ swap($\pi^{-1}_s$, $\pi^{-1}_{n-1}$)
$\ \ $ return $s + n \cdot$rank($n-1$, $\pi$, $\pi^{-1}$)

謎の $s$ が導入されるし，二重で添え字が入っていて一瞬混乱するかもしれませんが，冷静に読むとこれは $n-1$ 番目の要素と $n-1$ を入れ替えている (+ それに合わせて逆順列も更新している) だけです．さらに言い換えると，$n-1$ を本来あるべき $n-1$ 番目に戻している，すなわちソートしていると捉えることもできます．すると $n-2$ 番目までの要素はすべて $n-2$ 以下になるため，再帰の引数に渡しているのは実質長さ $n-1$ の順列ということになります．

これが最小完全ハッシュ関数であること (= ハッシュ衝突せず，値が $0$ から $n!-1$ までであること) は帰納法で証明できます．帰納法の基底は自明です．帰納ステップとして，rank($n-1$, $\pi$, $\pi^{-1}$) が $0$ から $(n-1)! - 1$ までの値を返す最小完全ハッシュ値を返すと仮定すると，rank($n$, $\pi$, $\pi^{-1}$)$-s$ の値は $0$ から $n! - n$ までの $n$ の倍数ということになります．$0 \le s \le n-1$ より rank($n$, $\pi$, $\pi^{-1}$) は 被りなく $0$ から $n!-1$ の範囲をとります．よってこの rank は最小完全ハッシュ関数となります．

unrank も同様に以下のアルゴリズムで計算できます．ここで初期値としては $r$ には unrank したいハッシュ値，$\pi$ には恒等順列 $(1, 2, \dots, n-1)$ を与えるものとします．アルゴリズムが終了したときの $\pi$ が unrank された順列です．

unrank ($n$, $r$, $\pi$):
if $n > 0$:
$\ \ $ swap($\pi_{n-1}$, $\pi_{(r \mod n)}$)
$\ \ $ unrank ($n-1$, $\lfloor r / n \rfloor$, $\pi$)

これは rank 計算アルゴリズムにおける $s$ が $r \mod n$ であることを考えると簡単に理解できます．

ちなみに余談として，これらのアルゴリズムは $S_n$ から順列1つを一様ランダムに生成する以下のアルゴリズムに着想を得て考案されたものです．

random ($n$, $\pi$):
for $k = n-1, n-2, \dots, 1$:
$\ \ $ swap($\pi_k$, $\pi_{rand(k)}$)

ここで，rand($k$) は $0$ 以上 $k$ 以下の整数を一様ランダムに生成する関数です．ランダムな順列の生成は結構したくなることがある (もしかして僕だけですか？) のでこれは知っておくと便利です．

まとめ

最小完全ハッシュ関数は主にハッシュテーブルを実装をする際に便利です．例えば順列をキーにする動的計画法をするときなども，DPテーブルを配列で実装できるようになるため嬉しみがあります．

辞書順最小完全ハッシュ関数は順列の全順序とハッシュ値の全順序とが一致するという性質があります．$O(N \log N)$ で計算できるので実用上もそれなりに高速です．

最小完全ハッシュ関数は辞書順のような綺麗な性質は失われますが，rank, unrank がシンプルな実装で $O(N)$ で実現できます．

今回紹介したように漸近評価で計算量が優れたアルゴリズムがすでに存在するので，もうそんなに盛んに研究されてないという認識ですが，例えば Blai Bonet 2008⁵ のように empirical に効率的なアルゴリズムの研究もあるようです．

1. 575 ↩

2. wikipediaでは単射 $f: [k] \to [n] \ (k \le n)$ のことを順列，$n = k$のときを置換と分けているようですが，本記事ではこのような区別をせず，$f: [n] \to [n]$ を順列，置換と呼びます． ↩

3. つまり一般性を失わず $S = [n]$ とすると最小完全ハッシュ関数も順列と見做せるわけですが，ここでは混乱を招くので特に触れません． ↩

4. Wendy Myrvold and Frank Ruskey, "Ranking and unranking permutations in linear time," Information Processing Letters, Vol. 79, pp. 281–284, 2001. ↩

5. Bonet, Blai. "Efficient algorithms to rank and unrank permutations in lexicographic order," AAAI-Workshop on Search in AI and Robotics, pp. 142-151, 2008. ↩