簡潔データ構造

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

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

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

であると呼ばれる。

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

簡潔辞書

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

  • r a n k q ( x ) = | { k ∈ [ 0 … x ) : B [ k ] = q } | {\displaystyle \mathbf {rank} _{q}(x)=|\{k\in [0\dots x):B[k]=q\}|}
  • s e l e c t q ( x ) = min { k ∈ [ 0 … n ) : r a n k q ( k ) = x } {\displaystyle \mathbf {select} _{q}(x)=\min\{k\in [0\dots n):\mathbf {rank} _{q}(k)=x\}}

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

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

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

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

エントロピー圧縮型辞書

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

応用例

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

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

参考文献

  1. ^ Jacobson, G. J (1988). Succinct static data structures. 
  2. ^ a b Raman, R.; Raman, V.; Rao, S.S. (2002). "Succinct indexable dictionaries with applications to encoding k-ary trees and multisets" (PDF). Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms. pp. 233–242. ISBN 089871513X。
  3. ^ Sadakane, K.; Grossi, R. (2006). "Squeezing succinct data structures into entropy bounds" (PDF). Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm. pp. 1230–1239. ISBN 0898716055。
  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.; Grabowski, S.; Mäkinen, V.; Navarro, G. (2005). "Practical implementation of rank and select queries" (PDF). Poster Proceedings Volume of 4th Workshop on Efficient and Experimental Algorithms (WEA). pp. 27–38.
  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" (PDF). Foundations of Computer Science, 2008. FOCS'08. IEEE 49th Annual IEEE Symposium on. pp. 305–313.
  10. ^ Belazzougui, Djamal. “Hash, displace, and compress”. 2011年12月30日閲覧。

推奨文献

  • 定兼邦彦「大規模データ処理のための簡潔データ構造」『情報処理』第48巻第8号、2007年8月、899-902頁、CRID 1050001337898050048、国立国会図書館書誌ID:8923108。 
  • 田部井靖生「私のブックマーク：簡潔データ構造」『人工知能学会誌』第26巻第6号、2011年11月、689-691頁。 
  • 定兼邦彦：「簡潔データ構造」、共立出版、ISBN 978-4320121744、（2018年2月22日）。