0

n 個の整数 IDが与えられた場合、最大 k 個の ID のすべての可能なセットを定数値にリンクしたいと考えています。私が探しているのは、セット ({1, 5}、{1, 3, 5}、{1, 2, 3, 4, 5, 6, 7} など) を一意の値に変換する方法です。

保証:

  • n < 100 および k < 10 (繰り返します: セットのサイズは [1, k] の範囲になります)。
  • ID の順序は関係ありません: {1, 5} == {5, 1}。
  • すべての組み合わせが可能ですが、一部除外される場合があります。
  • すべてのセットと値は定数であり、一度だけ作成されます。削除も挿入も、値の更新もありません。
  • 生成されると、実行される操作はルックアップのみになります。
  • ルックアップは頻繁に行われ、一方向に行われます (指定されたセット、ルックアップ値)。
  • 値を並べ替える (または整理する) 必要はありません。

さらに、「隣接する」セット (ID を 1 つ削除、ID を 1 つ追加、ID を 1 つ交換など) に到達しやすく、「少なくともこのセットを含むすべてのセット」にアクセスできると便利です (必須ではありません)。

何か案は？

4

3 に答える 3

1

素数の積を使用して列挙します。

  • -> 2
  • b -> 3
  • c -> 5
  • 日 -> 7
  • など

hash(ab) := 6、hash (abc) := 30

また、"ab" が "abc" のサブセットである場合、次のような副作用があります。

hash(abc) % hash(ab) == 0

と

hash(abc) / hash(ab) == hash(c)

悪いニュース: オーバーフローが発生する可能性があり、100 番目の素数はおそらく 1000 前後になり、64 ビットでは 1000**10 に対応できません。これは、ハッシュ関数としての機能には影響しません。サブセットのみが機能しません。アナグラムに適用される同じ方法

もう 1 つのオプションは Zobrist ハッシュです。これは素数法と同等ですが、素数の代わりに (乱数) 数の固定セットを使用し、乗算の代わりに XOR を使用します。あなたのような固定された小さな（<<〜70ビットが必要）セットの場合、ゾブリストテーブルを調整して衝突を完全に回避することができる場合があります（完全なハッシュを生成します）。

そして最後の（そして最も簡単な）方法は、（100ビット）ビットマップを使用し、それをハッシュ値として扱うことです（おそらくモジュロテーブルサイズの後）

まったく関係のない方法は、ビットマップのビットに基づいて決定木を構築することです。(ツリーの最大深さは k です)ビット値に関連する kD ツリー

于 2012-11-07T16:28:17.813 に答える
0

最善の解決策ではないかもしれませんが、次のことができます。

  1. 単純な IntegerComparator を使用してセットを最低から最高に並べ替えます
  2. セットの各アイテムを文字列に追加します

したがって、{2,5,9,4} の最初のステップがある場合は、{2,4,5,9}; 2番目->「2459」

このようにして、一意のセットから一意の文字列を取得します。それらを整数値にマップする必要がある場合は、その後文字列をハッシュできます。

私が考えることができる2番目の方法は、それらをJavaセットに保存し、キーとしてHashMapに対して単純にマップすることですset

于 2012-11-07T16:12:21.090 に答える
0

各セットから「差分」を計算 {1, 6, 87, 89} = {1,5,81,2,0,0,...} {1,2,3,4} = { 1,1, 1,1,0,0,0,0... };

次に、各数値を可変長エンコーディングでバイナリ エンコードし、ビットを連結します。

セットを比較するのは困難ですが (最初のいくつかの等しいビットを除いて)、セット内に多くの大きな間隔が存在することはできないため、考えられるすべての値が 64 ビットに収まる可能性があります。(少なくとも 16 ビットのスラック...)

于 2012-11-07T16:58:55.313 に答える