簡潔なデータ構造

コンピューター サイエンスでは簡潔なデータ構造とは、情報理論の下限に「近い」量のスペースを使用しますが、(他の圧縮表現とは異なり) 効率的なクエリ操作を可能にするデータ構造です。この概念はもともと、ビット ベクトル、(ラベルのない)ツリー、および平面グラフをエンコードするためにJacobson [1]によって導入されました。一般的な可逆データ圧縮アルゴリズムとは異なり、簡潔なデータ構造では、最初に解凍しなくても、その場で使用できる機能が保持されます。関連する概念として、圧縮データ構造があります。ただし、保存または符号化されたデータのサイズは、同様にデータ自体の特定の内容に依存します。

これが、あるデータを保存するのに必要な情報理論上の最適なビット数であると仮定します。このデータの表現は次のように呼ばれます。

  • スペースが少し必要な場合は暗黙的に、
  • スペースが少し必要な場合は簡潔に
  • 少しのスペースを取る場合はコンパクトです。

たとえば、ストレージのビットを使用するデータ構造はコンパクトで、ビットは簡潔で、ビットも簡潔で、ビットは暗黙的です。

したがって、暗黙的な構造は通常、入力データの何らかの並べ替えを使用して情報を格納することに還元されます。この最もよく知られた例はヒープです。

簡潔なインデックス可能な辞書

ランク/選択辞書とも呼ばれる簡潔なインデックス可能な辞書は、バイナリ ツリー-分ツリー、マルチセット [2]、接尾語ツリーや配列など多く簡潔表現手法の基礎を形成します[3]基本的な問題は、通常はビット配列として表されるユニバースのサブセットを格納することです。ただし、インデックス可能な辞書は、辞書に対する通常のメソッド (クエリ、および動的ケースの挿入/削除) と次の操作をサポートします:

のために

つまり、は、までの位置に等しい要素の数を返しますが、 は- 番目に出現する位置を返します

ストレージスペースのビット (元のビット配列と補助構造)を使用し、定数時間でのランク付け選択をサポートする単純な表現[4]があります。これは、範囲最小クエリの場合と同様のアイデアを使用します限られたサイズの部分問題で停止する前に、一定の数の再帰が行われます。ビット配列は、サイズ ビットの大きなブロックサイズビットの小さなブロックに分割されます。大きなブロックごとに、その最初のビットのランクが別のテーブルに保存されますこのような各エントリは、合計でビットを必要とします。ストレージのビット。大きなブロック内では、別のディレクトリに、そこに含まれる小さなブロックのそれぞれのランクが保存されますここでの違いは、格納する必要があるのは、含まれる大きなブロック内の最初のビットのランクとの差だけであるため、各エントリのビットのみが必要であることです。したがって、このテーブルは合計ビット数を必要とします。次に、長さ のビット文字列に関する考えられるすべてのランク クエリに対する答えを格納するルックアップ テーブルを使用できますこれには少しのストレージスペースが必要です。したがって、これらの補助テーブルはそれぞれスペースを取るため、このデータ構造は時間とスペースのビット数でのランク クエリをサポートします。

定数時間でクエリに答えるために、定数時間アルゴリズムは次を計算します。

実際には、ルックアップ テーブルはビット単位の演算と、小さなブロックに設定されたビット数を見つけるために使用できる小さなテーブルに置き換えることができます。簡潔なデータ構造は大規模なデータ セットで使用されるため、これは多くの場合有益です。その場合、キャッシュ ミスがより頻繁になり、ルックアップ テーブルが近くの CPU キャッシュから追い出される可能性が高くなります。[5]選択クエリは、 Rankに使用されるのと同じ補助構造に対して二分検索を実行することで簡単にサポートできますただし、最悪の場合は時間がかかります。追加ストレージのビットを使用するより複雑な構造を使用して、定数時間での選択をサポートできます[6]実際には、これらの解決策の多くは、漸近的な利点が明らかになる前に支配的な定数を表記法に隠しています。実際には、ブロードワード演算とワード位置合わせされたブロックを使用した実装の方がパフォーマンスが向上することがよくあります。[7]

エントロピー圧縮されたソリューション

空間アプローチは、の異なるサブセット(または正確に 1 を含む長さのバイナリ文字列)があり、これがを格納するのに必要なビット数の情報理論的な下限であることに注意することで改善できますこの限界を達成する、つまりスペースを使用する簡潔な (静的) 辞書があります[8]この構造は、ランク付けおよび選択クエリをサポートするように拡張でき、スペースを必要とします。[2]正しいランクただし、この構造のクエリは、最小限の完全ハッシュ関数の動作と同様に、セットに含まれる要素に限定されます。この境界は、クエリに時間がかかるように辞書の記憶領域を削減することで、領域と時間のトレードオフに抑えることができます[9]

また、使用するビット数が少ないランク (選択ではない) をサポートするインデックス可能な辞書を構築することもできますこのような辞書は、単調最小完全ハッシュ関数と呼ばれ、わずかなビットを使用して実装できます。[10] [11]

簡潔なハッシュ テーブル

簡潔なハッシュ テーブルは、簡潔な順序なし辞書とも呼ばれ、スペース ビットを使用してユニバースからのキーを格納し、一定の予想時間内でメンバーシップ クエリをサポートするデータ構造です。簡潔なハッシュ テーブルが一定の予想時間内での挿入と削除もサポートしている場合、それは動的と呼ばれ、それ以外の場合は静的と呼ばれます

最初の動的簡潔なハッシュ テーブルは、2003 年に Raman と Rao によって作成されました。[12]の場合、彼らのソリューションはスペースビットを使用します。その後、この空間境界は、任意の定数の対数のビットに改善できることが示されました。[13]後者のソリューションは、最悪の場合の一定時間でのすべての操作を高い確率でサポートします。

最初の静的簡潔ハッシュ テーブルは 1999 年に Pagh によって作成されました。[14] [15]の場合、彼らのソリューションはスペースビットを使用し、最悪の場合の定数時間クエリをサポートします。この境界はその後ビットに改良され[16] 、さらにビットに改良されました。[17]最初の 2 つのソリューション[15] [16]は最悪の場合の一定時間クエリをサポートしますが、最後のソリューションは一定の予想時間クエリをサポートします。[17]最終的な解決策では、サイズ のルックアップ テーブルへのアクセスも必要ですが、このルックアップ テーブルは格納されている要素のセットとは独立しています。[17]

その他の例

任意の長さの文字列 ( Pascal string )はZ + log( Z ) スペースを取るため、簡潔になります。最大長がある場合 (実際の場合は、2 32 = 4 GiB のデータは非常に長い文字列であり、2 64 = 16 EiB のデータは実際のどの文字列よりも大きいため)、次の長さの文字列になります。これも暗黙的であり、Z + k空間を取ります。ここで、k は最大長 (64 ビットなど) を表すデータの数です。

一連の可変長項目 (文字列など) をエンコードする必要がある場合、さまざまな可能性があります。直接的なアプローチは、各レコードに長さと項目を保存することです。これらを順番に配置できます。これにより、効率的に次の処理が可能になりますが、k番目の項目は見つかりません。別の方法は、区切り文字 (ヌルで終わる文字列など)を使用して項目を順番に配置することです。)。これは長さの代わりに区切り文字を使用し、シーケンス全体で区切り文字をスキャンする必要があるため、大幅に時間がかかります。どちらもスペース効率が良いです。別のアプローチは帯域外分離です。区切り文字を使用せずに項目を単純に次々に配置できます。項目境界は、長さのシーケンスとして、またはより適切には、このシーケンスへのオフセットとして保存できます。あるいは、項目の開始位置が 1 で構成され、その他の部分が 0 で構成される別個のバイナリ文字列が、それとともにエンコードされます。この文字列を指定すると、関数はインデックスを指定して各項目がどこから始まるかをすぐに判断できます。[18]これはコンパクトですが 2 Z空間 (O( Z )) を必要とするため、簡潔ではありません。

もう 1 つの例は、バイナリ ツリーの表現です。ノード上の任意のバイナリ ツリーは、親、左と右の子の検索、サブツリーのサイズの返しなど、任意のノードでのさまざまな操作をサポートしながらビットで表現できます、それぞれ一定の時間で。ノード上の異なるバイナリ ツリーの数はです大きい場合、これは約; したがって、それをエンコードするには少なくとも約ビットが必要です。したがって、簡潔な二分木はノードごとにビットのみを占有します。

こちらも参照

参考文献

  1. ^ ジェイコブソン、G.J (1988)。簡潔な静的データ構造(博士論文)。ペンシルバニア州ピッツバーグ: カーネギーメロン大学。
  2. ^ ab ラマン、R.; V. ラマン。S.S ラオ (2002)。「k-ary ツリーとマルチセットのエンコードへのアプリケーションを備えた簡潔なインデックス可能な辞書」。離散アルゴリズムに関する第 13 回 ACM-SIAM 年次シンポジウムの議事録233–242ページ。arXiv : 0705.0552CiteSeerX 10.1.1.246.3123土井:10.1145/1290672.1290680。ISBN   0-89871-513-X
  3. ^ 貞兼和夫; R. グロッシ (2006)。「簡潔なデータ構造をエントロピー境界に押し込む」(PDF)離散アルゴリズムに関する第 17 回 ACM-SIAM 年次シンポジウムの議事録1230–1239ページ。ISBN  0-89871-605-52011 年 9 月 29 日のオリジナル(PDF)からアーカイブされました。
  4. ^ ジェイコブソン、G. (1989 年 11 月 1 日)。スペース効率の高い静的ツリーとグラフ(PDF)コンピュータサイエンスの基礎に関する第 30 回 IEEE シンポジウム。土井:10.1109/SFCS.1989.63533。2016 年 3 月 12 日のオリジナル(PDF)からアーカイブされました。
  5. ^ ゴンザレス、R.; S.グラボウスキー; V.マキネン。G. ナバロ (2005)。「ランクおよび選択クエリの実践的な実装」(PDF)効率的で実験的なアルゴリズムに関する第 4 回ワークショップ (WEA) のポスター議事録27~38ページ。
  6. ^ デヴィッド・クラーク (1996)。コンパクトパットツリー(PDF)(博士論文)。ウォータールー大学。
  7. ^ ヴィグナ、S. (2008)。「ランク/選択クエリのブロードワード実装」(PDF)実験的なアルゴリズムコンピューターサイエンスの講義ノート。Vol. 5038。154–168 ページ。CiteSeerX 10.1.1.649.8950土井:10.1007/978-3-540-68552-4_12。ISBN   978-3-540-68548-7S2CID  13963489。
  8. ^ ブロドニク、A.; J. I マンロー (1999)。「一定の時間とほぼ最小限のスペースでのメンバーシップ」(PDF)サイアム J. コンピューティング 28 (5): 1627 ~ 1640 年。CiteSeerX 10.1.1.530.9223土井:10.1137/S0097539795294165。  
  9. ^ パトラシュク、M. (2008)。「サクシンター」(PDF)コンピュータ サイエンスの基礎、2008 年。FOCS'08。に関する IEEE 第 49 回年次 IEEE シンポジウム305–313ページ。
  10. ^ ベラズーギ、ジャマル; ボルディ、パオロ。パー、ラスムス。ヴィーニャ、セバスティアーノ (2009-01-04)。「モノトーン最小完全ハッシュ: O(1) アクセスのソートされたテーブルの検索」。離散アルゴリズムに関する第 20 回 ACM-SIAM シンポジウムの議事録ペンシルバニア州フィラデルフィア: 工業および応用数学協会: 785–794。土井: 10.1137/1.9781611973068.86ISBN 978-0-89871-680-1
  11. ^ アサディ、セパール; ファラック=コルトン、マルティン。Kuszmaul, William (2023 年 1 月)、「Tight Bounds for Monotone Minimal Perfect Hashing」、2023 年離散アルゴリズムに関する年次 ACM-SIAM シンポジウム (SODA) の議事録、ペンシルベニア州フィラデルフィア: 工業および応用数学協会、456–476 ページ、arXiv : 2207.10556doi :10.1137/1.9781611977554.ch20、ISBN 978-1-61197-755-42023-04-28に取得
  12. ^ ラマン、ラジーブ; Rao、Satti Srinivasa (2003)、「Succinct Dynamic Dictionaries and Trees」、Automata、Languages and Programming、ベルリン、ハイデルベルク: Springer Berlin Heidelberg、pp. 357–368、doi :10.1007/3-540-45061-0_30、ISBN 978-3-540-40493-42023-04-28に取得
  13. ^ ベンダー、マイケル・A. ファラック=コルトン、マルティン。ジョン・クスマウル。ウィリアム・クスマウル。劉明蒙(2022-06-09)。「ハッシュテーブルの最適な時間と空間のトレードオフについて」。コンピューティング理論に関する第 54 回年次 ACM SIGACT シンポジウムの議事録米国ニューヨーク州ニューヨーク: ACM。1284–1297ページ。土井:10.1145/3519935.3519969。hdl :1721.1/146419。ISBN 9781450392648S2CID  240354692。
  14. ^ パー、ラスムス (1998-01-28)。「最悪の場合の検索時間が O(1) の辞書の冗長性が低い」。BRICSレポートシリーズ5 (28)。土井: 10.7146/brics.v5i28.19434ISSN  1601-5355。
  15. ^ ab Pagh、ラスムス (2001 年 1 月)。「クエリ時間が一定の静的ディクショナリの冗長性が低い」。SIAM ジャーナル オン コンピューティング31 (2): 353–363。土井:10.1137/s0097539700369909。ISSN  0097-5397。
  16. ^ ab パトラスク、ミハイ (2008 年 10 月)。「サクシンター」。2008 年、コンピュータ サイエンスの基礎に関する第 49 回 IEEE 年次シンポジウムIEEE。305–313ページ。土井:10.1109/focs.2008.83。ISBN 978-0-7695-3436-7S2CID  257721481。
  17. ^ abc ユウ、華成 (2020-06-22). 「ほぼ最適な静的ラスベガス簡潔辞書」。コンピューティング理論に関する第 52 回年次 ACM SIGACT シンポジウムの議事録米国ニューヨーク州ニューヨーク: ACM。1389–1401ページ。arXiv : 1911.01348土井:10.1145/3357713.3384274。ISBN 9781450369794S2CID  207780523。
  18. ^ ベラズーギ、ジャマル。「ハッシュ、置換、圧縮」(PDF)