6

知覚的なハッシュを生成するtineyeに似たプロセスがあり、これらは32ビットintです。

将来的にはこれらをSQLデータベース（おそらくnosqlデータベース）に保存する予定です。

しかし、ハッシュの類似性に基づいてレコードを取得する方法に困惑しています。

何か案は？

4

3 に答える 3

14

一般的なアプローチ（少なくとも私には一般的です）は、ハッシュビット文字列をいくつかのチャンクに分割し、これらのチャンクをクエリして完全に一致するようにすることです。これは「プレフィルター」ステップです。次に、返された結果に対してビット単位のハミング距離の計算を実行できます。これは、データセット全体のより小さなサブセットにすぎないはずです。これは、データファイルまたはSQLテーブルを使用して実行できます。

つまり、簡単に言うと、DBに32ビットのハッシュがたくさんあり、「クエリ」ハッシュから4ビットのハミング距離内にあるすべてのハッシュを検索するとします。

  1. 4つの列を持つテーブルを作成します。各列には、32ビットハッシュの8ビット（文字列または整数として）スライス、islice1から4が含まれます。

  2. qslice1から4で同じ方法でクエリハッシュをスライスします。

  3. のいずれかになるようにこのテーブルをクエリしますqslice1=islice1 or qslice2=islice2 or qslice3=islice3 or qslice4=islice4。4 - 1これにより、クエリハッシュから3ビット（）以内にあるすべてのDBハッシュが得られます。

  4. 返されたハッシュごとに、クエリハッシュを使用してペアごとに正確なハミング距離を計算します（4つのスライスからインデックス側のハッシュを再構築します）

ステップ4の操作の数は、テーブル全体の完全なペアワイズハミング計算よりもはるかに少ないはずです。

このアプローチは、モーゼスチャリカルによって、その「simhash」独創的な論文とそれに対応するGoogle特許で最初に説明されました。

  1. ハミング空間での近似最近傍探索

[...]

それぞれdビットで構成されるビットベクトルが与えられた場合、ビットのN = O（n 1 /（1+））ランダム順列を選択します。ランダム置換σごとに、ビットベクトルのソートされた順序Oσを、σによって置換されたビットの辞書式順序で維持します。クエリビットベクトルqが与えられると、次のようにして近似最近傍を見つけます。

各順列σについて、Oσで二分探索を実行して、qに最も近い2つのビットベクトルを見つけます（σによって順列されたビットによって取得される辞書式順序で）。ここで、qに一致する最長のプレフィックスの長さの順に、バイナリ検索によって返された位置の上下の要素を調べる、ソートされた順序Oσのそれぞれで検索します。

Monika Henzigerは、彼女の論文「ほぼ重複するWebページの検索：アルゴリズムの大規模な評価」でこれを拡張しました。

3.3アルゴリズムCの結果

各ページのビット文字列を重複しない12個の4バイト部分に分割し、20B個を作成し、少なくとも1個の共通部分を持つすべてのページのC類似度を計算しました。このアプローチでは、最大11の違い、つまりC類似度373のページのすべてのペアを見つけることが保証されていますが、大きな違いがある場合は一部を見逃す可能性があります。

これは、Gurmeet Singh Manku、Arvind Jain、およびAnishDasSarmaによる論文「 DetectingNear-DuplicatesforWebCrawlings 」でも説明されています。

  1. ハミング距離の問題

定義：fビットフィンガープリントのコレクションとクエリフィンガープリントFが与えられた場合、既存のフィンガープリントが最大kビットでFと異なるかどうかを識別します。（上記の問題のバッチモードバージョンでは、単一のクエリフィンガープリントではなく、一連のクエリフィンガープリントがあります）

[...]

直感：2dfビットの真にランダムなフィンガープリントのソートされたテーブルを考えてみましょう。表の最上位のdビットだけに注目してください。これらのdビット数のリストは、（a）かなりの数の2 dビットの組み合わせが存在し、（b）非常に少数のdビットの組み合わせが複製されるという意味で「ほぼカウンター」になります。一方、最下位のf −dビットは「ほぼランダム」です。

ここで、| d −d|となるようにdを選択します。は小さな整数です。テーブルはソートされているため、d個の最上位ビット位置でFに一致するすべてのフィンガープリントを識別するには単一のプローブで十分です。| d −d|以降 が少ない場合、そのような一致の数も少ないと予想されます。一致するフィンガープリントごとに、最大でkビット位置でFと異なるかどうかを簡単に判断できます（これらの違いは、当然、f − dの最下位ビット位置に制限されます）。

上記の手順は、kビット位置でFとは異なる既存のフィンガープリントを見つけるのに役立ちます。これらはすべて、Fの最下位f − dビットに制限されます。これにより、かなりの数のケースが処理されます。すべてのケースをカバーするには、次のセクションで正式に概説するように、少数の追加のソート済みテーブルを作成するだけで十分です。

PS：これらの優れた頭脳のほとんどは、FWIWのあるレベルで、またはいつかGoogleに関連付けられていました。

于 2017-11-25T16:07:25.193 に答える
1

ハミング距離を見つけるには、ビット単位の加算と減算（整数の＆と〜）を使用してこれらを計算できます。

SQLはこの種の処理用には作られていません。大規模なデータセットでの比較は非常に面倒になり、システムの強度を利用するクエリの速度にはなりません。そうは言っても、私は同じようなことをしました。

これにより、個人差が生じます。これは、完全なデータセットで実行して順序付けする必要があり、せいぜい厄介です。より高速に実行したい場合は、「地域」によるインデックス作成や、データ内の自然なグループの検索などの戦略を使用する必要があります。アンブレラクラスタリング戦略などがあります-多くの文献があります。ただし、ほとんどの従来のデータベースシステムでは厄介です。

于 2012-06-22T14:31:20.213 に答える
1

Davidの議論は正しいですが、データがあまりない場合は、SQLのバイナリ文字列のハミング距離を確認してください。

于 2013-04-01T21:43:24.013 に答える