Clever Geek Handbook

短いドキュメントのあいまいな重複の定義

文書のあいまいなコピーを判別するためのシンプルだが効果的なアルゴリズムを共有したい。 この目的のために帯状疱疹アルゴリズムを使用することに関する多くの記事があります。 噂によると、大規模な検索エンジンは自宅で非常によく似たアルゴリズムを使用しています。 ただし、帯状疱疹は短い（3〜5文）文書にはあまり適していないことは誰もが認めています。 そして、私の仕事では、そのような文書を正確に扱う必要がありました。 解決策として、彼らはテキストをループして長くすることを提案していますが、これは非常に正しい解決策ではないようです、重複認識の精度はまだ低いでしょう。



したがって、私が使用したアルゴリズムの説明：



まず、テキストのコレクションにインデックスを付ける必要があります



  1. 各コレクションテキストをこのテキストの単語の配列に変換します。これは、以前にhtmlタグ、数字、その他の不要な情報を切り取りました。

  2. 15個の最も長い単語を選択します。テキスト自体が15個の単語より短い場合でも、4文字より短い単語はいずれの場合も使用されません。

  3. 選択した各単語に対して、チェックサム（crc32など）を計算し、「合計のID」、「ドキュメントのID」、「合計」の形式でデータベースに金額を書き込みます。

  4. 別の表では、テキスト自体のいくつかの特性を記述します。「md5」と「チェックサム付きの表に分類された単語の数」です。 2番目のフィールドは、適切な長さの15ワードを見つけることができなかったテキストに必要です。条件に応じて、これはワード単位のドキュメントの長さです。





次の構造のテーブルを使用します。



CREATE TABLE `items_hashes` (

`id` int(11) NOT NULL auto_increment,

`doc_id` int(11) NOT NULL,

`word_hash` int(11) NOT NULL,

PRIMARY KEY (`id`)

);



CREATE TABLE `items_hashes_summary` (

`doc_id` int(11) NOT NULL,

`full_hash` char(32) NOT NULL,

`length` smallint(11) NOT NULL,

PRIMARY KEY (`doc_id`)

);







テキストの一意性を確認してください



すべてのドキュメントのインデックスが作成されたら、コレクション内の一意性についてテキストをチェックできます。 これを行うには、次のものが必要です。

  1. items_hashes_summaryテーブルのデータを使用して、コレクションのドキュメントと完全に一致することを確認します。 そのような一致が見つかった場合、次の手順は意味をなさず、それ以外の場合はさらに進みます。

  2. チェックするテキストについては、前のリストの最初の3つのステップを実行しますが、データベースにチェックサムをまだ書き込まないでください。

  3. 分析されたドキュメントに一致する単語およびこれらの一致の数を含むデータベース内のドキュメントを検索します。 次のような方法でこれを行うことができます。



    SELECT doc_id, COUNT(id) as intersects FROM items_hashes

    WHERE (word_hash = %cur_doc_hash1% OR word_hash = %cur_doc_hash2% OR ... )

    GROUP BY doc_id

    HAVING intersects > 1







    （たとえば、HAVINGインターセクト> 5以上など、大きなコレクションで書く価値があります。そうしないと、さらなる処理が遅くなる可能性があります）

  4. ここで、見つかった各ドキュメントとの割合で「類似度」を見つけます。これは、式によって計算されます。



    $類似性=（$インターセクション/ $長さ）* 100、



    ここで、$ lengthは、比較されたドキュメントの最短の長さです。

    $ intersecs-一致する単語の数。



    コレクションドキュメントとの「類似度」が80％を超える場合、ドキュメントは一意ではないと考えます。タスクに別の値を選択する必要がある場合があります。





インデックス化されたコレクション内にすでに類似のテキストのペアを見つけるタスクがある場合、これも実行できます。最後から2番目のステップでクエリを変更するだけで、ドキュメントとそれ自体の共通部分が検索されません。



それはすべて非常に高速に動作します。 いずれにせよ、12,000のドキュメントのコレクションと非常に弱いVPSで問題はありません。 また、仮想マシンで7万件のドキュメントをテストしましたが、すべてが非常に高速でした。



ここで実際にどのように機能するかを感じることができます 。 アナウンスを受け取り、何かを変更して、新しいものとして追加してみてください。 非常によく似たものがデータベースに既に存在することをすぐに言わなければなりません。 突然広告を変更しすぎて追加される場合にのみ、後で削除することを忘れないでください;）



ユーザーは依然として同じコンテンツ広告を公開することができますが、そのためには、ほとんどすべてを言い換えなければなりません。 誤検知はまだ確認されていません。



PHPの実装



わかりやすくするために、このアルゴリズムを実装するプロジェクトから2つのクラスを引き裂いて、pastebin.comに配置しました。 ドキュメントハッシュを受信するクラス （汎用で、すべてのプロジェクトで使用可能）とモデルクラス （プロジェクトで使用する準備ができていません）、修正するのは難しくないと思います）。



PSこれはハブに関する私の最初のトピックですので、何かが間違っていても傷つけないでください。



UPD：カルマの皆さんに感謝します。今、私はそれを「開発」ブログに転送できます。


More articles:


All Articles