10

Scala でCount-Min Sketchアルゴリズムを実装しようとしているので、k 個のペアごとに独立したハッシュ関数を生成する必要があります。

これは私がこれまでにプログラムしたことのあるものよりも低レベルであり、アルゴリズム クラス以外のハッシュ関数についてはあまり知りません。

MD5 や MurmurHash などのハッシュ関数を使用する必要がありますか? f(x) = ax + b (mod p)p が素数で、a と b がランダムな整数である という形式の k 個のハッシュ関数を生成するだけですか? (つまり、誰もがアルゴリズム 101 で学習するユニバーサル ハッシング ファミリー)

私は生の速度よりも単純さを求めています (たとえば、実装が簡単な場合は、5 倍遅いものを使用します)。

4

2 に答える 2

5

ScalaはすでにMurmurHash実装されています（それはscala.util.MurmurHash）。非常に高速で、値の分散に非常に優れています。暗号化ハッシュはやり過ぎです。必要な時間の数十倍から数百倍の時間がかかります。k最初にさまざまなシードを選択するだけで、品質がほぼ暗号化されているため、kほぼ独立したハッシュコードを取得できます。（2.10では、おそらく使用に切り替える必要がありscala.util.hashing.MurmurHash3ます。使用法はかなり異なりますが、ミキシングでも同じことができます。）

近い値だけをランダムに遠い値にマッピングする必要がある場合、これは機能します。衝突を回避したい場合（つまり、AとBがハッシュ1を使用して衝突する場合、ハッシュ2を使用しても衝突しない可能性があります）、少なくとももう1つのステップを実行して、オブジェクト全体ではなくそのサブコンポーネントをハッシュする必要があります。ハッシュが別の方法で開始する機会があります。

于 2012-08-25T16:38:57.290 に答える
2

おそらく最も簡単な方法は、いくつかの暗号化ハッシュ関数を使用して、さまざまなバイト シーケンスを「シード」することです。ほとんどの実用的な目的では、結果は独立している必要があります。これは、暗号化ハッシュ関数が持つべき重要なプロパティの 1 つであるためです (メッセージの一部を置き換えると、ハッシュは完全に異なるはずです)。

私は次のようなことをします：

// for each 0 <= i < k generate a sequence of random numbers
val randomSeeds: Array[Array[Byte]] = ... ; // initialize by random sequences

def hash(i: Int, value: Array[Byte]): Array[Byte] = {
    val dg = java.security.MessageDigest.getInstance("SHA-1");
    // "seed" the digest by a random value based on the index
    dg.update(randomSeeds(i));
    return dg.digest(value);
    // if you need integer hash values, just take 4 bytes
    // of the result and convert them to an int
}

編集: Count-Min Sketch の正確な要件はわかりません。単純な has 関数で十分かもしれませんが、最も単純なソリューションではないようです。

結果のハッシュ関数が非常に異なるという非常に強力な保証があり、標準ライブラリを使用するだけで簡単に実装できるため、暗号化ハッシュ関数を提案しました。

一方、 と の形式の 2 つのハッシュ関数がある場合f1(x) = ax + b (mod p)、単純な線形公式 を使用してf2(x) = cx + d (mod p)( を知らなくても) 別のハッシュ関数を使用して一方を計算できます。これは、それらがあまり独立していないことを示唆しています。そのため、ここで予期しない問題が発生する可能性があります。xf2(x) = c / a * (f1(x) - b) + d (mod p)

于 2012-08-25T09:01:58.777 に答える