4

私は例で説明しようとしています：

番号付き要素 E = [elem0, elem1, elem2, ...] のリストを想像してください。

1 つのインデックス セットは、E の要素を参照する {42, 66, 128} になる可能性があります。このセットの順序は重要ではないため、{42, 66, 128} == {66, 128, 42} ですが、各要素は任意のインデックス セットで最大 1 回 (つまり、実際のセットです)。

私が今欲しいのは、E の要素を参照するインデックス セットを含む別の順序付きリスト M を提供するスペース効率の良いデータ構造です。それ自体がインデックス可能であること (したがって、M はこの意味でリストであるため、正確なインデックスは重要ではありません)。必要に応じて、すべてのインデックス セットに同じ数の要素を含めるように強制できます。

たとえば、M は次のようになります。

0: {42, 66, 128}
1: {42, 66, 9999}
2: {1, 66, 9999}

次のことができるようになりました。

for(i in M[2]) { element = E[i]; /* do something with E[1],E[66],and E[9999] */ }

おそらく、これがどこに向かっているのかわかるでしょう: 別のマップ M2 があるかもしれません。これは、最終的に E の要素を指す M を指すセットの順序付きリストです。

この例でわかるように、インデックス セットは比較的似ている可能性があります (M[0] と M[1] は最初の 2 つのエントリを共有し、M[1] と M[2] は最後の 2 つのエントリを共有します)。セットの配列を使用する素朴な方法よりも効率的なものでなければなりません。ただし、適切な「共有」を保証するインデックス エントリの適切なグローバル順序付けを考え出すことはできないかもしれません。

M をツリーとして表現すること (M のインデックスは深さ優先の検索順序などに由来する) から、union-find 構造のハッシュ マップ (それがどのように機能するかはわかりませんが :)

このようなものの教科書のデータ構造へのポインターは大歓迎です (データベースの世界には何かありますか?) が、「自作」のソリューションまたはランダムなアイデアのみを提案していただければ幸いです。

E には数千または数百万の要素が含まれる可能性があり、(一部の) インデックス セットは潜在的に大きく、少なくとも一部のインデックス セット間の類似性は相当なものである必要があり、複数のマッピング レイヤーが存在する可能性があるため、スペース効率は私にとって重要です。

ありがとうございます！

4

4 に答える 4

1

インデックスを打ち負かすのはかなり難しいでしょう。適切なデータ型を使用することで、スペースを節約できます (たとえば、gnu C では、E で 64k 要素未満の場合はshort 、< 4G の場合はint ...)。

その上、

E の順序は重要ではないと言うので、連続する要素を最大化して Ms.

例えば、

E: { 1,2,3,4,5,6,7,8 }

0: {1,3,5,7}
1: {1,3,5,8}
2: {3,5,7,8}

Eを再配置することにより

E: { 1,3,5,7,8,2,4,6 }

値ではなく E インデックスを使用すると、E のサブセットに基づいて Ms を定義し、インデックスを与えることができます。

0: {0-3}     // E[0]: 1, E[1]: 3, E[2]: 5, E[3]: 7 etc...
1: {0-2,4}
2: {1-3,4}

こちらです

  • 生の数値の代わりにインデックスを使用します（通常、インデックスは小さく、負ではありません..）
  • M はサブセットで構成されており、0-30、1、2、3 を意味します。

難しい部分は、サブセットのサイズを最大化して Ms のサイズを最小化するように E を再配置するアルゴリズムを作成することです。

E 再配置アルゴリズムの提案

  • すべてのさんを並べ替え
  • すべての M を処理:

要素 'x' に隣接要素 'y' のリストと、'y' が 'x' の直後にある回数を示すマップを作成するアルゴ

Map map (x,y) -> z
for m in Ms
  for e,f in m // e and f are consecutive elements
    if ( ! map(e,f)) map(e,f) = 1
    else map(e,f)++
  rof
rof

Eを再配置する

ER = {}                 // E rearranged
Map mas = sort_map(map) // mas(x) -> list(y) where 'y' are sorted desc based on 'z' 
e = get_min_elem(mas)   // init with lowest element (regardless its 'z' scores)


while (mas has elements) 
  ER += e        // add element e to ER
  f = mas(e)[0]  // get most likely neighbor of e (in f), ie first in the list
  if (empty(mas(e))
    e = get_min_elem(mas) // Get next lowest remaining value
  else
    delete mas(e)[0]  // set next e neighbour in line
    e = f
  fi
elihw

アルゴ (マップ) はO(n*m)、E に n 個の要素、すべての Ms に m 個の要素を持つ空間である必要があります。

于 2013-01-23T11:25:09.760 に答える
1

ビット配列を使用することができます。それらは、 ifがセット内にあり、if がセット内にa[i]ない1要素の配列です。したがって、すべてのセットは、メンバーが少数またはまったく含まれていない場合でも、正確にビットを占有します。スペース効率はそれほど良くありませんが、この配列を何らかの圧縮アルゴリズムで圧縮すると、サイズが大幅に小さくなります (最終的なエントロピー限界に達する可能性があります)。したがって、動的マルコフコーダー、RLE、またはグループハフマンを試して、最も効率的なものを選択できます。次に、反復プロセスには、オンザフライの解凍とそれに続くビットの線形スキャンが含まれます。長時間の実行では、解凍アルゴリズムを変更してそのようなケースを検出できます (RLE が最も単純なケースです)。i0isize(E)10

差異が小さいセットが見つかった場合は、共通部分の代わりにセットを保存し、スペースを節約するAことができます。この場合、反復するには、両方を展開してから展開する必要があります。A xor BABBAA xor Bxor

于 2013-01-23T13:30:56.287 に答える
1

M のすべての数字を組み合わせて重複を削除し、UniqueM という名前を付けることができます。

すべての M[X] コレクションはビット マスクに変換されます。たとえば、int 値は 32 個の数値を格納できます (無制限のカウントをサポートするには、int の配列を格納する必要があります。配列サイズが合計で 10 の場合、320 個の異なる要素を格納できます)。long 型は 64 ビットを格納できます。

E: {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}

M[0]: {6, 8, 1}
M[1]: {2, 8, 1}
M[2]: {6, 8, 5}

次のように変換されます。

UniqueM: {6, 8, 1, 2, 5}
M[0]: 11100 {this is 7}
M[1]: 01110 {this is 14}
M[2]: 11001 {this is 19}

注: また、E を並べ替えて新しい UniqueM を作成し、その中で間隔を使用する代わりに、my と ring0 のアプローチを組み合わせることもできます。

于 2013-01-23T12:04:14.607 に答える
0

別の便利な解決策:

E: {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}

M[0]: {1, 2, 3, 4, 5, 10, 14, 15}
M[1]: {1, 2, 3, 4, 5, 11, 14, 15}
M[2]: {1, 2, 3, 4, 5, 12, 13}

頻繁に使用するアイテムをキャッシュする:

Cache[1] = {1, 2, 3, 4, 5}
Cache[2] = {14, 15}
Cache[3] = {-2, 7, 8, 9} //Not used just example.

M[0]: {-1, 10, -2}
M[1]: {-1, 11, -2}
M[2]: {-1, 12, 13}

キャッシュされたリストへのリンクを負の数としてマークします。

于 2013-01-23T15:22:27.927 に答える