k-wise 独立ハッシュ関数のファミリに属するハッシュ関数を使用する必要があります。関数を選択できる k-wise 独立ハッシュ関数のセットを生成できる、C、C++、または python の任意のライブラリまたはツールキットへの任意のポインター。
背景: ここでこのアルゴリズムを実装しようとしています: http://researcher.watson.ibm.com/researcher/files/us-dpwoodru/knw10b.pdf個別の要素の問題について。
私はこのスレッドを見てきました: Murmur ハッシュを使用してペアごとに独立したハッシュ関数を生成することについて言及しているk ペアごとに独立したハッシュ関数を生成します。k-wise独立ハッシュ関数に似たものがあるかどうか疑問に思っていました. 利用可能なものがない場合、そのような k-wise 独立ハッシュ関数のセットを構築することは可能でしょうか?
前もって感謝します。
「k-wise 独立ハッシュ関数」などというものはありません。ただし、関数の k-wise 独立ファミリがあります。
念のため、関数のファミリは、h がファミリからランダムに選択され、x_1 .. x_k および y_1 .. y_k が任意に選択される場合、「すべての i に対して、h(x_i) = y_i " は Y^-k であり、Y は y_i が選択された共同ドメインのサイズです。
2、3、4、および 5 のような小さい k に対して k ごとに独立であることが知られている関数のファミリがいくつかあります。任意の k の場合、多項式ハッシュを使用する必要がある可能性があります。これには 2 つのバリアントがあり、そのうちの 1 つは 2-independent ではないことに注意してください。実装するときは注意してください。
多項式ハッシュ ファミリは、a_0 から a_{k-1} までの k 個の定数を使用して、フィールド F からそれ自体にハッシュでき、a_i x^i の合計によって定義されます。ここで、x はハッシュするキーです。素数 p を法とする整数を F とすることで、体の算術演算をコンピュータに実装できます。ドメインと範囲をuint32_tなど。その場合、フィールド F_{2^32} を使用でき、Z_2 に対して多項式乗算を使用してから、そのフィールドで既約多項式による除算を使用できます。それ以外の場合は、p が 2^32 (または 64) より大きい Z_p で操作し、2^32 を法とする多項式の結果を取得できると思います。それはほぼ k-wise に依存しませんが、分析を進めるにはそれで十分な場合もあります。KNW アルゴリズムを再分析してハッシュ ファミリーを変更するのは簡単ではありません。
k ワイズ独立ファミリのメンバーを生成するには、お気に入りの乱数ジェネレータを使用して関数をランダムに選択します。多項式ハッシュの場合、それはa上記の s を選択することを意味します。/dev/random十分なはずです。
あなたが指摘した論文「個別要素問題の最適アルゴリズム」は素晴らしいもので、何度も引用されています。ただし、実装は簡単ではなく、big-O 表記に隠された定数があるため、HyperLogLog よりも遅くなるか、より多くのスペースを必要とすることさえあります。多くの論文で、このアルゴリズムの複雑さが指摘されており、HyperLogLog と比較して実行不可能であるとさえ言われています。個別の要素数の推定器を実装する場合は、以前のアルゴリズムから始めることができます。あなたの目標が教育である場合、そこには多くの複雑さがあります。目標が実用性である場合は、HyperLogLog ほど実用的ではないものを作成するだけでも大変な作業になる可能性があるため、KNW には近づかないようにする必要があります。
別のアドバイスとして、このアルゴリズムまたはハッシュを使用する他のランダムアルゴリズムについて学び、理解したい場合は、「Murmur ハッシュを使用する」または「xxhash から k 個の値を選択する」という提案をおそらく無視する必要があります。Murmur/xx は実際には問題ないかもしれませんが、それらは k-wise の独立したファミリではなく、このページのアドバイスの一部は意味的にも整形式ではありません。たとえば、「k 個の異なるハッシュが必要な場合は、k 個の異なるシードを使用して、同じアルゴリズムを k 回再利用するだけです」は、k ワイズ独立ファミリには関係ありません。実装したいこのアルゴリズムでは、ハッシュ関数を任意の回数適用することになります。「k個の異なるハッシュが必要」ではなく、n個が必要です最初に k に依存しないハッシュ ファミリからランダムに選択し、次に選択した関数をこのようなアルゴリズムへの入力であるストリーミング キーに適用することによって生成されるさまざまなハッシュ値。
「k-wise独立ハッシュ関数」とは何を意味するのか100％わかりませんが、2つのハッシュ関数を考え出し、それらの線形結合を使用することで、k個の異なるハッシュ関数を取得できます。
ブルーム フィルター モジュールに例があります : http://stromberg.dnsalias.org/svn/bloom-filter/trunk/bloom_filter_mod.py