Practical Minimal Perfect Hash Function

Presentation on theme: "Practical Minimal Perfect Hash Function"— Presentation transcript:

1 Practical Minimal Perfect Hash Function
Susumu Yata

2 参考文献 Simple and Space-Efficient Minimal Perfect Hash Functions
Hypergraph と Rank/Select を利用した完全ハッシュ Fabiano C. Botelho, Rasmus Pagh and Nivio Ziviani 10th International Workshop on Algorithms and Data Structures (WADS07) , August 2007 Bep: Associative Arrays for Very Large Collections 大規模コレクション向けの連想配列 Daisuke Okanohara Practical Minimal Perfect Hash Function 2019/4/15

3 説明の順序 概要 基礎知識 提案手法 評価 まとめ 提案手法の特徴と応用 ハッシュと完全ハッシュ コンセプト ハッシュ関数 → 完全ハッシュ
完全ハッシュ → 最小完全ハッシュ 評価 時間と空間 まとめ Practical Minimal Perfect Hash Function 2019/4/15

4 提案手法の概要と成果物 実用的な最小完全ハッシュ関数 公開ライブラリとライセンス 規模 大規模なキー集合 （1000 万件でも大丈夫）
規模 大規模なキー集合 （1000 万件でも大丈夫） 時間 構築時間は O(n), 検索時間は O(1) 領域 理論的下限値の 2 倍程度 （3 bits/key） 公開ライブラリとライセンス LGPL 修正 BSD ライセンス 特に指定なし Practical Minimal Perfect Hash Function 2019/4/15

5 最大の特徴 3 bits/key は伊達じゃない 例えば，ダブル配列… キー数 サイズ 補足 10 万 37.5 KB キャッシュ
理論的に 8 bytes/key 以上 1 億 → 800 MB 以上 … むりぽ キー数 サイズ 補足 10 万 37.5 KB キャッシュ 100 万 375 KB 1000 万 3.75 MB キャッシュ & メモリ 1 億 37.5 MB メモリ 10 億 375 MB Practical Minimal Perfect Hash Function 2019/4/15

6 その他の特徴 マッチング 未登録キーの扱い 時間 完全一致のみ → ダブル配列（トライ）とは別用途 登録／未登録を判断できない
完全一致のみ → ダブル配列（トライ）とは別用途 未登録キーの扱い 登録／未登録を判断できない 何かが出てくる → あらためて確認が必要 時間 ハッシュ値を 2, 3 用意する Rank 関数も使う → こいつらがネック Practical Minimal Perfect Hash Function 2019/4/15

7 その特徴を生かすには？ 記憶装置の特性を考慮 ネックが緩和されるのは… インデックスとして利用
速い キャッシュ ＞ メモリ ＞ HDD 遅い ネックが緩和されるのは… 低速な記憶装置にデータを置く状況 インデックスとして利用 Case 1: ハッシュ関数 on キャッシュ → インデックス キー本体 on メモリ → データ Case 2: ハッシュ関数 on メモリ → インデックス キー本体 on HDD → データ Practical Minimal Perfect Hash Function 2019/4/15

8 提案手法の応用先 Web アーカイブ 参照方法 課題 入力 URI 平均 100 Bytes 出力 DATA 平均 10 KB
規模 1 億ページ URI リスト 10 GB on HDD or SSD DATA リスト 1 TB on HDD 参照方法 完全ハッシュ （37.5 MB） → URI リスト → DATA リスト  課題 構築時の作業領域については未検討  Practical Minimal Perfect Hash Function 2019/4/15

9 基礎知識 ハッシュ関数から最小完全ハッシュ関数まで Practical Minimal Perfect Hash Function
2019/4/15

10 ハッシュ関数 ハッシュ表にて利用 注意 Apple 1 ハッシュ関数 衝突 Orange ＆ 2 再ハッシュ 3 Grape …
衝突したときは再ハッシュ 少ないほど良い 注意 MD5, SHA-1 暗号理論にて頻出のハッシュ関数 Apple ハッシュ関数 1 衝突 ＆ 再ハッシュ Orange 2 3 Grape … Practical Minimal Perfect Hash Function 2019/4/15

11 完全ハッシュ関数 衝突のないハッシュ関数 1 Sushi 2 Tempura 完全 3 ハッシュ関数 Mt. Fuji 4 Geisha 5
空のセルがあったりなかったり 1 Sushi 2 完全 ハッシュ関数 Tempura 3 Mt. Fuji 4 Geisha 5 Samurai 6 7 Practical Minimal Perfect Hash Function 2019/4/15

12 最小完全ハッシュ関数 衝突も空きもないハッシュ関数 Ninja 1 Sushi 2 Harakiri 最小完全 3 ハッシュ関数
Ninja 1 Sushi 2 Harakiri 最小完全 ハッシュ関数 3 Tempura 4 Mt. Fuji Geisha 5 Samurai 6 Naruto 7 Practical Minimal Perfect Hash Function 2019/4/15

13 提案手法のコンセプト イメージをつかむ Practical Minimal Perfect Hash Function 2019/4/15

14 提案手法のコンセプト 完全ハッシュ関数の生成 最小完全ハッシュ関数への変換 ハッシュ関数を 2, 3 用意
合成して完全ハッシュ関数になるか検証 ダメなら再チャレンジ 最小完全ハッシュ関数への変換 Rank 関数による穴埋め Practical Entropy-Compressed Rank/Select Dictionary Okanohara, Daisuke and Kunihiko Sadakane In the Proceedings of ALENEX 2007 Practical Minimal Perfect Hash Function 2019/4/15

15 基になるハッシュ関数の用意 汎用的なハッシュ関数を 2, 3 用意 Sushi ハッシュ関数０ 1 Tempura 2 ハッシュ関数１
ハッシュ表も 2, 3 用意 大きさには少し余裕を持たせる Sushi ハッシュ関数０ 1 Tempura 2 ハッシュ関数１ Mt. Fuji 3 Geisha 4 Samurai 5 Practical Minimal Perfect Hash Function 2019/4/15

16 ハッシュ関数の合成 衝突しないようにハッシュ関数を選択 Sushi ハッシュ関数０ 1 Tempura 2 ハッシュ関数１ Mt. Fuji
適当に組み合わせる うまくいかないときはハッシュ関数を用意しなおす Sushi ハッシュ関数０ 1 Tempura 2 ハッシュ関数１ Mt. Fuji 3 Geisha 4 Samurai 5 Practical Minimal Perfect Hash Function 2019/4/15

17 ハッシュ関数の組み合わせを数値化 選択テーブル g を用意 g Sushi : g[2]+g[3] = 0 1
Sushi : g[2]+g[3] = 0 1 Tempura : g[2]+g[4] = 1 2 Mt. Fuji : g[1]+g[3] = 0 3 Geisha : g[0]+g[3] = 0 4 1 Samurai : g[2]+g[5] = 1 5 1 Practical Minimal Perfect Hash Function 2019/4/15

18 完全ハッシュ関数ができた 構成要素 Sushi 1 Tempura 2 完全 ハッシュ関数 Mt. Fuji 3 邪魔 Geisha 4
hash0() ハッシュ関数 その１ hash1() ハッシュ関数 その２ g[] 選択テーブル Sushi 1 Tempura 完全 ハッシュ関数 2 Mt. Fuji 邪魔 3 Geisha 4 Samurai 5 Practical Minimal Perfect Hash Function 2019/4/15

19 そして最小完全ハッシュ関数へ 下準備 Rank 関数 最小完全ハッシュ関数 used Rank 1 1 1 1 2 1 2 3 3 4 1
時間計算量 O(1) 最小完全ハッシュ関数 Rank の値を返すのみ used Rank 1 1 1 1 2 1 2 3 3 4 1 3 5 1 4 Practical Minimal Perfect Hash Function 2019/4/15

20 提案手法の実装 ハッシュ関数の用意 Practical Minimal Perfect Hash Function 2019/4/15

21 基になるハッシュ関数の工夫 汎用的なハッシュ関数（bep にて採用） ハッシュ関数を 3 つ ← 経験的に良い分割数 代案
高速で均一（CPU の知識が必要） 設定の変更による切り替えが可能 ハッシュ関数を 3 つ ← 経験的に良い分割数 欠点 1： 用意するのが面倒 欠点 2： 計算に時間がかかる 代案 キーを 3 分割 Practical Minimal Perfect Hash Function 2019/4/15

22 キーを 3 分割 高速化のポイント I N T E R N A T I O N A L I Z E I N T E R N A T I O
32 or 64 ビットずつ処理（パッキング） ハッシュ関数を 1 回だけ使う 例： INTERNATIONALIZE → INTELIZE + RNAT + IONA I N T E R N A T I O N A L I Z E I N T E R N A T I O N A L I Z E I N T E L I Z E R N A T I O N A キー 1 キー 2 キー 3 Practical Minimal Perfect Hash Function 2019/4/15

23 キーが短いときは キーを分割できないので I N T E R N A T I O N A L I Z E I N T E R N A T I
最終ブロックをパッキングしない ← 未検証 例： INTERNATIONALIZE → INTELE + RNATI + IONAZ 例： HASH → HH + A + S I N T E R N A T I O N A L I Z E I N T E R N A T I O N A L I Z E I N T E L E R N A T I I O N A Z キー 1 キー 2 キー 3 Practical Minimal Perfect Hash Function 2019/4/15

24 ハッシュ値の算出 ハッシュ値の取りうる値 ハッシュ値の求め方 ← 実際には一度の呼び出し キー数 n に対して ［0, 1.23n）
ハッシュ関数が均一と仮定して 1000 回の試行でほぼ 100% 成功する大きさ 分割キーに割り当てる ブロックの大きさ m: 1.23n / 3 = 0.41n キー 1 ［0, m），キー 2 ［m, 2m），キー 3 ［2m, 3m） ハッシュ値の求め方 ← 実際には一度の呼び出し ハッシュ値 1： hash(key1) % m ハッシュ値 2： m + (hash(key2) % m) ハッシュ値 3： 2m + (hash(key3) % m) Practical Minimal Perfect Hash Function 2019/4/15

25 提案手法の実装 完全ハッシュ関数の実現 Practical Minimal Perfect Hash Function 2019/4/15

26 ハイパーグラフの例（ハイパーグラフ – Wikipedia）
Hypergraph（ハイパーグラフ） ハイパーなグラフのこと ← 分からなくても大丈夫 X 頂点の集合 頂点の次数 エッジの数 E エッジの集合 エッジの濃度 頂点の数 各エッジは X の部分集合（空集合を除く） ハイパーグラフの例（ハイパーグラフ – Wikipedia） Practical Minimal Perfect Hash Function 2019/4/15

27 参考：ハイパーグラフ – Wikipedia
特殊なハイパーグラフ k-uniform hypergraph 各エッジの濃度が k 各エッジが持つ頂点の数が k 個という意味 一般的なグラフは 2-uniform hypergraph k-partite hypergraph k 個に分割できるハイパーグラフ 前頁の例は 3-partite hypergraph 参考：ハイパーグラフ – Wikipedia だいたいこんな感じ Practical Minimal Perfect Hash Function 2019/4/15

28 ハッシュ値からハイパーグラフを生成 ハイパーグラフの構成 キー 1 キー 2 キー 3 Tempura 4 7 Mt. Fuji 1 5 8
3-partite uniform hypergraph キー数 n に対して1.23n 個の頂点（m = 0.41n ずつ） 各キーのハッシュ値 3 つからなる n 個のエッジ キー 1 キー 2 キー 3 Tempura 4 7 Mt. Fuji 1 5 8 Geisha 2 6 9 Samurai Practical Minimal Perfect Hash Function 2019/4/15

29 Acyclic（非循環）かどうかを検証 Acyclic とは ← この論文での定義 Tempura 4 7 Mt. Fuji 1 5 8
以下の手順によりすべてのエッジを除去できるかどうか 次数 1 の頂点を含むエッジを探す 最初は Tempura, Mt. Fuji, Samurai のどれか 見つからなければ終了する 当該エッジを取り除いて最初に戻る Tempura 4 7 Mt. Fuji 1 5 8 Geisha 2 6 9 Samurai Practical Minimal Perfect Hash Function 2019/4/15

30 Acyclic だとどうなるの？ 完全ハッシュ関数ができる 1 2 Tempura 4 7 Mt. Fuji 1 5 8 Geisha 2
取り除いたエッジ（キー）の順番を利用する 逆順にハッシュ値を割り当てる 同時に選択テーブルを生成する 1 2 Tempura 4 7 Mt. Fuji 1 5 8 Geisha 2 6 9 Samurai Practical Minimal Perfect Hash Function 2019/4/15

31 選択テーブルを生成 どのハッシュ値を採用するのか決める id 1 2 Tempura 4 7 Mt. Fuji 1 5 8 Geisha 2
1 2 Tempura 4 7 Mt. Fuji 1 5 8 Geisha 2 6 9 Samurai hashValue Practical Minimal Perfect Hash Function 2019/4/15

32 アンコール（Encore） もう一回 id 1 2 hashValue Tempura 4 7 2 1 Mt. Fuji 1 5 8
各キーのハッシュ値からエッジを生成する 完全ハッシュ関数になるかどうか判定する 選択テーブルを生成する id 1 2 hashValue Tempura 4 7 2 1 Mt. Fuji 1 5 8 Geisha 1 1 2 g 2 6 9 Samurai 1 Practical Minimal Perfect Hash Function 2019/4/15

33 提案手法の実装 最小完全ハッシュ関数の実現 Practical Minimal Perfect Hash Function
2019/4/15

34 Rank 関数 Rank 関数の定義 Rank 関数の時間計算量 1 1 1 1 1 1 1 1 1 1 1 2 3 4 4 5 5 6 7
ビット列 bits[] に対して bits[0] から bits[x-1] までに含まれるビット 1 の数 Rank 関数の時間計算量 インデックスなし O(n) インデックスあり O(1) 1 1 1 1 1 1 1 1 1 1 1 2 3 4 4 5 5 6 7 8 9 Practical Minimal Perfect Hash Function 2019/4/15

35 Rank 辞書 Rank 関数の高速化 … … … ビット列を 2 段階のブロックに分割する 大きめのブロック 256 ビット
大きめのブロック 256 ビット 各ブロックの先頭に対する Rank() を保存 ← かろうじて O(1) 32 bit / large block ← bit / bit 小さめのブロック 32 ビット 大きめのブロック内での Rank() を保存 ← まさしく O(1) 8 bit / small block ← 0.25 bit / bit … … … Practical Minimal Perfect Hash Function 2019/4/15

36 小さめブロック内での計算 選択肢は 3 つくらい 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 2 2 1 1 3 2 4 2
SSE4 POPCNT 命令 工夫なし 32 回のループ 工夫あり ビット演算を使ってマージ 参考 1 “PopCount” で Google 先生に尋ねる 参考 2 “Hacker’s Delight”, Addison-Wesley, 2002 参考 3 “ハッカーのたのしみ”, エスアイビーアクセス, 2004 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 2 2 1 1 3 2 4 2 5 6 11 Practical Minimal Perfect Hash Function 2019/4/15

37 Rank 関数で何をするんだっけ？ 完全ハッシュ関数の穴埋め used 最終結果 1 Ninja 完全ハッシュ関数 Rank 関数
1 Ninja 完全ハッシュ関数 Rank 関数 Sushi 2 1 1 3 1 2 Harakiri 4 1 3 Tempura Mt. Fuji 6 1 4 Geisha Samurai 8 1 5 9 1 6 Practical Minimal Perfect Hash Function 2019/4/15

38 評価とまとめ そろそろ終わり Practical Minimal Perfect Hash Function 2019/4/15

39 理論的な評価 空間 時間 選択テーブル 1.23n x 2 = 2.46n bits
Rank 辞書 1.23n x = 0.46n bits 合計 bits/key 時間 参照 O(1) ハッシュ関数 O(1) + Rank 関数 O(1) 構築 O(n) ハッシュ関数 O(n) + ハイパーグラフ生成 O(n) + Acyclic 検証 O(n) + 選択テーブル生成 O(n) + Rank 関数 O(n) 1000 回の試行でほぼ 100% 決まる想定 Practical Minimal Perfect Hash Function 2019/4/15

40 まとめ まとめ 今後の課題 ハッシュ関数の合成による最小完全ハッシュ関数の実現 従来の最小完全ハッシュ関数とは違って実用的
3-partite uniform hypergraph と Rank 関数を利用 従来の最小完全ハッシュ関数とは違って実用的 O(n) で構築して，O(1) で参照できる サイズは理論的下限の 2, 3 倍くらい 今後の課題 構築時の作業領域を削減したい ディスク上でなんとかならないか 応用したい 応用例（Web アーカイブ）みたいなもの Practical Minimal Perfect Hash Function 2019/4/15