簡潔なデータ構造

コンピュータサイエンスにおいて、簡潔なデータ構造とは、情報理論の下限に「近い」量の空間を使用するデータ構造ですが、（他の圧縮表現とは異なり）効率的なクエリ操作が可能です。この概念は、もともとジェイコブソン^{[1]によって}ビットベクトル、（ラベルなしの）ツリー、および平面グラフをエンコードするために導入されました。一般的なロスレスデータ圧縮アルゴリズムとは異なり、簡潔なデータ構造では、最初に解凍することなく、その場で使用することができます。関連する概念として、圧縮データ構造があります。これは、格納またはエンコードされたデータのサイズが、データ自体の特定のコンテンツに同様に依存しているという点で共通しています。

あるデータを格納するために必要な情報理論的最適ビット数を 仮定します。このデータの表現は次のように呼ばれます。${\displaystyle Z}$

• 暗黙的に、スペースを少し取る場合は${\displaystyle Z+O(1)}$
• スペースを少し取る場合は簡潔に、${\displaystyle Z+o(Z)}$
• 少しのスペースを取る場合はコンパクトにします。${\displaystyle O(Z)}$

たとえば、ストレージのビットを使用するデータ構造はコンパクトで、ビットは簡潔で、ビットも簡潔で、ビットは暗黙的です。 ${\displaystyle 2Z}$${\displaystyle Z+{\sqrt {Z}}}$${\displaystyle Z+\lg Z}$${\displaystyle Z+3}$

したがって、暗黙的な構造は通常、入力データの何らかの順列を使用して情報を格納するように簡略化されます。この最もよく知られた例はヒープです。

簡潔なインデックス可能辞書は、ランク/選択辞書とも呼ばれ、二分木、-分木、多重集合、^[2]や接尾辞木、配列^[3]など、数多くの簡潔な表現手法の基礎を形成します。基本的な問題は、通常、 ビット配列 として表されるユニバースのサブセットを格納することです。インデックス可能辞書は、辞書に対する通常の方法 (クエリ、および動的なケースでの挿入/削除) に加えて、次の操作をサポートします。 ${\displaystyle k}$${\displaystyle S}$${\displaystyle U=[0\dots n)=\{0,1,\dots ,n-1\}}$${\displaystyle B[0\dots n)}$${\displaystyle B[i]=1}$${\displaystyle i\in S.}$

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

のために。 ${\displaystyle q\in \{0,1\}}$

つまり、 は位置までの に等しい要素の数を返しますが、 は の - 番目の出現の位置を返します。 ${\displaystyle \mathbf {rank} _{q}(x)}$${\displaystyle q}$${\displaystyle x}$${\displaystyle \mathbf {select} _{q}(x)}$${\displaystyle x}$${\displaystyle q}$

ビットの記憶空間（元のビット配列と補助構造）を使用し、定数時間で順位付けと選択をサポートする単純な表現^{[4]があります。これは、}範囲最小クエリと同様のアイデアを使用します。つまり、限られたサイズのサブ問題で停止する前に、定数回の再帰が行われます。ビット配列は、サイズ ビットの大きなブロックとサイズ ビットの小さなブロックに分割されます。各大きなブロックについて、その最初のビットの順位が別のテーブル に格納されます。各エントリは、合計ビットの記憶域を占めます。大きなブロック内では、別のディレクトリに、そこに含まれる小さなブロックのそれぞれの順位が格納されます。ここでの違いは、エントリごとに ビットのみが必要であることです。これは、格納する必要があるのが、それを含む大きなブロックの最初のビットの順位との差のみであるためです。したがって、このテーブルは合計 ビットを必要とします。その後、 の長さのビット文字列に対するすべての可能な順位付けクエリへの回答を格納するルックアップテーブルを使用できます。これにはビットの記憶域が必要です。したがって、これらの補助テーブルはそれぞれスペースを占有するため、このデータ構造は時間とスペースのビットでランク付けクエリをサポートします。 ${\displaystyle n+o(n)}$${\displaystyle o(n)}$${\displaystyle B}$${\displaystyle l=\lg ^{2}n}$${\displaystyle s=\lg n/2}$${\displaystyle R_{l}[0\dots n/l)}$${\displaystyle \lg n}$${\displaystyle (n/l)\lg n=n/\lg n}$${\displaystyle R_{s}[0\dots l/s)}$${\displaystyle l/s=2\lg n}$${\displaystyle \lg l=\lg \lg ^{2}n=2\lg \lg n}$${\displaystyle (n/s)\lg l=4n\lg \lg n/\lg n}$${\displaystyle R_{p}}$${\displaystyle s}$${\displaystyle i\in [0,s)}$${\displaystyle 2^{s}s\lg s=O({\sqrt {n}}\lg n\lg \lg n)}$${\displaystyle o(n)}$${\displaystyle O(1)}$${\displaystyle n+o(n)}$

クエリに一定時間で回答するために、一定時間アルゴリズムは次の計算を行います。 ${\displaystyle \mathbf {rank} _{1}(x)}$

• ${\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]}$

実際には、ルックアップテーブルは、ビット単位の演算と、小さなブロックに設定されているビットの数を見つけるために使用できる小さなテーブルに置き換えることができます。これは多くの場合有益です。なぜなら、簡潔なデータ構造は大規模なデータ セットで使用されるためです。その場合、キャッシュ ミスがはるかに頻繁になり、ルックアップ テーブルが近くの CPU キャッシュから追い出される可能性が高くなります。^{[5]選択クエリは、}ランクに使用されるのと同じ補助構造でバイナリ検索を実行することで簡単にサポートできますが、最悪の場合、時間がかかります。追加のストレージのビットを使用するより複雑な構造を使用すると、定数時間で選択をサポートできます。 ^[6]実際には、これらのソリューションの多くには、漸近的な利点が明らかになる前に支配的な表記法に隠れた定数があります。ブロードワード演算とワード境界ブロックを使用した実装は、実際にはパフォーマンスが向上することがよくあります。^[7]${\displaystyle R_{p}}$${\displaystyle O(\lg n)}$${\displaystyle 3n/\lg \lg n+O({\sqrt {n}}\lg n\lg \lg n)=o(n)}$${\displaystyle O(\cdot )}$

空間アプローチは、の異なる- 部分集合(または長さが で、それぞれが1 である 2 進文字列)が存在することに注目することで改善できます。したがって、を格納するために必要なビット数の情報理論上の下限値となります。この上限値、つまり空間を使用する上限値を達成する簡潔な (静的) 辞書があります。 ^{[8]この構造は、}ランク付けと選択のクエリをサポートするように拡張することができ、空間を必要とします。^[2]ただし、この構造の正しいランク付けクエリは、最小完全ハッシュ関数の動作と同様に、セットに含まれる要素に制限されます。この上限値は、辞書のストレージ スペースを に減らすことで、空間と時間のトレードオフにまで減らすことができます。クエリには時間がかかります。 ^[9]${\displaystyle n+o(n)}$${\displaystyle \textstyle {\binom {n}{m}}}$${\displaystyle m}$${\displaystyle [n)}$${\displaystyle n}$${\displaystyle m}$${\displaystyle \textstyle {\mathcal {B}}(m,n)=\lceil \lg {\binom {n}{m}}\rceil }$${\displaystyle B}$${\displaystyle {\mathcal {B}}(m,n)+o({\mathcal {B}}(m,n))}$${\displaystyle {\mathcal {B}}(m,n)+O(m+n\lg \lg n/\lg n)}$${\displaystyle {\mathcal {B}}(m,n)+O(nt^{t}/\lg ^{t}n+n^{3/4})}$${\displaystyle O(t)}$

ビット未満でランク（選択ではない）をサポートするインデックス可能な辞書を構築することも可能です。このような辞書は単調最小完全ハッシュ関数と呼ばれ、 ビット未満で実装できます。^{[10] [11]}${\displaystyle \textstyle {\mathcal {B}}(m,n)}$${\displaystyle O(m\log \log \log n)}$

簡潔なハッシュ テーブル (簡潔な順序なし辞書とも呼ばれる) は、スペース ビットを使用してユニバースからのキーを格納し、一定の予想時間でメンバーシップ クエリをサポートするデータ構造です。簡潔なハッシュ テーブルが一定の予想時間で挿入と削除もサポートする場合は動的と呼ばれ、そうでない場合は静的と呼ばれます。${\displaystyle m}$${\displaystyle \{0,1,\dots ,n-1\}}$${\displaystyle (1+o(1)){\mathcal {B}}(m,n)}$

最初の動的簡潔ハッシュテーブルは、2003 年に Raman と Rao によって提案されました。^[12]の場合、彼らのソリューションではスペース ビットを使用します。その後、このスペースの境界は、任意の定数個の対数に対して ビットに改善できることが示され^[13]、その後すぐにこの境界も最適であることが示されました。^{[14] [15]}後者のソリューションは、すべての操作を最悪の場合でも一定時間で高い確率でサポートします。 ${\displaystyle n={\text{poly}}(m)}$${\displaystyle {\mathcal {B}}(m,n)+O(m\log \log m)}$${\displaystyle {\mathcal {B}}(m,n)+O(m\log \log \log \cdots \log m)}$

最初の静的簡潔ハッシュテーブルは、1999 年に Pagh によって提案されました。^{[16] [17]}の場合、彼らのソリューションは空間ビットを使用し、最悪の場合の定数時間のクエリをサポートします。この境界はその後ビットに改善され、^[18]、さらにビットに改善されました。^[19]最初の 2 つのソリューション^{[17] [18] は}最悪の場合の定数時間のクエリをサポートしますが、最後のソリューションは定数の期待時間のクエリをサポートします。^[19]最後のソリューションでは、サイズ のルックアップテーブルへのアクセスも必要ですが、このルックアップテーブルは格納される要素のセットに依存しません。^[19]${\displaystyle n={\text{poly}}(m)}$${\displaystyle {\mathcal {B}}(m,n)+O(m(\log \log m)^{2}/\log m)}$${\displaystyle {\mathcal {B}}(m,n)+m/{\text{poly}}\log m}$${\displaystyle {\mathcal {B}}(m,n)+{\text{poly}}\log m}$${\displaystyle n^{\epsilon }}$

任意の長さの文字列 (パスカル文字列)はZ + log( Z ) のスペースを占めるため、簡潔です。最大長がある場合 (実際には 2 ³² = 4 GiB のデータは非常に長い文字列であり、2 ⁶⁴ = 16 EiB のデータは実際のどの文字列よりも大きいため)、長さのある文字列も暗黙的であり、Z + k のスペースを占めます。ここで、k は最大長を表すデータの数 (例: 64 ビット) です。

可変長の項目 (文字列など) のシーケンスをエンコードする必要がある場合、さまざまな方法があります。直接的な方法は、各レコードに長さと項目を格納することです。これらを次々に配置できます。これにより、効率的な next が可能になりますが、k番目の項目を見つけることはできません。別の方法としては、項目を区切り文字で順序付けて配置する方法があります (例: null で終了する文字列)。これは長さの代わりに区切り文字を使用し、シーケンス全体をスキャンして区切り文字を探す必要があるため、大幅に遅くなります。どちらもスペース効率に優れています。別の方法は、帯域外分離です。項目を区切り文字なしで次々に配置するだけです。項目の境界は、長さのシーケンスとして、またはより適切なのは、このシーケンスへのオフセットとして格納できます。または、項目が始まる位置に 1 が入り、それ以外の場所に 0 が入った別のバイナリ文字列を、項目と一緒にエンコードします。この文字列が与えられると、関数はインデックスが与えられれば、各項目がどこから始まるかをすばやく判断できます。^[20]これはコンパクトだが簡潔ではない。2Zの空間、つまりO( Z )を占有するからである。 ${\displaystyle select}$

もう 1 つの例は、二分木の表現です。ノード上の任意の二分木は、任意のノードに対するさまざまな操作をサポートしながら、ビットで表現できます。操作には、親、左と右の子の検索、サブツリーのサイズの取得など、それぞれ定数時間で実行できます。ノード上の異なる二分木の数は です。 が大きい場合、この数は約 です。したがって、これをエンコードするには少なくとも約ビットが必要です。したがって、簡潔な二分木は、ノードあたり ビットのみを占有します。 ${\displaystyle n}$${\displaystyle 2n+o(n)}$${\displaystyle n}$${\displaystyle {\tbinom {2n}{n}}}$${\displaystyle /(n+1)}$${\displaystyle n}$${\displaystyle 4^{n}}$${\displaystyle \log _{2}(4^{n})=2n}$${\displaystyle 2}$

• 最小完全ハッシュ関数
• 簡潔で非対話的な知識の議論