暗黙的なデータ構造

コンピュータサイエンスにおいて、暗黙的データ構造または空間効率の良いデータ構造とは、メインデータまたは必須データ以外の情報をほとんど保存しないデータ構造、つまり、オーバーヘッドが低いデータ構造のことです。要素の位置が意味と要素間の関係性を持つことから、「暗黙的」と呼ばれます。これは、要素間の関係を明示的に示すポインタの使用とは対照的です。「低オーバーヘッド」の定義はさまざまですが、一般的には一定のオーバーヘッドを意味します。ビッグ O 表記法では、O (1) のオーバーヘッドです。より制限の少ない定義は、より大きなオーバーヘッドを許容する簡潔なデータ構造です。

暗黙的なデータ構造とは、一定のO (1)の空間オーバーヘッド（情報理論の下限を超える）を持つデータ構造である。

歴史的に、Munro & Suwanda (1980) は暗黙的なデータ構造 (およびそれに基づいて動作するアルゴリズム) を「構造情報がポインターで明示されるのではなく、データの格納方法で暗黙的である」ものと定義しました。彼らの定義はいくぶん曖昧で、最も厳密には単一の配列で、サイズのみが保持される (単一のオーバーヘッド数) ^{[1]か、より緩くは定数のオーバーヘッド (} O (1) )を持つデータ構造と定義しています。^{[2]この後者の定義は今日ではより標準的であり、定数ではないが小さな}o (n)オーバーヘッドを持つデータ構造というさらに緩い概念は、今日ではJacobson (1988) によって定義された簡潔なデータ構造として知られています。Munro & Suwanda (1980) はそれを半暗黙的と呼んでいました。 ^[3]

基本的な違いは、静的データ構造 (読み取り専用) と動的データ構造(変更可能) です。ソートされたリストを配列として表すなどの単純な暗黙的なデータ構造は、静的データ構造としては非常に効率的ですが、変更操作 (ソートされたリストの場合の挿入など) が非効率的であるため、動的データ構造としては非効率的です。

暗黙的なデータ構造の簡単な例としては、配列データ構造があります。これはリストの暗黙的なデータ構造で、長さという定数のオーバーヘッドのみを必要とします。これは、各データ要素に関連付けられたポインターがあり、ある要素から次の要素への関係を明示的に示すリンク リストとは異なります。同様に、ヌル終端文字列は、文字列(文字のリスト)の暗黙的なデータ構造です。これらは静的データ構造 (読み取り専用) であり、要素に対する単純な反復操作のみを許可するため、非常に単純であると考えられています。

同様に単純なのは、多次元配列を単一の 1 次元配列として、その次元とともに表すことです。たとえば、m × n配列を、長さm·nの単一のリストとして、数値mとnとともに表します(各 1 次元サブ配列へのポインタの 1 次元配列として表すのではなく)。要素は同じ型である必要はなく、データのテーブル(レコードのリスト) も同様に、各フィールドの長さとともに、フラットな (1 次元の) リストとして暗黙的に表すことができます。ただし、各フィールドのサイズは均一である必要があります (したがって、レコードごとではなく、フィールドごとに 1 つのサイズを使用できます)。

もう少し簡単な例としては、ソートされたリストをソートされた配列で表すことが挙げられます。これにより、バイナリ検索による対数時間で検索が可能になります。検索ツリー、特にバイナリ検索ツリーとは対照的です。バイナリ検索ツリーでも対数時間の検索が可能ですが、ポインタが必要です。ソートされた配列は、バイナリ検索ツリーとは異なり、リストの変更に時間がかかるため、静的データ構造としてのみ効率的ですが、ツリーのスペース オーバーヘッドは不要です。

暗黙的なデータ構造の重要な例としては、完全な二分木を深さの昇順で、つまりルート、最初の左の子、最初の右の子、最初の左の子の最初の左の子などのリストとして表すことが挙げられます。このようなツリーは、特定の深さまでの祖先図で顕著に見られ、暗黙的な表現はAhnentafel (祖先テーブル) として知られています。

これは、完全な二分木（最後のレベルが不完全な場合がある）に一般化することができ、暗黙的なデータ構造の最もよく知られた例、つまり、優先度キューの暗黙的なデータ構造である二分ヒープを生み出します。これは、複数の操作が可能で、効率的な動的データ構造（データの効率的な変更が可能）であるため、以前の例よりも洗練されています。 topだけでなく、insertやpopも実行できます。

より洗練された暗黙的なデータ構造には、ビープ(双方向の親ヒープ) が含まれます。

リストや値の表の単純な例は先史時代にまで遡りますが、歴史的に重要な暗黙のデータ構造は、少なくとも1590 年にミカエル・アイツィンガーが系図作成に使うために導入した Ahnentafel にまで遡ります。正式なコンピュータ サイエンスでは、最初の暗黙のデータ構造は一般に、バイナリ検索に使われるソート済みリストであると考えられています。これは、1946 年にジョン・モークリーが、コンピュータ関連のトピックに関する最初の講義集であるムーア スクール講義で導入しました。 ^{[4] [5]}バイナリ ヒープは、ヒープソートを実装するためにウィリアムズ (1964) で導入されました。 [ ^5]暗黙のデータ構造の概念は、ビープの導入と分析の一環として、マンローとスワンダ (1980) によって形式化されました。^[5]

Hervé Brönnimann、J. Ian Munro、Greg Frederickson の出版物を参照してください。