問題タブ [simhash]

入力の小さな変化が出力の小さな変化になるハッシュ関数はありますか? たとえば、次のようなものです。

Java で実装されたsimhash関数に遭遇した人はいますか?

すでに検索しましたが、何も見つかりませんでした。

問題は、テキスト文書のコレクションがあり、入力文書に最も類似した文書を取得したいということです。入力テキスト ドキュメントは完全に一致するか、部分的に変更されている可能性があります。アルゴリズムは非常に高速でなければなりません。

現在、コレクション ドキュメントから指紋を取得する simhash を発見しました。同じことを行う他のアルゴリズムはありますか?

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

ハッシュ関数の使用に問題があります。ドキュメント内のすべての単語にいくつかの番号（128ビットまたは64ビット）を割り当てる必要があります。したがって、「類似性」のハッシュ値は「類似性」に近い必要があります。つまり、similarity => 10022（say）の値がある場合、similar=>10025になります。これは似たような言葉で近づくはずです。また、異なる名前のハッシュ値も類似している必要があります。つまり、「john」のハッシュ値も「michel」または「sita」とほぼ同じである必要があります...など。誰かがそれについて何か考えを持っているなら。

よろしくお願いします。:)

ここで実装されているように、「距離」が2つの文字列間の類似性スコアであるペアワイズ距離マトリックスを構築したいと思います。以前に他の計算に使用したことがあり、簡単な並列化が優れているため、これを行うためにsci-kit Learnのペアワイズ距離法を使用することを考えていました。

関連するコードは次のとおりです。

stringsのように見え['foo', 'bar', 'baz']ます。

これを試すと、エラーがスローされますValueError: could not convert string to float。これを言うのは本当にばかげているかもしれませんが、なぜここで変換を行う必要があるのか​​、なぜそのエラーをスローしているのかはわかりませんmetric。入力が浮動小数点数である必要があるのはなぜですか? また、simhash の「距離」に基づいてこのペアごとの距離行列を作成するにはどうすればよいですか?

Macでsimhashを実行するための同じセットアップとコードがありますが、動作します。

しかし、Ubuntuで実行すると、simhashの実装自体にバグがあると不平を言います。

このような問題に遭遇したことがありますか？

objs = [(str(k), Simhash(v)) for k, v in index_data.items()] ファイル "/usr/local/lib/python2.7/dist-packages/simhash-1.1.2-py2. 7.egg/simhash/ init .py"、30 行目、init self.build_by_text(unicode(value)) で UnicodeDecodeError: 'ascii' コーデックは位置 34 のバイト 0xf6 をデコードできません: 序数が範囲内にありません (128)

次のようなデータフレームがあります。

Apple -> aple などの文字列の距離を計算したい。最終結果は次のとおりです。

現在、これは私が使用しているコードです（ただし、大きなデータの場合は非常に遅いです）：

距離を効率的に計算するのを手伝ってくれる人はいますか?