algorithm - 大規模なデータセット間で重複/類似したテキストを検出しますか？

Question

私は数千のレコードを持つ大規模なデータベースを持っています。ユーザーが自分の情報を投稿するたびに、同じ/類似のレコードがすでに存在するかどうかを知る必要があります。この問題を解決するためのアルゴリズムやオープンソースの実装はありますか？

私たちは中国語を使用しています。「類似」とは、レコードの内容が最も同じで、80％〜100％が同じである可能性があることを意味します。各レコードは大きくなりすぎず、約2k〜6kバイトになります

Answer 1

http://d3s.mff.cuni.cz/~holub/sw/shash/

http://matpalm.com/resemblance/simhash/

Answer 2

この回答は非常に複雑なクラスです（最悪の場合は5次であり、データベースを最初に検証するのは4次で、次にレコードを追加するために4次/ 4次であると予想されます）。そのため、拡張性が低く、残念ながらありません。私が今考えることができるはるかに良い答え。

このアルゴリズムはRatcliff-Obershelpアルゴリズムと呼ばれ、Pythonのdifflibに実装されています。アルゴリズム自体は、3次時間の最悪の場合であり、2次式が予想されます。次に、2次式であるレコードの可能なペアごとにそれを行う必要があります。もちろん、レコードを追加する場合、これは線形にすぎません。

編集：申し訳ありませんが、ドキュメントを読み間違えました。difflibは3次ではなく、2次のみです。他のアルゴリズムではなく、それを使用してください。

Answer 3

shngle-min-hashテクニックを見てください。これがあなたを助けることができるプレゼンテーションです。

Answer 4

私が似たようなことをするために使用したアプローチの1つは、単語の統計に基づいて通常の検索インデックスを作成し、そのインデックスに対する検索であるかのように新しいアイテムを使用することです。高い場合、新しいアイテムはあまりにも似ています。間違いなく、標準のテキスト検索ライブラリのいくつかをこれに使用できますが、数千のレコードしかない場合は、独自のレコードを作成するのは非常に簡単です。