大規模キー集合の 効率的な格納手法 tx bep 2007/10/31@Google 東京 大規模キー集合の 効率的な格納手法 tx bep 岡野原　大輔 東京大学

概要 大量のキーを操作するためのライブラリを二つ紹介し，その中で利用されている技術について解説 tx bep LOUDS（木の簡潔データ構造） bep 最小完全ハッシュ関数

背景 (1/3) キー: 任意長の文字列 多くのデータ構造, アプリケーションの肝 大規模なキー集合を扱う必要性 例：人名, URL, 特徴関数名, 座標情報 多くのデータ構造, アプリケーションの肝 連想配列 (C++ STL map)やDB キーを使って様々な操作を行う 大規模なキー集合を扱う必要性 数億, 数十億規模のキーを扱いたい 通常は、ディスク上に置いておく

背景 (2/3) 簡潔データ構造 実行時間 と 作業領域量が最適なデータ構造 非常に巨大なデータ構造をメモリ上で扱える 殆どの操作の実行時間はO(1) 作業領域量は情報理論的下限に漸近する，つまり 　L通りあるデータ構造を(1+o(n)) logL bitsで表現 データ圧縮とは違い，事前の復元は必要無い データ構造例：ビット配列，木，文字列，グラフ 非常に巨大なデータ構造をメモリ上で扱える

背景 (3/3) Rank/Select辞書 ビット配列に対する簡潔データ構造 ビット配列 B[0…n-1]に二つの操作 rankc(B,i) : B[0…i]中のcの数を返す selectc(B,i) : (i+1)番目のcの位置を返す 例 　　 rank1(B, 6) = 5 select0(B, 1) = 4 rank, select操作付きビット配列はnH0+o(n) bitsの作業領域量でO(1) timeで実現可能 [Okanohara+ 07] 0 1 2 3 4 5 6 7 8 9 10 1 0 1 1 0 1 1 1 0 1 1 B

従来のデータ構造のおさらい 赤黒木 (C++ STL map, Java Treemap) 平衡二分木．各ノードがキー（必要であれば値も）を管理．木の深さは一定． ハッシュ(C++ STL hash_map, Java Hashmap) キーのハッシュ値をバケット番号として扱う．衝突は適宜解決

従来データ構造の問題点 木構造を扱う場合 ハッシュ関数の場合 作業領域量が大きい．1ノードあたり，親，最初の子，次の兄弟を持つだけで sizeof(int)*3 バイト ハッシュ関数の場合 衝突を解決するのが大変． キャッシュミスを少なくするためにキーをまとめて持つ方法も提案 “Cache-conscious Collision Resolution in String Hash Tables”, N. Askitis, 2005

tx: 木の簡潔データ構造を 用いたTrieライブラリ

Trie (prefix tree) 木構造．枝に文字がついている．根から葉へのパスが各キーに対応． 共通接頭辞を持つキーをまとめて検索可能 w i e o n e a n n キー : "to", "tea", "ten", "i", "in", "inn“, and “we”.

Tx: Succinct Trie Data Structure 枝の文字情報を一つの配列で保存 作業領域量はキーを全てつなげた時のサイズの約半分 Trieの各種操作はそのまま実現できる

木の簡潔データ構造 節点*数nの順序木Tnは2n bitで表現可能 次の操作をO(1)timeで実現 Tnの種類数はカタラン数Cn log2Cn ≒ 2n 従来のポインタ手法はO(n log n) bit 次の操作をO(1)timeで実現 親, 子, 兄弟を辿る, 深さ, 子の数, 子孫の数, ノード番号, 二つのノード間のLCA など * 本発表中は葉も子が0個の節点だとする

木をBFSで辿り，k次のノードを行きがけに k個の’1 ‘と1個の’0’で表す LOUDS: Level-Ordered Unary Degree Sequence [Jacobson 89, O’Neil Delpratt 06] 木をBFSで辿り，k次のノードを行きがけに k個の’1 ‘と1個の’0’で表す 先頭にSuper Root S（番人）を追加 n個の節点からなる順序木にはn個の1, n+1個の0が出現する 1 3 S 1 2 3 4 5 6 7 8 2 10 110 1110 110 0 0 0 0 0 4 5 6 7 8

LOUDS (続) i番目の節点は1と0の2回表現されている 今回はi番目の節点とi番目の1を対応させる 3 2 S 1 2 3 4 5 6 7 8 10 110 1110 110 0 0 0 0 0 4 5 6 7 8 5番目の1 (5+1)番目の0

LOUDS上での操作 B[i]に対応するノードに対する各操作 10 110 1110 110 0 0 0 0 0 最初の子 = select0(B, rank1(B,i)-1) + 1 最後の子 = select0(B, rank1(B,i)) - 1 親 = select1(B, rank0(B,i)-1) 次の兄弟 = i+1 1 S 1 2 3 4 5 6 7 8 3 2 10 110 1110 110 0 0 0 0 0 4 5 6 7 8 実際確かめてみよう 2

Trieの枝情報の表現 E[i] = i+2番目の節点に向かう枝の文字 枝にcが付いている子を探す場合 Eは長さn-1の配列 枝にcが付いている子を探す場合 for (int j = rank1(B,i)-2; B[i] != 0; i++, j++) if (e[j] == c) break; // found c 1 S 1 2 3 4 5 6 7 8 a c 3 10 110 1110 110 0 0 0 0 0 2 d b b a c 4 5 6 7 8 E = [acbcdab]

Q[] = “ad”を検索する例 初期状態 i = 2; // root 10 110 1110 110 0 0 0 0 0 j = rank1(B, i)-2; // 0 E[0], E[1],..,を探す E[0]でaが見つかる i = select0(B, rank1(B,i)-1) + 1 + 0; // 5 j = rank1(B, i); // 2 E[2], E[3], …, を探す E[4]でdが見つかる 1 S 1 2 3 4 5 6 7 8 a c 3 10 110 1110 110 0 0 0 0 0 2 d b b a c E = [acbcdab] 4 5 6 7 8

Trieの格納情報の表現 T[i] = i+1番目のノードに情報を格納している場合は1, そうでない場合は0の配列 格納した情報は配列A[0..]に入れておき、 i番目のノード情報へのアクセスは A[rank1(B, i) – 2] と行える 1 S 1 2 3 4 5 6 7 8 a c 3 10 110 1110 110 0 0 0 0 0 2 d b b a c E = [acbcdab] 4 5 6 7 8 T = [1011111]

実験 入力データ Web 1T 5-gram Version 1 1gramのリストから出現頻度を除いたもの キーワード種類数: 13,588,391 キーワードの総長: 112,349,445 bytes trie中の葉も含めたノード数: 34,722,820

BP (Balanced Parenthesis Encoding) 木をDFSで辿り，ノードの行きがけに，’(‘, 帰りがけに’)’ を書く（LISP等のS式) DFUDS (Depth-First Unary Degree Sequence) 木をDFSで辿り，ノードの行きがけに, k次のノードを k個の’(‘と1個の’)’で表す 各ノードの次数をUnary Codeで表現 1 6 2 3 4 5 7 8 順序木の例 (番号はDFSの行きがけ順）

bep: 最小完全ハッシュ関数を利用した連想配列

bep: MPHFを利用した連想配列 ハッシュベースの連想配列 最小完全ハッシュ関数を利用 単純な登録・参照のみを扱う キー順序は保存しない キー集合に対する キーの追加，削除はバッチ的に行う

最小完全ハッシュ関数 (MPHF: Minimal Perfect Hash Function) 単純なアプローチでは作れない n個のキーで偶然できる確率は n! / nn ≒ e-n

PHFの構築手法 (1/3) [Botelho+ 07] n個のキー k1 k2… knに対し，[0..m-1] (n≦m)を値域とするPHFを構築する 二つの独立なハッシュ関数h1, h2を用意 h1は[0..m/2) に， h2は[m/2 .. m)に写像するようなハッシュ関数 グラフG={V,E}を考える． 頂点 V = {0,…,m-1} 枝　 ei = (h1(ki), h2(ki)) (i=1…n) 2部グラフであり、枝の数はn個

PHFの構築手法 (2/3) 各枝につき，頂点を1つずつ割り当てる この時，割り当てた頂点が重複しないようにする グラフGに閉路が無いなら必ず重複しないように割り当てられる． この割り当てが，各枝と対応するキーのハッシュ値になる 1 2 3 4 5 2 7 6 4 3 8 5 6 7 8 9

PHFの構築手法 (3/3) 先程の割り当てが行えるように各頂点vについて番号g(v)∈{0,1}を付ける 最終的なハッシュ関数は次の通り 先程割り当てた順の逆順につけてく 最終的なハッシュ関数は次の通り g 1 1 2 3 4 5 2 7 6 4 3 8 5 6 7 8 9 g 1 1 1

PHFが構築できる確率 ランダムに構築した2部グラフに閉路が無いなら構築成功 m = 2.09n の時 閉路が無い確率は約0.29 3種類のハッシュ関数を使い， 3-ハイパーグラフを利用しても同様のことができる m = 1.23n の時 閉路が無い確率はほぼ1

PHFからMPHF 今回構築したPHFは既にかなり密 rank関数を利用しMPHFにする m=1.23n, 値域のうち1/1.23はキー B[0…m-1] B[i]=1, iにキーがある, B[i]=0 キーが無い

bep （キーを除いた）最終的なデータ構造 問題点：キー自体をどう保存するか h1 h2に利用したパラメータ g[0…m-1] (それぞれ2bit) B[0…m-1] m bit 合計 1 keyあたり 約3bit c.f. 完全ハッシュ関数を保存する下限は約1.4n bit 問題点：キー自体をどう保存するか 知らないキーをNOTFOUNDと返せない

キーの保存方法 現在は全てのキーをそのまま保存 キー自身の圧縮を検討中 i番目のエントリには，p(kj)=iであるkjをおき、p(k’)番目のエントリとk’を比較 ハッシュ関数自身に比べはるかに大きい キー自身の圧縮を検討中 prefixとsuffixの冗長性を利用する

まとめ/今後の課題 大規模キー集合を扱うためのライブラリ tx, bep とその背後の技術を紹介した ライブラリはまだまだ未成熟で発展途上 LOUDなどの簡潔データ構造、MPHFなどは他のアプリケーションにも利用可能 ライブラリはまだまだ未成熟で発展途上 いろんな言語でサポートしたい 構築、更新、分散などさぼっているところはいくらでもある もし良かったら使ってみてください “tx trie” で検索してください

Reference http://www-tsujii.is.s.u-tokyo.ac.jp/~hillbig/tx-j.htm http://www-tsujii.is.s.u-tokyo.ac.jp/~hillbig/bep-j.htm D. Okanohara, K. Sadakane, Practical Entropy-Compressed Rank/Select Dictionary. ALENEX 2007. O. Delpratt, N. Rahman, R. Raman. Engineering the LOUDS Succinct Tree Representation. WEA 2006. F.C Botelho, R. Pagh, N. Ziviani. Simple and Space-Efficient Minimal Perfect Hash Functions WADS 2007