簡潔データ構造

簡潔データ構造 (かんけつデータこうぞう、) とは計算機科学の用語で、情報理論的下界に「近い」領域量だけを使いつつ、（他の圧縮形式とは異なり）効率的に質問を受け付けることができるデータ構造を指す。その概念は最初 Jacobson によって、木、平面的グラフを符号化するために導入された。通常のロスなしデータ圧縮アルゴリズムとは異なり、簡潔データ構造は事前の展開操作をせずに使用することができる。は関連する考え方に基づいているが、圧縮データ構造ではデータ構造のサイズは表現しようとする特定のデータに依存する。
あるデータを保持するために必要な情報理論的に最小のビット数がformula_1だとする。このデータの表現形式は、
であると呼ばれる。
implicit データ構造は通常、なんらかの順列を用いて情報を保持することに帰着される。よく知られる事例としてはヒープが挙げられる。
簡潔辞書.
簡潔索引つき辞書(簡潔ビットベクトル、完備辞書とも呼ぶ)は、"rank/select" 辞書とも呼ばれ、二分木、formula_5分木、多重集合や、接尾辞木、接尾辞配列などの多数の簡潔表現手法の基礎をなしている。基本的な問題設定は、 formula_6の空間中で部分集合formula_7を保持するというものであり、通常 formula_8 iff formula_9 とするビット配列として部分集合を表現する。索引つき辞書は通常の辞書の操作（参照、および動的辞書の場合は挿入と削除）に加えて、次の二つの操作をサポートする。
ただし、formula_12とする。
ある単純な表現方法 では formula_13 ビットの領域（元のビット配列と、formula_14 の補助データ構造）を使って rank と select を定数時間でサポートできる。この方法はと似た考え方に基づいており、固定サイズの部分問題に行き着くまでに定数回数の再帰呼び出しだけで済む。ビット配列 formula_15 はサイズ formula_16 の"大ブロック"とサイズformula_17の"小ブロック"に分割される。大ブロック一つごとに、最初のビットのrankが別の表 formula_18 に保持される。この表の各エントリには formula_19 ビットが必要で、合計 formula_20 ビットの領域を使う。大ブロックの中では、もう一つの表 formula_21 を使って、そのブロックに含まれる formula_22 個の小ブロックのrankを保持する。ここでの違いは、各エントリで、そのエントリが入っている大ブロックの最初のビットのrankからの差分だけを保持すればよいので、 formula_23 ビットだけが必要になることである。このため、この表は合計 formula_24 ビットになる。そして、小ブロック内の formula_25 ビットに対しては、formula_26 ビットの全てのビット列に対するrank質問の答えを保持するルックアップ表 formula_27 を使うことができる。このテーブルには formula_28 ビットの領域を必要とする。 これらの補助表は formula_14 の領域だけを使うため、このデータ構造はrank質問を formula_30 時間と formula_13 ビットの領域でサポートする。
次の定数時間アルゴリズムを用いると、formula_32の質問に定数時間で答えることができる。
formula_33
実用上は、ルックアップ表 formula_27 をビット命令とより小さい表で置き換え、小ブロックで立っているビットの数を調べるようにすることができる。多くの場合、こうすることで大きなデータセットで簡潔データ構造を用いる際の、キャッシュミスの増大とそれによって起こるルックアップ表がキャッシュから追い出されるという問題に対処できる。select質問は、"rank"に用いたものと同じ補助データ構造と二分探索とを合わせることで容易にサポートできるが、そのやり方では最悪の場合 formula_35 の時間がかかる。formula_36 ビットの追加領域を用いる、より複雑なデータ構造により、selectは定数時間でサポートできる。こうした解決法の多くでは、実用上、漸近的な特長が効果を発揮する至らない場合、formula_37記法に隠れた定数が支配的となる。その場合、長ワード命令とワードサイズに揃えたブロックを利用した実装のほうが効率的であることが多い。
エントロピー圧縮型辞書.
formula_13 の領域のアプローチは、 formula_39 のなかには異なる formula_40-部分集合が（言い換えるなら、長さformula_41でちょうどformula_40個の1があるビット列が）formula_43 個あることに注意すると、さらに改善できる。このとき、formula_15を保持するのに必要なビット数の情報理論的下界は、formula_45である。この下界を達成する（静的な）簡潔辞書は存在し、 必要とする領域はformula_46 である。そのデータ構造はさらに、formula_47の領域量でrankとselectをサポートするように拡張することができる。この下界は、辞書を保持する領域を formula_48 とし、質問に必要な時間を formula_49 とすることで領域と時間のトレードオフに帰着させることができる。
応用例.
可変長のアイテムの列を符号化する必要がある場合は、単に個々のアイテムを区切り記号なしで順に並べればよい。それと別に、アイテムの始まりの位置に1を、それ以外の位置に0を置いた二値配列を符号化する。この補助ビット列で formula_50 関数を用いるとあるインデクス値のアイテムの開始位置を高速に求めることができる。
別の例として二分木の表現がある。ノード数formula_41のあらゆる二分木は、親の参照、左右の子の参照、部分木のサイズの取得など、各ノードに対する多数の操作を定数時間でサポートしながら formula_52 ビットで表現できる。 ノード数 formula_41 の異なる二分木の数は formula_54formula_55 である。大きな formula_41 に対しては、これはおよそ formula_57 にしたがう。このため、符号化には少なくともおよそ formula_58 ビットが必要である。したがって簡潔二分木に必要な領域量はノードごとに formula_59 ビットである。