Algoritma apa yang dapat saya gunakan untuk mendeteksi jika artikel atau posting merupakan duplikat?

17

Saya mencoba mendeteksi apakah artikel atau posting forum adalah entri duplikat dalam database. Saya telah memikirkan hal ini, sampai pada kesimpulan bahwa seseorang yang menduplikasi konten akan melakukannya menggunakan salah satu dari ketiganya (dalam penurunan yang sulit dideteksi):

  1. salin sederhana tempelkan seluruh teks
  2. salin dan tempel bagian-bagian teks yang digabungkan dengan miliknya
  3. menyalin artikel dari situs eksternal dan menyamar sebagai milik mereka

Mempersiapkan Teks Untuk Analisis

Pada dasarnya ada anomali; tujuannya adalah membuat teks semurni mungkin. Untuk hasil yang lebih akurat, teks "standar" oleh:

  1. Stripping duplikat spasi putih dan pemangkasan depan dan belakang.
  2. Baris baru distandarisasi untuk \ n.
  3. Tag HTML dihapus.
  4. Menggunakan RegEx yang disebut Daring Fireball URL dilucuti.
  5. Saya menggunakan kode BB dalam aplikasi saya sehingga masuk ke.
  6. (ä) ccented dan asing (selain Enlgish) dikonversi ke bentuk non asing.

Saya menyimpan informasi tentang setiap artikel di (1) tabel statistik dan di (2) tabel kata kunci.

(1) Tabel Statistik Statistik berikut disimpan tentang konten tekstual (seperti posting ini)

  1. panjang teks
  2. jumlah surat
  3. jumlah kata
  4. jumlah kalimat
  5. kata rata-rata per kalimat
  6. indeks keterbacaan otomatis
  7. skor kabut gunning

Untuk bahasa Eropa, Coleman-Liau dan Automated Readability Index harus digunakan karena mereka tidak menggunakan penghitungan suku kata, sehingga harus menghasilkan skor yang cukup akurat.

(2) Tabel Kata Kunci

Kata kunci dihasilkan dengan mengecualikan daftar besar kata-kata berhenti (kata-kata umum), misalnya, 'the', 'a', 'of', 'to', dll, dll.

Contoh data

  • text_length, 3963
  • letter_count, 3052
  • word_count, 684
  • kalimat_kount, 33
  • word_per_sentence, 21
  • gunning_fog, 11.5
  • auto_read_index, 9.9
  • kata kunci 1, terbunuh
  • kata kunci 2, petugas
  • kata kunci 3, polisi

Perlu dicatat bahwa sekali artikel diperbarui, semua statistik di atas dibuat ulang dan bisa menjadi nilai yang sama sekali berbeda.

Bagaimana saya bisa menggunakan informasi di atas untuk mendeteksi jika artikel yang pertama kali diterbitkan, sudah ada dalam database?

Saya tahu apa pun yang saya desain tidak akan sempurna, risiko terbesar adalah (1) Konten yang bukan duplikat akan ditandai sebagai duplikat (2) Sistem memungkinkan konten duplikat masuk.

Jadi algoritma harus menghasilkan angka penilaian risiko dari 0 menjadi duplikat risiko 5 menjadi duplikat mungkin dan 10 menjadi duplikat. Apa pun di atas 5 maka ada kemungkinan bagus bahwa konten tersebut duplikat. Dalam hal ini, konten dapat ditandai dan ditautkan ke artikel yang merupakan duplikat yang mungkin dan manusia dapat memutuskan apakah akan menghapus atau mengizinkan.

Seperti yang saya katakan sebelumnya saya menyimpan kata kunci untuk seluruh artikel, namun saya bertanya-tanya apakah saya dapat melakukan hal yang sama berdasarkan paragraf; ini juga akan berarti lebih jauh memisahkan data saya di DB tetapi juga akan membuatnya lebih mudah untuk mendeteksi (2) di posting awal saya.

Saya sedang berpikir rata-rata tertimbang antara statistik, tetapi dalam urutan apa dan apa yang akan menjadi konsekuensi ...

algorithms michael
sumber
Jika itu benar-benar cocok, Anda cukup mengatur bidang menjadi unik. Jika tidak, Anda harus memutuskan pada titik mana teks dapat dianggap sebagai salinan atau karya yang diturunkan dengan cermat.
James P.
2
Ada banyak arah di mana analisis semacam ini bisa berjalan. Orang-orang menulis seluruh buku tentang topik semacam ini. Jika tujuan Anda adalah untuk menentukan "kedekatan relatif" Anda benar-benar memiliki sedikit pilihan selain menggali apa yang disebut Pemrosesan Bahasa Alami dan Pembelajaran Mesin . Itulah yang disebut oleh para ilmuwan komputer, tetapi itu benar-benar hanya analisis statistik tingkat lanjut. Titik awal yang baik mungkin melihat pada jarak levenshtein, tetapi statistik "bodoh" seperti jumlah kata / kalimat akan sangat sedikit membantu Anda.
rdlowrey
1
Juga, sebelum dimigrasikan dari SO, ini ditandai [php], jadi Anda dapat memeriksa fungsi levenshtein asli php
rdlowrey
Ide bagus untuk memeriksakan manusia kemungkinan duplikat! Anda mungkin dapat secara otomatis memutuskan bahwa> 7 adalah duplikat dan <6 berbeda dan hanya memiliki manusia memeriksa skor 6 atau 7. Saya tahu bahwa dengan identifikasi spam ada mesin-tidak-tahu-DAN-manusia- tidak tahu kategori mana pun; area abu-abu antara duplikat hampir dan karya asli di mana yang terbaik yang dapat Anda lakukan adalah membuat panggilan penilaian yang agak sewenang-wenang.
GlenPeterson
@rdlowrey - Algoritma Levenshtein adalah apa yang saya gunakan dalam proyek serupa yang saya lakukan di C #. Saya setuju, ini adalah tempat yang baik untuk memulai dan mungkin cukup.
jfrankcarr

Jawaban:

4

Ada banyak algoritma yang menangani kesamaan dokumen di NLP. Berikut makalah seminal yang menjelaskan berbagai algoritma. Wikipedia juga memiliki koleksi yang lebih besar. Saya mendukung ukuran Jaro Winkler dan telah menggunakannya untuk proyek sekolah pascasarjana dalam metode pengelompokan aglomeratif.

Candide
sumber
6

Lihatlah algborithm Rabin-Karp . Ini menggunakan hash bergulir agak seperti menggunakan rsync untuk meminimalkan byte yang dikirimkan selama sinkronisasi. Dengan menyesuaikan ukuran jendela yang Anda gunakan untuk hash, Anda dapat membuatnya lebih atau kurang sensitif. RK digunakan untuk, antara lain, deteksi plagiarisme, yang pada dasarnya mencari semacam dupes.

Peter Rowell
sumber
4
Masalah yang OP jelaskan kelihatannya persis seperti deteksi plagiarisme , dan saya menyarankan itu sebagai tempat pertama untuk mencari bantuan. (Pastikan untuk mengidentifikasi sumber Anda!)
Caleb
4

Langkah pertama yang dilakukan adalah mendeteksi kalimat (atau beberapa blok data masuk akal lainnya. Ambil blok tersebut dan hapus semua data mete, html spasi putih acak, pengembalian dll. Ambil MD5 hasil dan simpan dalam tabel. Anda bisa kemudian cocokkan dengan blok ini untuk mencoba menemukan kecocokan.

Jika ini tidak berhasil, Anda dapat mencoba n-gram. Di sini Anda membutuhkan satu entri dari setiap kata di halaman, tetapi harus dapat memberi Anda kecocokan yang cukup baik.

http://en.wikipedia.org/wiki/N-gram

gam3
sumber
langkah-langkah berbasis n-gram jauh lebih baik daripada hash md5 terutama untuk data semi-terstruktur seperti html.
Candide
1

Untuk matematika matematika yang tepat saya akan menyimpan hash dan kemudian membandingkannya.

Saya pikir sistem yang digunakan untuk ujian mengukur kelompok kata dan kemudian frekuensi kelompok dari setiap ukuran. Misalnya rantai 30 kata yang disalin akan mencetak 5 poin risiko dan 5 kejadian 10 rantai kata mencetak skor 5 poin. Maka Anda akan memiliki ambang batas 30 poin per 500 kata.

Benar-benar Anda membutuhkan algoritma semantik sehingga kata-kata seperti 'juga' dan 'dan' diuraikan sebagai sama.

Llama terbalik
sumber