簡潔データ構造のソースを表示

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

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

* <math>Z + O(1)</math>ビットの領域を必要とする場合、''{{仮リンク|インプリシットなデータ構造|en|implicit data structure|label=implicit}}''、
* <math>Z + o(Z)</math>ビットの領域を必要とする場合、''簡潔'' (''succinct'')、
* <math>O(Z)</math>ビットの領域を必要とする場合、''コンパクト'' (''compact'')

であると呼ばれる。

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

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

* <math>\mathbf{rank}_q(x) = |\{ k \in [0 \dots x) : B[k] = q \}|</math>
* <math>\mathbf{select}_q(x)= \min \{k \in [0 \dots n) : \mathbf{rank}_q(k) = x\}</math>

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

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

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

<math>\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]</math>

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

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

==応用例==
可変長のアイテムの列を符号化する必要がある場合は、単に個々のアイテムを区切り記号なしで順に並べればよい。それと別に、アイテムの始まりの位置に1を、それ以外の位置に0を置いた二値配列を符号化する。この補助ビット列で <math>select</math> 関数を用いるとあるインデクス値のアイテムの開始位置を高速に求めることができる<ref>{{cite web|url=https://cmph.sourceforge.net/papers/esa09.pdf |title=Hash, displace, and compress|last=Belazzougui|first=Djamal|accessdate=2011-12-30}}</ref>。

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

==参考文献==
<references>
<ref name="jacobson1988succinct">
{{Cite journal
| last = Jacobson
| first = G. J
| title = Succinct static data structures
| year = 1988
}}
</ref>
<ref name="raman2002succinct">
{{Cite conference
| isbn = 089871513X
| pages = 233–242
| last = Raman
| first = R.
| first2=V.|last2=Raman|first3=S.S.|last3=Rao
| title = Succinct indexable dictionaries with applications to encoding k-ary trees and multisets
| book-title = Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms
| date = 2002
| url = http://www.cs.cmu.edu/afs/cs.cmu.edu/project/aladdin/wwwlocal/hash/RaRaRa02.pdf
}}
</ref>
<ref name="sadakane2006squeezing">
{{Cite conference
| isbn = 0898716055
| pages = 1230–1239
| last = Sadakane
| first = K.
| first2=R.|last2=Grossi
| title = Squeezing succinct data structures into entropy bounds
| book-title = Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm
| date = 2006
| url = http://www.dmi.unisa.it/people/cerulli/www/WSPages/WSFiles/Abs/S3/S33_abs_Grossi.pdf
}}
</ref>
<ref name="jacobson1989space">
{{Cite journal
| last = Jacobson
| first = G.
| title = Space-efficient static trees and graphs
| year = 1989
| url = http://www.cs.cmu.edu/afs/cs/project/aladdin/wwwlocal/compression/00063533.pdf
}}
</ref>
<ref name="gonzález2005practical">
{{Cite conference
| pages = 27–38
| last = González
| first = R.
| first2=S.|last2=Grabowski |first3=V. |last3=Mäkinen |first4=G. |last4=Navarro
| title = Practical implementation of rank and select queries
| book-title = Poster Proceedings Volume of 4th Workshop on Efficient and Experimental Algorithms (WEA)
| date = 2005
| url = http://www.dcc.uchile.cl/~gnavarro/algoritmos/ps/wea05.pdf
}}
</ref>
<ref name="clark1998compact">
{{Cite journal
| last = Clark
| first = D.
| title = Compact pat trees
| year = 1998
| url = https://uwspace.uwaterloo.ca/bitstream/10012/64/1/nq21335.pdf
}}
</ref>
<ref name="vigna2008broadword">
{{Cite journal
| pages = 154–168
| last = Vigna
| first = S.
| title = Broadword implementation of rank/select queries
| journal = Experimental Algorithms
| year = 2008
| url = http://sux.dsi.unimi.it/paper.pdf
}}
</ref>
<ref name="brodnik1999membership">
{{Cite journal
| volume = 28
| issue = 5
| pages = 1627–1640
| last = Brodnik
| first = A.
| coauthors = J. I Munro
| title = Membership in constant time and almost-minimum space
| journal = SIAM J. Comput.
| year = 1999
| url = http://www.cs.cmu.edu/afs/cs.cmu.edu/project/aladdin/wwwlocal/compression/BM99.pdf
| doi = 10.1137/S0097539795294165
}}
</ref>
<ref name="patrascu2008succincter">
{{Cite conference
| pages = 305–313
| last = Patrascu
| first = M.
| title = Succincter
| book-title = Foundations of Computer Science, 2008. FOCS'08. IEEE 49th Annual IEEE Symposium on
| date = 2008
| url = http://people.csail.mit.edu/mip/papers/succinct/succinct.pdf
}}
</ref>
</references>

==推奨文献==
*{{cite journal|和書
| pages = 899-902
| title = 大規模データ処理のための簡潔データ構造
| author = 定兼邦彦
| journal = 情報処理
| year = 2007
| month = 8
| volume = 48
| issue = 8
| url = http://id.nii.ac.jp/1001/00065880/
| CRID=1050001337898050048
| id={{国立国会図書館書誌ID|8923108}}
}}
*{{cite journal|和書
| pages = 689-691
| title = 私のブックマーク：簡潔データ構造
| author = 田部井靖生
| journal = 人工知能学会誌
| year = 2011
| month = 11
| volume = 26
| issue = 6
| url = https://www.ai-gakkai.or.jp/resource/my-bookmark/my-bookmark_vol26-no6/
}}
* 定兼邦彦：「簡潔データ構造」、共立出版、ISBN 978-4-320-12174-4、（2018年2月25日）。数少ない日本語の教科書


{{DEFAULTSORT:かんけつてたこうそう}}
[[Category:簡潔データ構造|*]]
[[Category:データ構造]]