問題タブ [locality-sensitive-hash]

C/C++/Java/C# で比較的理解しやすい (そして実装しやすい) 局所性に敏感なハッシュの例はありますか?

概念についてもっと学びたいので、いくつかのテキストファイルで実装を試して、それがどのように機能するかを確認したいので、高性能などは必要ありません...ハッシュの単なる例同様の入力に対して同様のハッシュを返す関数。後で例を挙げて、それからさらに学ぶことができます。:)

Cのデータ構造（ハッシュテーブル）をいじろうとしています。ビルド済みのハッシュテーブル ライブラリ (STL など) は使用していません。これがどのように機能するかをよりよく理解したいからです。ここでは、要素のリストを含むハッシュ テーブルを作成します。各要素には、キーと文字列要素データ (文字の配列)、および文字列要素データの長さが含まれます。

私の実装は機能しますが、同僚の 1 人と話し合った後、私の実装は効率的ではないと言われました。特に、私の実装はキャッシュに対応していないため、ハッシュテーブルのルックアップが非効率的でした。私は彼の説明をよく理解していませんでした。

だから私は知りたいのですが、キャッシュ対応の局所性の実装は実際には何を意味するのでしょうか?

ルックアップ時にキャッシュ対応の局所性プロパティを使用して、ハッシュ テーブルの実装をより効率的にするにはどうすればよいですか? このための構造を構築するより良い方法と、要素を整理する (検索を行う) より良い方法はありますか?

これが私がこれまでに行ったことです：

HASHTBL.h

HASHTBL.c

メインファイル

プログラムで LSHKIT を使用して、いくつかの高次元ベクトルの類似性を測定する必要があります。http://lshkit.sourceforge.net/で見つけることができる lshkit と呼ばれる lsh のライブラリがあります 。まず、ビルドできなかったので、「プロジェクトに LSHKIT ソースを直接追加する」セクション 3.2 に進みました。
すべての src コードを 1 つのプロジェクトに入れ、エラーを修正しましたが、それを使用してコンパイルする方法がわかりません。サンプルデータ用です（lshkit Webサイトで提案されています）

関数を呼び出して結果を確認する方法を教えてください。ありがとう

2 つの名前と 1 つの住所の「レコード」(基本的には CSV 文字列) があります。互いに類似しているレコードを見つける必要があります。基本的に、名前と住所の部分はすべて、人間が解釈したかのように「似ている」ように見えます。

この優れたブログ投稿 ( http://knol.google.com/k/simple-simhashing# ) のアイデアを使用して、単純な SimHash を作成しました。2 つ以上の文字列に対する SimHash の結果が同じである場合、このサブセットのすべてのレコードを、セットのすべてのレコードを他のすべてのレコードと比較する O(n^2) であるきめの細かいマッチング プログラムに渡します。

SimHash 部分には、データグラムのサイズ (基本的には文字列に対するサイズ n のスライディング ウィンドウ) と、SimHash の計算に使用する必要がある (ランダムな) ハッシュの数を決定するために使用する反復回数を定義できるパラメーターがあります。 . これまでのところ、データグラム サイズは 4 で、4 つのハッシュを使用して SimHash を計算しています。いろいろな組み合わせを試しましたが、今のところこれが一番いいです。

私が直面している問題は、このメソッドが私が持っているデータ セットの重複の約 80% を見つけることです。上記の非常に遅い O(n^2) 完全一致に対してデータセット全体を検証したため、これを知っています。O(n^2) マッチャは 10^4 未満のデータ セットには問題ありませんが、サイズ 10^8 のセットを実行する必要があるため、すぐに実行できなくなります。

SimHash の精度を高めて、より多くの「類似」レコードに同じ SimHash 番号がタグ付けされるようにする方法について、アイデア、提案、または考えはありますか?

編集: SimHashing の前に、すべての ![0-9A-Z] 文字を大文字にして削除します。一致させるべきものの例 (スペルミスは意図的なものです):

• JOHN SMITH、123 ANY STREET SOMETOWN ZIP
• ジョニー・スミス、123 ANY STRET
• SOMETOWN ZIP ROBERT PARKER, 442 ANY STREET サムタウン ZIP

ここで、1 と 2 は似ていますが、3 は似ていません。出力は次のようになります: 1 + 2

数十万のデータポイントを持つ高次元 (私の場合は 32) のデータセットでほぼ均等に分散されたデータに対して、Locality Sensitive Hashing による最近傍検索をサポートする軽量の Java ライブラリを探しています。

クエリのバケット内のすべてのエントリを取得するだけで十分です。本当に必要なものは、問題に含まれるいくつかのフィルターパラメーターを考慮して、別の方法で処理できます。

私はすでにlikelikeを見つけましたが、もう少し小さく、他のツール (likelike の場合は Apache Hadoop など) を必要としないものがあることを願っています。

LSHは、高次元のプロパティを持つ同様のアイテムを見つけるための良い方法のように思われることに気づきました。

論文ht​​tp://www.slaney.org/malcolm/yahoo/Slaney2008-LSHTutorial.pdfを読んだ後、私はまだそれらの公式と混同しています。

誰かがその簡単な方法を説明するブログや記事を知っていますか？

私はオーディオフィンガープリントシステムに取り組んでおり、最近いくつかの論文と調査を行いました。特にこのページ：c＃AudioFingerprintingとLocality Sensitive Hashing

これで、32ミリ秒のオーディオごとに一連のフィンガープリントを取得しました。私がやりたいのは、LSHまたは他の類似性保存方法を使用して、これらの個々のフィンガープリントを（それらのシーケンスではなく）ハッシュすることです。LSHについて私が理解したことから、LSHは多次元ベクトルで機能し、ハミング空間で比較できるバイナリ文字列を生成します。

ここでの私の問題は、私が持っている指紋が多次元ではないということです。それらは単一の長整数です。LSHを使用してこれらをハッシュするにはどうすればよいですか？一次元スカラーを（類似性を維持する方法で）ハッシュする方法はありますか？

私は私の質問に答えることができませんでした。

他の人と比較して忠実度を見つけることができるハッシュを生成するハッシュメソッドが必要です、

たとえば、「母」、「父」の2つの文字列が必要であり、2つのハッシュを比較すると、「その他」のためにそれらの間に忠実度があると表示されます。

それができるハッシュ方法はありますか？

ありがとうございました