私は現在、多くのテキストコンテンツを生成するストリーミングAPIに取り組んでいます。予想どおり、APIは多くの重複を提供し、重複に近いデータをフィルタリングするというビジネス要件もあります。
データストリームでの重複検出について少し調査し、安定したブルームフィルターについて読みました。安定したブルームフィルターは、偽陽性率に上限があるデータストリームで重複検出するためのデータ構造です。
しかし、私はニアデュプリケートを特定したいと思います。また、ニアエストネイバーの問題やニアデュプリケート検出で使用されるLSHやMinHashなどのハッシュアルゴリズムも調べました。
私はちょっと立ち往生していて、どのように進めるか、そして私が見ることができる論文/実装についての指針を探していますか？
まず、テキストをすべて小文字（または大文字）に正規化し、すべての非文字を空白に置き換え、複数の空白をすべて1つに圧縮し、先頭と末尾の空白を削除します。速度を上げるために、これらすべての操作をテキストの1つのパスで実行します。次にMD5、結果の文字列のハッシュ（またはより高速なもの）を取得します。MD5テーブル内のハッシュ（2つの64ビット整数として）のデータベースルックアップを実行します。存在する場合は完全に重複し、存在しない場合はテーブルに追加して次の手順に進みます。時間またはメモリ使用量に基づいて、古いハッシュを古くする必要があります。
ほぼ重複を見つけるには、正規化された文字列を潜在的な署名（部分文字列のハッシュ）に変換する必要があります。GregLindenによるSpotSigs論文とブログ投稿を参照してください。ルーチンSigs()が特定の文字列に対してこれを実行するとします。つまり、正規化された文字列xに対してSigs(x)、64ビット整数の小さな（1〜5）セットを返します。アルゴリズムのようなものを使用SpotSigsして、署名のテキスト内の部分文字列を選択できますが、データについて何か知っている場合は、独自の選択方法を作成するとパフォーマンスが向上する可能性があります。simhashアルゴリズムも確認することをお勧めします（コードはここにあります）。
Sigs()近い重複を効率的に見つける問題を考えると、一般に集合類似性結合問題と呼ばれます。このSpotSigsペーパーでは、メソッドと同様に、新しいセットを比較する必要があるセットの数を削減するためのいくつかのヒューリスティックについて概説しますsimhash。