問題タブ [murmurhash]

バイト配列で murmur2 ハッシュを使用していますが、バイトのサブセットのみをハッシュしたいのですが、murmur2 では 0 から始まる配列をハッシュすることしかできませんが、0 以外の開始オフセットと終了オフセットを指定したいと考えています。配列。

さまざまな変更を試みましたが、常にハッシュ衝突テストが 0 から非常に高い数値になります。murmur2 のような単一の小さなメソッドには適合しないため、murmur3 は使用したくありません。テストでは、murmur2 も少し高速です。

試してみたい人のための衝突テスターはこちら

注: 上記の衝突テストには、8 GB の RAM を搭載した PC が必要です。

Ruby のハッシュは、そのハッシュ値 (文字列と数値) を使用するだけです。内部的には、Murmur ハッシュ関数を使用します。2 つの異なるキーに対して同じハッシュ値を持つ確率がゼロではないことを考えると、どうすればそれができるのだろうか。

この Java バージョンで実装されているMurmurHash3_x64_128の逆関数を探しています。違いは、初期化と、シードをいくつかのマジック ナンバーで xor することにあることに注意してください。また、実際には、ビット 33 ～ 64 のみに関心があります ( 32 -> 32 ビットの簡略化されたバージョンの逆を見つけようとしているためです。h1h2

残念ながら、アルゴリズムのさまざまなバリエーションを使用している素敵なブログ投稿を見つけました。

ウィキによると、アルゴリズムは暗号学的に安全ではないため、逆が存在するはずです。

MurmurHash3_x86_128() にどのパラメータを指定すればよいか混乱しています。murmurhash3 コードはhttps://github.com/aappleby/smhasher/blob/master/src/MurmurHash3.cppにあります。メソッドの定義を以下に示します。

上記のメソッドで次の値を渡しましたが、コンパイラでセグメンテーション エラーが発生しました。私は何を間違っていますか？

Ubuntu 16.04 を使用しています。Murmurhash python ライブラリをインストールしようとしていますが、エラーがスローされます: コマンド 'x86_64-linux-gnu-gcc' が終了ステータス 1 で失敗しました。インターネットで調べたところ、このエラーはpythonヘッダーファイルが見つからないことが原因であると言われています。だから私はした

しかし、まだエラーがあります。エラーは、Anaconda がインストールされているためですか、それとも何ですか? このエラーを修正する方法など、誰かが私を助けてくれますか? エラーは次のとおりです。

Python と Scala の両方で文字列を MurmurHash する必要があります。しかし、それらは非常に異なる結果をもたらしています。Scala の組み込みMurmurHash3ライブラリは、私がオンラインのものを含めて試した他のライブラリと同じ結果をもたらさないようです。奇妙なことに、複数の文字ではなく、1 つの文字で一致するように見えます。ここではいくつかの例を示します。

パイソン:

スカラ:

Javaが署名していて、PythonのC実装がunsignedを使用していることを知っているので、signedおよびunsigned intで遊んでみました。しかし、NumPy を使用して signed int に変換しても、何の助けにもなりません。この Web サイトは、Python の実装に同意しているようです。

http://murmurhash.shorelabs.com/

ここで何が起こっているのかについてのアイデアはありますか?

多くのキー値がある場合、MurmurHash3_x86_128() をどのように呼び出すべきか混乱しています。murmurhash3 コードはhttps://github.com/aappleby/smhasher/blob/master/src/MurmurHash3.cppにあります。メソッドの定義を以下に示します。

以下に示すように、for ループを使用して別のキー値を渡していますが、ハッシュ値の戻り値は同じです。for ループを削除して個々のキー値を渡すと、値が異なります。私は何を間違っていますか？

Murmurhash3 を使用して、テキスト エントリの一意のハッシュを作成しています。テキスト エントリが作成されると、32 ビットのハッシュ整数を返すこの php 実装を使用して、ハッシュ値を取得します。ハッシュは BINARY(16) データベース列に格納されます。また、既存のデータベースを更新する必要があるため、この MySql 実装を使用してデータベースを更新しています。PHPで作成したハッシュに合わせるために、ベース変換して小文字化しています。

それは約 80% の確率で php バージョンと一致しますが、明らかにそれをカットするつもりはありません。たとえば、文字列「engtest」をハッシュする15d15mと、php と3uqiuqaMySql で作成されます。ただし、文字列「engtest 文」は両方で同じハッシュを作成します。私は何が間違っているのでしょうか？

(私は StackOverflow を初めて使用し、StackOverflow アカウントの権限が非常に低いため、この投稿で問題をよりよく説明するために多くの URL を追加することは許可されていません)。

概要

murmurhash3.js（以下）と同じハッシュを生成するように（以下）を変更する方法を教えてくださいMurmurHash3.cpp。必要なものに基づいて、MurmurHash3.cpp の単純な python コード「simple_python_wrapper.py」を提供します。sklearn がインストールされている場合、simple_python_wrapper.py はコンピューターで動作するはずです。

私の機械学習プロジェクトの 1 つで、from sklearn (a Python Machine Learning Library):Murmurhash3.cppを使用している間 (以下に表示) を頻繁に使用しました。sklearn の実装/インポート ツリーの奥深くで使用します。transformfrom sklearn.feature_extraction._hashing import transformtransformMurmurhash3.cpp

詳細

ハッシュ % (2^18) {つまり、"ハッシュ係数 2^18"} MurmurHash3.cpp に基づく

ハッシュ % (2^18) {つまり、"ハッシュ係数 2^18"} に基づく murmurhash3.js

murmurhash3.js

ここにHTMLコード+ JavaScriptをテストするために使用しているJavascriptがあります

https://jsbin.com/gicomikike/edit?html,js,output

simple_python_wrapper.py

これは、sklearn のインポート ツリーで MurmurHash3.cpp を利用します。

出力

MurmurHash3.cpp

もう少し説明しましょう。

from sklearn.feature_extraction._hashing import transformこのhttps://github.com/scikit-learn/scikit-learn/blob/master/sklearn/utils/src/MurmurHash3 に基づいて構築されたこれを 利用 するこのコードhttps://github.com/scikit-learn/scikit-learn/blob/412996f09b6756752dfd3736c306d46fca8f1aa1/sklearn/feature_extraction/_hashing.pyx を利用 します。 cpp。したがって、MurmurHash3.cpp は非常に重要です。JavascriptコードとMurmurHash3.cppが同じ結果を生成するように、この正確なMurmurHash3.cppのJavascriptバージョンが必要です。from sklearn.utils.murmurhash cimport murmurhash3_bytes_s32https://github.com/scikit-learn/scikit-learn/blob/master/sklearn/utils/murmurhash.pyx

これが必要なのは、機械学習ツールの一部をオンラインで利用できるようにしたいためであり、ハッシュはクライアントの Web ブラウザーで実行する必要があります。

これまでのところ、MurmurHash3 の Javascript 実装をいくつか見つけました。ただし、murmurhash3.jshttps://github.com/whitequark/murmurhash3-js/blob/master/murmurhash3.jsは、sklearn で使用される MurmurHash3.cpp に (コード構造に関して) 最も近いようです。しかし、私はまだ両方から同じハッシュを取得していません。

murmurhash3.js（上記）と同じハッシュを生成するように（上記）を変更する方法を教えてくださいMurmurHash3.cpp。

非常に幅の広い C* テーブルがあります。それらが広くなりすぎるのを防ぐために、私は自分にぴったりの戦略に出会いました. こちらの動画で紹介されました。 パーティションを賢くバケット化する

この戦略の良い点は、「ルックアップ テーブル」が必要ないことです (高速です)。悪い点は、バケットの最大量を知る必要があり、最終的にバケットがなくなることです。使用します (スケーラブルではありません)。バケットの最大サイズを知っているので、これを試してみます。

テーブルの主キーからハッシュを計算することにより、これを残りの主キーとともにバケット部分として使用できます。

ハッシュが特定の主キーに対して常に同じであることを確認するために、次の方法を思いつきました（と思いますか？）。

グアバハッシュの使用:

私が sha512 を使用する理由は、最大 256 文字 (512 ビット) の文字列を持つことができるようにするためです。そうしないと、結果が同じになることはありません (私のテストによると思われます)。

私はハッシングの第一人者とはほど遠いので、次の質問をしています。

要件:異なるノード/マシンでの異なる JVM 実行間で、特定の Cassandra プライマリ キーの結果は常に同じである必要がありますか?

1. 言及された方法に頼って仕事をすることはできますか?
2. 特定の文字列に対して常に同じ結果が得られるように、大きな文字列をハッシュするより良い解決策はありますか?
3. 常に文字列からハッシュする必要がありますか?それとも、C* の主キーに対してこれを行うより良い方法があり、常に同じ結果を生成する可能性がありますか?

特定のテーブルのデータ モデリングについて話し合うつもりはありません。バケット戦略が必要なだけです。

編集：

さらに精巧にしてこれを思いついたので、文字列の長さは任意です。これについてどう思いますか？