$ \DeclareMathOperator{\arccosh}{arccosh} \DeclareMathOperator{\arcsinh}{arcsinh} \DeclareMathOperator{\rank}{rank} \DeclareMathOperator{\rot}{rot} \DeclareMathOperator{\grad}{grad} \DeclareMathOperator{\diver}{div} $

最小完全ハッシュ函数

ハッシュ函数のうち、可逆で、かつ、生成するハッシュ値の値域が最小である函数のことを、最小完全ハッシュ函数と言います。 その作り方を解説していきたいと思います。

1最小完全ハッシュ函数

まずは最小完全ハッシュ函数とは何かということを紹介していきます。

1.1ハッシュ函数

ハッシュ函数(hash function)とは、あるデータが与えられたときに、そのデータを代表する(短い)数値を返す函数のことです。
現在よく使われているのは、MD5 [1] やSHA1 [2] と呼ばれるハッシュ函数です。 これらはバイナリデータを入力とし、一定の長さのバイナリデータ [3] を返します。
少し例を挙げて説明します。
ある会社で大量の(数十万人とか)顧客の情報を扱う場合を考えます。 しかし顧客一人ひとりの情報を細かく集めようとすると、すごい量になります。 住所、氏名、年齢、生年月日はおろか交友関係、性癖、もっと言えば生まれてからこの方までの行動や言動、全てが一個人の情報として含まれています。
まぁそこまで細かい情報を顧客が提供してくれるかどうかは別として、これらすべての情報を集めて管理するのははっきり言って現実的ではありません。 膨大な情報のうちから必要なデータのみを抜き出して管理することが必要でしょう。 そうすれば見なければいけないデータが減るので検索にも有利ですし、メモリ(HDD)も節約できます。
この場合だと(目的に依りますが)氏名、年齢、住所、性別、電話番号、メールアドレスなどを持っていれば十分だと思います。
このように、膨大なデータからそのデータを代表する値のみを取り出す函数のことをハッシュ函数と言います。
ちなみにハッシュ函数が出力する値のことをハッシュ値などと呼びます。

1.2完全ハッシュ函数

ハッシュ函数のうち入力が異なれば出力も必ず異なるものを完全ハッシュ函数(perfect hash function)と言います。
出力が分かれば入力が分かるので、可逆なハッシュ函数のことを完全ハッシュ函数と言うと思ってもらって構いません。
先ほどの顧客の例で言うと、氏名をハッシュ値として採用するハッシュ函数では、同姓同名の人がいる可能性があるので、完全ハッシュ函数とはいえません。
一方、氏名と住所のセットをハッシュ値と採用するハッシュ函数を考えると、同姓同名の人が同じ場所に住んでいるという状況はまず考えられませんから [4] 、このときには完全ハッシュ函数となっています。

1.3最小完全ハッシュ函数

入力として考えられる値がちょうど$n$個だとします。 この入力に対する完全ハッシュ函数のうち、出力が $0 \cdots n-1$の内のどれかであるハッシュ函数を、最小完全ハッシュ函数(minimal perfect hash function)といいます。
"最小"という名が付いているのは、あらゆる完全ハッシュ函数のうちで最もコンパクトな数値を出力する函数が最小完全ハッシュ函数だからです(たぶん)。
先ほどの名簿の例では最小完全ハッシュ函数を作るのは難しい[5]ので、$0$または$1$の数字が二個並んでいる入力に対して最小完全ハッシュ函数を考えましょう。
  • $00 \rightarrow 0$
  • $01 \rightarrow 1$
  • $10 \rightarrow 2$
  • $11 \rightarrow 3$
とすれば最小完全ハッシュ函数となっています。

1.3.1要件

入力が$n$通りの最小完全ハッシュ函数の出力は、$0 \cdots n-1$のうちのいずれかです。
さらに言うと、あるハッシュ函数が最小完全ハッシュ函数である必要十分条件は、
  • 入力が異なれば出力も異なる
  • 出力は$0 \cdots n-1$のいずれかである
です。 重要なので覚えておいてください。

[1]「えむでぃふぁいぶ」と読む。MDはMessage Digestの略。詳細な仕様は、RFC 1321を参照されたい
[2]「しゃーわん」と読む。SHAはSecure Hash Argolismの略。詳細な仕様は、FIPS PUB 180-1を参照されたい
[3]MD5は128ビット、SHA1は160ビット。 通常これらの値は十六進数を用いて表す。 十六進数表記においては、MD5は32桁、SHA1は40桁
[4]さすがに同じ名前をつける人はいませんよね…。
[5]不可能な気がする

20...n-1の数の並び

$0 \cdots n-1$の数値が$k$個並んでいる順列の最小完全ハッシュ函数を考えましょう。
例えば一週間に一度だけ家の前を通る竿竹屋さんがいて、彼が何曜日に家の前を通るのかを一ヶ月間記録したいとします。 日曜日を$0$、月曜日を$1$、という風に曜日を数字で表すことにすれば一ヶ月の記録は、$0 \cdots 6$の数値が$4$個並んでいる順列になりますね。

2.1作り方

この順列を$k$桁の$n$進数だとみなすと、これは最小完全ハッシュ函数の要件をすべて満たします。
たとえば$k=2, n=3$の時に与えられ得る入力と、その出力を書き出すと、
  • $00 \rightarrow 0$
  • $01 \rightarrow 1$
  • $02 \rightarrow 2$
  • $10 \rightarrow 3$
  • $11 \rightarrow 4$
  • $12 \rightarrow 5$
    (以下略)
という風に最小完全ハッシュ函数になっています。

2.2完全性

$n$進数なので自明でしょう。

2.3最小性

入力は全部で$n^k$種類であり、$k$桁の$n$進数のとりうる値は$0 \cdots n^{k-1}$なので最小です。

3i番目が0...ai-1のいずれかである数列

入力の$i$番目が$a_i$通りの値をとりうる場合($0 \cdots a_i-1$のいずれか)の最小完全ハッシュ函数を考えます。

3.1作り方

入力を、
\begin{equation} b_0, b_1, b_2, \cdots ,b_{n-1} \end{equation}
(1)
とおくと、最小完全ハッシュ函数は、
\begin{equation} f_a(b) = b_0 + a_0 \times b_1 + a_0 a_1 \times b_2 + \cdots + a_0 \cdots a_{n-2} \times b_{n-1} \end{equation}
(2)
です。

3.2完全性

$b_i, c_i$を入力とするとき、
	$k$番目より前については$b_i$と$c_i$は等しいが、$k$番目は異なるとする。
	このとき、上で定義されたハッシュ函数の出力は必ず異なる。
ということを示します。
まず、
\begin{equation} \mod a_0 a_1 \cdots a_k \end{equation}
(3)
では、
\begin{equation} f_a(b) \equiv b_0 + a_0 b_1 + \cdots + a_0 \cdots a_{k-1} b_k \end{equation}
(4)
\begin{equation} f_a(c) \equiv c_0 + a_0 c_1 + \cdots + a_0 \cdots a_{k-1} c_k \end{equation}
(5)
なので、
\begin{equation} f_a(b) - f_a(c) \equiv a_0 \cdots a_{k-1} (b_k - c_k) \not\equiv 0 \end{equation}
(6)
より示されました。

3.3最小性

まず与えられる入力は全部で、
\begin{equation} a_0 \times a_1 \times \cdots \times a_{n-1} \end{equation}
(7)
通りです。
そして上で定義したハッシュ函数の出力の最小値は、
\begin{equation} \forall i, b_i = 0 \end{equation}
(8)
のときに$0$をとります。
一方、最大値は、
\begin{equation} \forall i, b_i = a_i-1 \end{equation}
(9)
のときに、
\begin{eqnarray*} & & b_0 + a_0 \times b_1 + \cdots + a_0 \cdots a_{n-2} \times b_{n-1} \\ & = & (a_0 - 1) + a_0 (a_1 - 1) + \cdots + a_0 \cdots a_{n-2} (a_{n-1} - 1) \\ & = & a_0 \cdots a_{n-1} - 1 \end{eqnarray*}
(10)
です。
以上で最小性は示されました。

40...n-1の順列

次に、$0 \cdots n-1$の数字を並び替えた数列の最小完全ハッシュ函数を考えます。

4.1作り方

分かりにくいので$n=5$として、$\{3, 4, 1, 5, 2\}$という数列を例にとって説明します。

4.1.1自分より大きい数字

まずは自分よりも右にある数字のうち、自分自身の数字よりも大きいもの[1]を数えます。
元の数列34152
自分より大きな数字2120-
{2, 1, 2, 0}という数列が得られました。

4.1.2マージ

次に上で得られた数列に左から順に、$1, 5, 5 \times 4, 5 \times 4 \times 3$を掛けます。
\begin{equation} \{2, 1, 2, 0\} \rightarrow \{2, 5, 40, 0\} \end{equation}
(11)
そして各項を足し合わせて完成です。
\begin{equation} 2 + 5 + 40 + 0 = 47 \end{equation}
(12)

4.2完全性と最小性

第一段階で生成した数列は、前セクションで解説した数列と同じ [2] です。 ちなみに左から順に、数列のとりうる値は、
\begin{equation} 0 \cdots 4, 0 \cdots 3, 0 \cdots 2, 0 \cdots 1 \end{equation}
(13)
となっています。
前セクションでの議論により、このハッシュ函数は最小完全ハッシュ函数です。

[1]小さいものでもよい
[2]第二段階での操作は前セクションで解説したやり方を真似てやっていることが分かります