簡潔データ構造

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

簡潔データ構造 (かんけつデータこうぞう、: succinct data structure) とは計算機科学の用語で、情報理論的下界に「近い」領域量だけを使いつつ、(他の圧縮形式とは異なり)効率的に質問を受け付けることができるデータ構造を指す。その概念は最初 Jacobson [1] によってビット配列英語版平面的グラフを符号化するために導入された。通常のロスなしデータ圧縮アルゴリズムとは異なり、簡潔データ構造は事前の展開操作をせずに使用することができる。圧縮データ構造英語版は関連する考え方に基づいているが、圧縮データ構造ではデータ構造のサイズは表現しようとする特定のデータに依存する。

あるデータを保持するために必要な情報理論的に最小のビット数がZだとする。このデータの表現形式は、

  • Z + O(1)ビットの領域を必要とする場合、implicit英語版
  • Z + o(Z)ビットの領域を必要とする場合、簡潔 (succinct)、
  • O(Z)ビットの領域を必要とする場合、コンパクト (compact)

であると呼ばれる。

implicit データ構造は通常、なんらかの順列を用いて情報を保持することに帰着される。よく知られる事例としてはヒープが挙げられる。

簡潔辞書[編集]

簡潔索引つき辞書は、rank/select 辞書とも呼ばれ、二分木k分木、多重集合[2]や、接尾辞木接尾辞配列などの多数の簡潔表現手法の基礎をなしている[3]。基本的な問題設定は、 U = [0 \dots n) = \{0, 1, \dots, n - 1\}の空間中で部分集合Sを保持するというものであり、通常 B[i] = 1 iff i \in S とするビット配列として部分集合を表現する。索引つき辞書は通常の辞書の操作(参照、および動的辞書の場合は挿入と削除)に加えて、次の二つの操作をサポートする。

  • \mathbf{rank}_q(x) = |\{ k \in [0 \dots x) : B[k] = q \}|
  • \mathbf{select}_q(x)= \min \{k \in [0 \dots n) : \mathbf{rank}_q(k) = x\}

ただし、q \in \{0, 1\}とする。

ある単純な表現方法 [4] では n + o(n) ビットの領域(元のビット配列と、o(n) の補助データ構造)を使って rankselect を定数時間でサポートできる。この方法はRange Minimum Query英語版と似た考え方に基づいており、固定サイズの部分問題に行き着くまでに定数回数の再帰呼び出しだけで済む。ビット配列 B はサイズ l = \lg^2 n大ブロックとサイズs = \lg n / 2小ブロックに分割される。大ブロック一つごとに、最初のビットのrankが別の表 R_l[0 \dots n/l) に保持される。この表の各エントリには \lg n ビットが必要で、合計 (n/l) \lg n = n / \lg n ビットの領域を使う。大ブロックの中では、もう一つの表 R_s[0 \dots l/s) を使って、そのブロックに含まれる l/s = 2 \lg n 個の小ブロックのrankを保持する。ここでの違いは、各エントリで、そのエントリが入っている大ブロックの最初のビットのrankからの差分だけを保持すればよいので、 \lg l = \lg \lg^2 n = 2 \lg \lg n ビットだけが必要になることである。このため、この表は合計 (n/s) \lg l = 4 n \lg \lg n / \lg n ビットになる。次にルックアップ表 R_p を使って、ビット列 s for i \in [0, s)に対して可能なすべてのrank質問の答えを保持することができる。これには 2^s s \lg s = O(\sqrt{n} \lg n \lg \lg n) ビットの領域を必要とする。これらの補助表は o(n) の領域だけを使うため、このデータ構造はrank質問を O(1) 時間と n + o(n) ビットの領域でサポートする。

次の定数時間アルゴリズムを用いると、\mathbf{rank}_1(x)の質問に定数時間で答えることができる。

\mathbf{rank}_1(x) = R_l[\lfloor x / l \rfloor] + R_s[\lfloor x / s\rfloor] + R_p[x \lfloor x / s\rfloor, x \text{ mod } s]

実用上は、ルックアップ表 R_p をビット命令とより小さい表で置き換え、小ブロックで立っているビットの数を調べるようにすることができる。多くの場合、こうすることで大きなデータセットで簡潔データ構造を用いる際の、キャッシュミスの増大とそれによって起こるルックアップ表がキャッシュから追い出されるという問題に対処できる[5]。select質問は、rankに用いたものと同じ補助データ構造と二分探索とを合わせることで容易にサポートできるが、そのやり方では最悪の場合 O(\lg n) の時間がかかる。3n/\lg \lg n + O(\sqrt{n} \lg n \lg \lg n) = o(n) ビットの追加領域を用いる、より複雑なデータ構造により、selectは定数時間でサポートできる[6]。こうした解決法の多くでは、実用上、漸近的な特長が効果を発揮する至らない場合、O(\cdot)記法に隠れた定数が支配的となる。その場合、長ワード命令とワードサイズに揃えたブロックを利用した実装のほうが効率的であることが多い[7]

エントロピー圧縮型辞書[編集]

n + o(n) の領域のアプローチは、 [n) のなかには異なる m-部分集合が(言い換えるなら、長さnでちょうどm個の1があるビット列が)\textstyle \binom{n}{m} 個あることに注意すると、さらに改善できる。このとき、Bを保持するのに必要なビット数の情報理論的下界は、\textstyle \mathcal{B}(m,n) = \lceil \lg \binom{n}{m} \rceilである。この下界を達成する(静的な)簡潔辞書は存在し、 必要とする領域は\mathcal{B}(m,n) + o(\mathcal{B}(m,n)) である[8]。そのデータ構造はさらに、\mathcal{B}(m,n) + O(m + n \lg \lg n / \lg n)の領域量でrankselectをサポートするように拡張することができる[2]。この下界は、辞書を保持する領域を \mathcal{B}(m,n) + O(n t^t / \lg^t n + n^{3/4}) とし、質問に必要な時間を O(t) とすることで領域と時間のトレードオフに帰着させることができる[9]

応用例[編集]

可変長のアイテムの列を符号化する必要がある場合は、単に個々のアイテムを区切り記号なしで順に並べればよい。それと別に、アイテムの始まりの位置に1を、それ以外の位置に0を置いた二値配列を符号化する。この補助ビット列で select 関数を用いるとあるインデクス値のアイテムの開始位置を高速に求めることができる[10]

別の例として二分木の表現がある。ノードnのあらゆる二分木は、親の参照、左右の子の参照、部分木のサイズの取得など、各ノードに対する多数の操作を定数時間でサポートしながら 2n + o(n) ビットで表現できる。 ノード数 n の異なる二分木の数は {\tbinom{2n}{n}}/(n+1) である。大きな n に対しては、これはおよそ 4^n にしたがう。このため、符号化には少なくともおよそ \log_2(4^n)=2n ビットが必要である。したがって簡潔二分木に必要な領域量はノードごとに 2 ビットである。

参考文献[編集]

  1. ^ Jacobson, G. J (1988). Succinct static data structures. 
  2. ^ a b Raman, R.; V. Raman, S. S Rao (2002). “Succinct indexable dictionaries with applications to encoding k-ary trees and multisets”. Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms. pp. 233–242. ISBN 089871513X. http://www.cs.cmu.edu/afs/cs.cmu.edu/project/aladdin/wwwlocal/hash/RaRaRa02.pdf 
  3. ^ Sadakane, K.; R. Grossi (2006). “Squeezing succinct data structures into entropy bounds”. Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm. pp. 1230–1239. ISBN 0898716055. http://www.dmi.unisa.it/people/cerulli/www/WSPages/WSFiles/Abs/S3/S33_abs_Grossi.pdf 
  4. ^ Jacobson, G. (1989). Space-efficient static trees and graphs. http://www.cs.cmu.edu/afs/cs/project/aladdin/wwwlocal/compression/00063533.pdf. 
  5. ^ González, R.; S. Grabowski, V. Mäkinen, G. Navarro (2005). “Practical implementation of rank and select queries”. Poster Proceedings Volume of 4th Workshop on Efficient and Experimental Algorithms (WEA). pp. 27–38. http://www.dcc.uchile.cl/~gnavarro/algoritmos/ps/wea05.pdf 
  6. ^ Clark, D. (1998). Compact pat trees. https://uwspace.uwaterloo.ca/bitstream/10012/64/1/nq21335.pdf. 
  7. ^ Vigna, S. (2008). “Broadword implementation of rank/select queries”. Experimental Algorithms: 154–168. http://sux.dsi.unimi.it/paper.pdf. 
  8. ^ Brodnik, A.; J. I Munro (1999). “Membership in constant time and almost-minimum space”. SIAM J. Comput. 28 (5): 1627–1640. doi:10.1137/S0097539795294165. http://www.cs.cmu.edu/afs/cs.cmu.edu/project/aladdin/wwwlocal/compression/BM99.pdf. 
  9. ^ Patrascu, M. (2008). “Succincter”. Foundations of Computer Science, 2008. FOCS'08. IEEE 49th Annual IEEE Symposium on. pp. 305–313. http://people.csail.mit.edu/mip/papers/succinct/succinct.pdf 
  10. ^ Belazzougui, Djamal. “Hash, displace, and compress”. 2011年12月30日閲覧。

推奨文献[編集]