簡潔データ構造超入門VI 〜これまでのまとめと集合の簡潔構造〜

今回は集合の簡潔構造について話をする。今回で簡潔構造の初歩的な話は一段落となるので、いままでの話をまとめつつ集合の簡潔構造とは?どういうことに使えるのか?という話をする。
集合の簡潔構造は大変重要で、ここを理解すれば簡潔構造の基礎はだいたいOKといえる。

前回までの記事:
簡潔データ構造超入門 〜つくって学ぶ簡潔ビットベクトル〜 - EchizenBlog-Zwei
簡潔データ構造超入門II 〜ちょっとだけ実用的な簡潔ビットベクトル〜 - EchizenBlog-Zwei
簡潔データ構造超入門III 〜簡潔ビットベクトルで転置インデックスを効率的に実装する〜 - EchizenBlog-Zwei
簡潔データ構造超入門IV 〜LOUDSというメモリ効率のよい木構造の話(準備編)〜 - EchizenBlog-Zwei
簡潔データ構造超入門V 〜LOUDSというメモリ効率のよい木構造の話(本編)〜 - EchizenBlog-Zwei


初回(I)の記事で疎ベクトル(いくつかの次元にしか値が入っていないベクトル)を簡潔ビットベクトルで表現すると嬉しいことがあるよ、という話をした。例えば

0, 5, 0, 3, 6, 0, 0, 2

という8次元のベクトルがあったときに簡潔ビットベクトルは

01011001

のような値の入っている次元だけビットの立っているビット列になる。これとは別に

5362

のように値が入っている部分の数字を列挙したもの(とりあえず密データ列と呼んでおく)も別途もっておく。簡潔ビットベクトルと密データ列だけもたせた場合、単純にベクトル表現するよりメモリ効率が良いという話だった。
さて簡潔ビットベクトルは

rank(x)  : x番目のビット以前(xの位置を含む)の立っているビットの数
select(i): i番目に立っているビットの位置

という二つの操作ができる。rank(次元)とすると密データ列の何番目の要素をみればよいかわかり、select(密データの添字)とするとその値がどの次元に対応するものかがわかる。という話だった(selectの話は(II)で説明した)。


さて、ここで集合の簡潔構造を説明する。ビットベクトルのデータ構造は具体的なビット列に対して定義されたデータ構造だったので、すみやかにプログラムにすることができた。
一方で集合の簡潔構造は集合(set)に対してrank/selectの機能が提供される、というだけで具体的なデータ構造の形式は決まっていない。集合というのは

0からnまでの範囲の自然数のうち重複を許してm個の要素を持ったもの

例:
1, 2, 2, 4
2, 3, 5
0, 5, 5, 6, 6

であり

rank(x): xより小さいの値の数を返す
selecti): i番目に小さい値を返す

というrank/selectが定義される。この定義を見てピンときた方もいるかもしれないが、記事(III〜V)で解説した単調増加列をunaryで表現したものが、まさしく集合の簡潔構造となっている。unaryにはビットベクトルのrank/selectを用いて

rank0(select(x)): xより小さいの値の数を返す
rank(select0(i)) : i番目の値を返す

という操作が定義されていたが、これはそれぞれ集合のrank/selectに対応する。というわけで集合の簡潔構造があれば簡潔木であるLOUDSが実装できる。このとき簡潔集合としてunaryのビットベクトルを用いる必要は必ずしもない(私が開発しているerila-trieは簡潔集合として岡野原氏の提案するvertical nodeを採用している。vertical codeは(集合の)rankは遅いが、selectが高速という特徴がある。トライ木ではselectのほうが利用頻度が高いため簡潔構造としてvertical codeを採用した)。


さて集合の簡潔構造は具体的な実装としていろいろあるが、unaryよりももっとシンプルなものがある。それは簡潔ビットベクトルをそのまま使うやり方。初回で疎ベクトルを例に出したが疎ベクトルの値が入っている要素を集合の要素と考えると、集合の簡潔構造とすることができる。このときrank/selectはそのままビットベクトルのrank/selectに対応する。
じゃあビットベクトルをそのまま使ったらいいじゃん。なんでunaryとか面倒な話をしたの?となるかもしれない。実はビットベクトルをそのまま使うと値を重複して持つことができない(同じ次元は複数ないので)。ところがunaryなら同じ次元が複数持てる。
LOUDSではリーフノードが子ノードを持たないため子ノードの累計値に同じものが並ぶケースがあるためunaryを使わざるを得なかった、という話(もちろんvertical codeも重複して要素を持てる)。
このように集合が重複を許すかどうかは重要で、重複を許さない集合をset、許す集合をmultisetなどと区別したりする。ちなみにとりうる値の総数をn、集合に含む要素数をm個としたときビットベクトルはnビット、unaryはn+mビット必要となる。従って重複がないことがわかっている場合はビットベクトルでそのまま表現した方がメモリ効率が良い。
最後に。重複あり集合のデータ構造としては最近では以下の論文で提案されている4つの手法が優れている。読みやすい論文なので興味のある方は読むとよいかも(vertical codeもこの論文に解説がある)。

Practical Entropy-Compressed Rank/Select Dictionary
D. Okanohara, and K. Sadakane; ALENEX2007

というわけでここまでで一段落。簡潔集合(とビットベクトルを含めた代表的な実装方法)を理解すれば現在の簡潔データ構造の入門としては十分な気がする。
ただちに応用可能な簡潔構造としてはLOUDSとウェーブレット木が有名で前者は記事(VI、V)で解説した。ウェーブレット木はビットベクトルを0/1ではなく任意の値に拡張したもので文字列に対してrank/selectをすることが可能になっている。BWT変換した文字列の検索が高速に可能なので全文検索(FM-Indexなど)に利用されている。ウェーブレット木については機会があればそのうち記事を書く。
また簡潔データ構造については定兼氏による以下の講義資料が非常に充実しているので、ぜひ参考にされたい。

http://researchmap.jp/sada/succinct/