arrays - ソートされた配列のコンパクトなデータ構造

Question

次のようなソートされた番号を持つテーブルがあります。

1 320102
2 5200100
3 92010023
4 112010202
5 332020201
6 332020411
: 
5000000000 3833240522044511
5000000001 3833240522089999
5000000002 4000000000213312

レコード番号を考えると、O(log n) 時間の値が必要です。レコード番号は 64 ビット長であり、欠落したレコード番号はありません。値は 64 ビット長で、並べ替えられており、value(n) < value(n+1) です。

明らかな解決策は、単純に配列を作成し、レコード番号をインデックスとして使用することです。これには、値ごとに 64 ビットのコストがかかります。

しかし、それを行うには、よりスペース効率の良い方法が必要です。値が常に増加していることはわかっているので、それは実行できるはずですが、それを可能にするデータ構造を覚えていません。

解決策は、配列で deflate を使用することですが、要素にアクセスするために O(log n) が得られないため、受け入れられません。

私に与えるデータ構造を知っていますか：

O(log n) アクセス
スペース要件 < 64 ビット/値

= 編集 =

すべての数値が事前にわかっているため、各数値の違いを見つけることができます。これらの差の 99 パーセンタイルを取ると、比較的控えめな数値が得られます。log2 を取ると、適度な数を表すのに必要なビット数が得られます。これを適度なビットと呼びましょう。

次に、これを作成します。

64-bit value of record 0
64-bit value of record 1024
64-bit value of record 2048
64-bit value of record 3072
64-bit value of record 4096

次に、すべてのレコードのデルタテーブル:

modest-bits difference to record 0
modest-bits difference to previous record
1022 * modest-bits difference to previous record
modest-bits difference to record 1024

k*1024 を記録するためのささやかなビットの差は常に 0 になるため、シグナリングに使用できます。ゼロ以外の場合、次の 64 ビットは、64 ビット値として次の 1024 レコードの単純な配列へのポインターになります。

控えめな値が 99 パーセンタイル数として選択されるため、それは多くても 1% の確率で発生するため、多くても 1% * n * 控えめなビット + 1% * n * 64 ビット * 1024 が無駄になります。

スペース: O(ささやかなビット * n + 64 ビット * n / 1024 + 1% * n * ささやかなビット + 1% * n * 64 ビット * 1024)

ルックアップ: O(1 + 1024)

(99% と 1024 は調整が必要な場合があります)

=編集2 =

上記のアイデアに基づいていますが、無駄なスペースが少なくなります。これを作成します。

64-bit value of record 0
64-bit value of record 1024
64-bit value of record 2048
64-bit value of record 3072
64-bit value of record 4096

そして、modest-bits で表すことができないすべての値に対して、big-value テーブルをツリーとして作成します。

64-bit position, 64-bit value
64-bit position, 64-bit value
64-bit position, 64-bit value

次に、1024 レコードごとにリセットされるすべてのレコードのデルタテーブル:

modest-bits difference to record 0
modest-bits difference to previous record
1022 * modest-bits difference to previous record
modest-bits difference to record 1024

大きな値のテーブルにあるすべての値に対してもリセットされます。

スペース: O(控えめなビット * n + 64 ビット * n / 1024 + 1% * n * 2 * 64 ビット)。

ルックアップでは、大きな値のテーブルを検索し、次に 1024 番目の値を検索し、最後に適度なビット値を合計する必要があります。

ルックアップ: O(log(大きな値のテーブル) + 1 + 1024) = O(log n)

これを改善できますか？それとも別の方法でうまくやりますか？

score 2 · Accepted Answer

OPは、数値をブロックに分割することを提案します（1回のみ）。ただし、このプロセスは継続される場合があります。すべてのブロックをもう一度分割します。そして再び...最後に、バイナリトライを取得する可能性があります。

ここに画像の説明を入力してください

ルートノードには、インデックスが最小の数値が含まれています。その右の子孫は、テーブルの中央の数値とインデックスが最小の数値の差を格納しますd = A[N/2] - A[0] - N/2。これは、他の右の子孫（図の赤いノード）でも継続されます。リーフノードには、前の番号からのデルタが含まれていますd = A[i+1] - A[i] - 1。

したがって、trieに格納されている値のほとんどは、デルタ値です。それらのそれぞれは64ビット未満を占めます。また、コンパクトにするために、ビットストリームに可変ビット長の数値として格納できます。各数値の長さを取得し、O（log N）時間でこの構造をナビゲートするには、ビットストリームに（一部の）数値と（一部の）サブツリーの長さも含まれている必要があります。

各ノードには、左側のサブツリー（存在する場合）の長さ（ビット単位）が含まれます。
リーフノードを除く各右子孫（図の赤いノード）には、その値の長さ（ビット単位）が含まれています。リーフノードの長さは、ルートからこのノードまでのパス上の他の長さから計算できます。
各右の子孫（図の赤いノード）には、対応する値とパス上の最も近い「赤い」ノードの値の差が含まれています。
すべてのノードは、ルートノードから順番にビットストリームにパックされます。左側の子孫は常にその祖先に従います。右の子孫は、左の子孫によってルート化されたサブツリーに従います。

インデックスが指定された要素にアクセスするには、インデックスのバイナリ表現を使用して、トライ内のパスをたどります。このパスをトラバースしながら、「赤」ノードのすべての値を合計します。インデックスにゼロ以外のビットが残っていない場合は停止します。

N/2値の長さを格納するためのいくつかのオプションがあります。

最大長から平均長より下のどこかまでのすべての値を表すために、各長さに必要な数のビットを割り当てます（いくつかの非常に短い外れ値を除く）。
また、いくつかの長い外れ値を除外します（それらを別のマップに保持します）。
長さが均等に分散されていない可能性があるため、値の長さにはハフマン符号化を使用するのが妥当です。

固定長またはハフマンエンコーディングは、トライの深さごとに異なる必要があります。

N / 4の最小のサブツリーには単一の値が含まれているため、実際にはN/4のサブツリーの長さは値の長さです。

他のN/4サブツリーの長さは、固定（事前定義）長のワードで格納される場合があるため、大きなサブツリーの場合、概算（切り上げ）の長さしかわかりません。

2 ³⁰のフルレンジ64ビット数の場合、約34ビット値をパックする必要があります。3/4ノードの場合、約 4ビットの値の長さ、および4つおきのノードに対して10ビットのサブツリーの長さ。これにより、34％のスペースが節約されます。

値の例：

0 320102
1 5200100
2 92010023
3 112010202
4 332020201
5 332020411
6 3833240522044511
7 3833240522089999
8 4000000000213312

これらの値を試してください：

root               d=320102           vl=19    tl=84+8+105+4+5=206
   +-l                                         tl=75+4+5=84
   | +-l                                       tl=23
   | | +-l
   | | | +-r       d=4879997          (vl=23)
   | | +-r         d=91689919         vl=27
   | |   +-r       d=20000178         (vl=25)
   | +-r           d=331700095        vl=29    tl=8
   |   +-l
   |   | +-r       d=209              (vl=8)
   |   +-r         d=3833240190024308 vl=52
   |     +-r       d=45487            (vl=16)
   +-r             d=3999999999893202 vl=52

値の長さのエンコーディング：

           bits start end
Root       0    19    19
depth 1    0    52    52
depth 2    0    29    29
depth 3    5    27    52
depth 4    4    8     23

サブツリーの長さには、それぞれ8ビットが必要です。

エンコードされたストリームは次のとおりです（読みやすくするために、バイナリ値は引き続き10進数で表示されます）。

bits value                      comment
19   320102                     root value
8    206                        left subtree length of the root
8    84                         left subtree length
4    15                         smallest left subtree length (with base value 8)
23   4879997                    value for index 1
5    0                          value length for index 2 (with base value 27)
27   91689919                   value for index 2
25   20000178                   value for index 3
29   331700095                  value for index 4
4    0                          smallest left subtree length (with base value 8)
8    209                        value for index 5
5    25                         value length for index 6 (with base value 27)
52   3833240190024308           value for index 6
16   45487                      value for index 7
52   3999999999893202           value for index 8

全部で285ビットまたは564ビットワード。また、値の長さのエンコーディングテーブル（350ビット）からビット/開始値を格納する必要があります。635ビットを格納するには、10個の64ビットワードが必要です。つまり、このような少数のテーブルは圧縮できません。多数のテーブルの場合、値の長さのエンコーディングテーブルのサイズはごくわずかです。

インデックス7の値を検索するには、ルート値（320102）を読み取り、206ビットをスキップし、インデックス4（331700095）の値を追加し、8ビットをスキップし、インデックス6（3833240190024308）の値を追加し、インデックス7（45487）の値を追加します。インデックス（7）を追加します。結果は、予想どおり3 833 240 522089999です。

score 1 · Accepted Answer

あなたがあなたの質問で概説するように、私はそれをブロックで行います。ブロックサイズkを選択します。ここで、目的の値に到達する前に、平均k/2値をデコードする必要があることを受け入れることができます。合計n個の値の場合、n/k個のブロックがあります。n / kエントリのテーブルは、各ブロックの開始点を見つけるためにデータストリームを指します。そのテーブルのどこに行くかを見つけるのは、二分探索の場合はO（log（n / k））です。または、テーブルが十分に小さく、重要な場合は、補助ハッシュテーブルを使用してO（1）について調べることができます。

各ブロックは、開始64ビット値で始まります。それ以降のすべての値は、前の値からのデルタとして保存されます。私の提案は、これらのデルタを、次の値にいくつのビットがあり、その後にその数のビットがあるかを示すハフマンコードとして格納することです。ハフマンコードはブロックごとに最適化され、そのコードの説明はブロックの先頭に格納されます。

1..64の範囲で、実質的にフラットなハフマンコードに続くビット数を持つ6ビットを各値の前に置くことで、これを単純化できます。ビット長のヒストグラムによっては、最適化されたハフマンコードは、フラットコードと比較してかなりの数のビットをノックオフする可能性があります。

これを設定したら、kを試して、それをどれだけ小さくしても、圧縮への影響を制限できるかどうかを確認できます。

score 0 · Accepted Answer

それを行うデータ構造を知りません。

スペースを確保し、速度を落とさないための明白な解決策は、保存するさまざまな int サイズに基づいて、さまざまな配列サイズで独自の構造を作成することです。

擬似コード

class memoryAwareArray {
    array16 = Int16[] //2 bytes
    array32 = Int32[] //4 bytes
    array64 = Int64[] //8 bytes

    max16Index = 0;
    max32Index = 0;

    addObjectAtIndex(index, value) {
      if (value < 65535) {
        array16[max16Index] = value;
        max16Index++;
        return;
      }
      if (value < 2147483647) {
        array32[max32Index] = value;
        max32Index++;
        return;
      }

      array64[max64Index] = value;
      max64Index++;
    }

    getObject(index) {
      if (index < max16Index) return(array16[index]);
      if (index < max32Index) return(array32[index-max16Index]);
      return(array64[index-max16Index-max32Index]);
    }
}

これらの線に沿ったものは速度を大幅に変更するべきではなく、構造全体を埋めると約 7 ギガを節約できます。もちろん、値の間にギャップがあるため、それほど節約できません。

arrays - ソートされた配列のコンパクトなデータ構造

3 に答える 3

Related

Reference