8

同じ要素を持つベクトルに対して同じバケットを生成するハッシュ関数はありますか?同じ相対位置でk回シフトされますか?

例えば：

hash([1,9,8,7]) -> b1
hash([9,8,7,1]) -> b1

hash([1,8,9,7]) -> b2
hash([1,9,8,5]) -> b3

v1 = [1,9,8,7] v2 = [9,8,7,1] v2はv1が k=3 回左にシフトされるため、両方のベクトルは同じハッシュを取得する必要があります。

しかし、v3 = [1,8,9,7] は同じ相対順序を保持せず、v4 = [1,9,8,5] は異なる値を持つため、どちらもハッシュ b1 を取得しません。

私の最初のアプローチは、各ベクトルの最大値を計算し、その位置を基準 (オフセット = 0) と見なすことでした。最大値が常に最初の位置になるように、各ベクトルをシフトするだけで済みます。このように、シフトされたベクトルは同じように見えます。ただし、ベクトルは要素を繰り返すことができるため、最大値の位置が異なります。

4

6 に答える 6

4

  1. 辞書編集的に最小の配列回転を見つけます。

    本来の方法は、O(n 2 ) ですべての回転をチェックすることですが、Booth のアルゴリズム、Shiloach の Fast Canonization Algorithm、または Duval の Lyndon Factorization Algorithm を使用して線形時間で実行できます。

    詳しくはこちらをご覧ください。

  2. 回転した配列のハッシュを計算します。

    これは、さまざまな方法で行うことができます。たとえば、Java は次のようにします。

    hash = s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

異なる要素を持つ配列が同じ値にハッシュされることは不可能ではありません (これはハッシュでは避けられません) が、同じ配列のすべてのローテーションは同じハッシュになります。

于 2013-08-20T12:01:19.740 に答える
1

常にベクトル コンポーネントとして数値があると仮定すると、次のように計算します。

  • すべての成分の積
  • d_i隣接するコンポーネント ( i、 )のすべての差の積(i+1) mod n。ここで、すべての非負の差に対して 1 が追加されます。

両方を乗算します。

最初の製品は要素の順序から離れて抽象化され、コンポーネントの回転を法とする 2 番目の製品によって再導入されます。同じ値の 2 つの隣接するコンポーネントがある場合、それぞれの差に 1 を追加すると、0 へのマッピングが回避されます。

すべてのコンポーネント順列を同じハッシュ値にマップするため、スタンドアロンの最初の製品では十分ではありません。スタンドアロンの 2 番目の積は、(1,...,1) に沿ったすべてのベクトル オフセットを同じ値にマッピングするため、十分ではありません。

于 2013-08-20T10:13:39.523 に答える
1

配列の要素をハッシュしないでください。代わりに、隣接する 2 つのセルの違いをハッシュしてください。

#include <stdio.h>

unsigned hashdiff(unsigned arr[], size_t siz);

        /* toy hash function: don't try this at home ... */
#define HASH1(v) ((v)*7654321)

unsigned hashdiff(unsigned arr[], size_t siz)
{
unsigned idx;
unsigned hash;

if (siz < 1) return 0;
if (siz < 2) return HASH1(arr[0]);

hash = HASH1( arr[0] - arr[siz-1] );

for(idx=1; idx < siz; idx++) {
        hash ^= HASH1(arr[idx] - arr[idx-1] );
        }

return hash;
}

unsigned arr1[] = {1,9,8,7};
unsigned arr2[] = {9,8,7,1 };

unsigned arr3[] = {1,8,9,7 };
unsigned arr4[] = {1,9,8,5 };

int main(void)
{
unsigned hash;

hash = hashdiff (arr1, 4); printf("%x\n", hash);
hash = hashdiff (arr2, 4); printf("%x\n", hash);
hash = hashdiff (arr3, 4); printf("%x\n", hash);
hash = hashdiff (arr4, 4); printf("%x\n", hash);

return 0;
}

結果：

./a.out
fee56452
fee56452
1100b22
fca02416

更新: {1,2,3,4} と {11,12,13,14} を同じ値にハッシュしたくない場合は、次のように違いを増やすことができます。

#define HASH1(v) ((v)*7654321)
#define HASH2(a,b) HASH1(3u*(a)-5u*(b))

unsigned hashdiff2(unsigned arr[], size_t siz)
{
unsigned idx;
unsigned hash;

if (siz < 1) return 0;
if (siz < 2) return HASH1(arr[0]);

hash = HASH2( arr[0] , arr[siz-1] );

for(idx=1; idx < siz; idx++) {
        hash ^= HASH2( arr[idx] , arr[idx-1] );
        }

return hash;
}
于 2013-08-20T10:21:53.863 に答える
1

時折発生するハッシュ衝突をあまり気にしない場合は、単純にすべての要素の合計をハッシュとして取得できます (ただし、浮動小数点の問題には注意してください)。これは、ベクトルの回転に対して不変であるためです。xorまたは、個々の要素のすべてのハッシュを合計することもできます。後続の要素の違いに基づいて何かを計算することもできます (最後の要素から最初の要素まで折り返します)。ローテーションに対して不変であるこれらのプロパティのいくつかを一緒に追加すると、2 つの「等しくない」配列が同じハッシュを生成する可能性はかなり低くなります。多分何かのような

n = length(x)
rot_invariant_hash = hash(n) + sum(hash(x[i])) + sum(hash(x[mod(i+1, n)] - x[i]))

ここで、XOR などの他の可換 (?) 演算のすべての合計を置き換えることができます。また、差分に適用されるハッシュ関数が恒等関数でないことを確認してください。そうしないと、これらの部分がすべてゼロになります。これにはすべて O(n) の計算時間がかかります。

単なる好奇心: 意図したアプリケーションは何ですか?

于 2013-08-20T10:09:37.657 に答える
1

b1 をそれ自体と連結すると、次のようになります。

[1,9,8,7,1,9,8,7]

この配列には、元の配列の巡回順列がすべて含まれています。

次に、長さ 4 のすべての部分配列のハッシュを計算し、これらを結合して結合すると、一意のハッシュが得られます。配列のサイズによっては、ハッシュ関数の計算に最適化が必要になる場合があります。

編集:最初のものと等しい最後の部分を除くすべての部分配列!

于 2013-08-20T08:55:18.293 に答える