Musuh misterius: peminjaman kabur

Peminjaman Ilegal adalah hydra berkepala banyak, musuh yang terus-menerus mengubah wajahnya. Investigator pribadi terbaik kami siap untuk berpegang teguh pada kejahatan apa pun yang dilakukan oleh musuh ini. Namun, musuh tidak tidur, ia licik dan berbahaya: jelas menggantikan dalam satu hal, ia sangat terampil menyapu jejak orang lain. Terkadang ia berhasil menangkap basah dengan bantuan karyawan kami yang paling gesit - Suffix Massiv . Terkadang musuh ragu-ragu, dan Pencarian Paraphrase yang teliti tapi santai berhasil menghitung lokasinya. Tapi kejahatan itu berbahaya, dan kita terus-menerus membutuhkan kekuatan baru untuk melawannya .

Hari ini kita akan berbicara tentang detektif tujuan khusus baru kita bernama Fuzzy Search , serta pertemuan pertamanya dengan pinjaman fuzzy.

Dengan Anda agen antiplagiarisme detektif, bersiap-siap untuk Kasus Lawan Misterius

Adegan

Saat memeriksa area (dokumen), Anti-Plagiarisme memeriksa apakah ada panggilan tentang kemungkinan kejahatan di area tersebut. Saksi mata yang akan memberi sinyal kepada kami tentang kejahatan tersebut adalah Indeks Shingles .

"Sinanaga adalah sepotong teks yang berukuran beberapa kata." Setiap bagian seperti itu di-hash, dan dokumen yang memiliki sirap dengan hash yang sama seperti pada dokumen yang diperiksa dicari dalam indeks.

Seorang saksi mata, melihat kebetulan dalam hash dari dua sirap, memanggil kami dengan pesan tentang kejahatan. Sayangnya, sinanaga indeks tidak dapat dihukum karena panggilan palsu, itu kebal terhadap sanksi, itulah sebabnya ada banyak panggilan. Agensi menentukan dokumen dengan akumulasi panggilan terbesar - tempat terjadinya potensi kejahatan.

Petunjuk pertama

Sekarang kau seorang detektif, nak.
Mulai sekarang Anda dilarang untuk percaya pada kebetulan.

Detective Fuzzy Search tiba di tempat kejadian. Penjahat yang cukup besar tidak luput dari perhatian, karena semakin besar skala kejahatan, semakin besar kemungkinan untuk meninggalkan petunjuk. Untuk Pencarian Fuzzy, lead tersebut adalah kecocokan pendek dengan panjang yang tetap. Tampaknya detektif kita kehilangan sebagian besar jejak penjahat yang terampil, tetapi hanya 5% penyerang tidak meninggalkan petunjuk seperti itu. Penting untuk tidak kehilangan penjahat, sehingga detektif dengan cepat memindai area tersebut menggunakan teknik khusus untuk mendeteksi pertandingan.

Buku harian detektif tentang metode kerja. Tahap pertama

Kami akan menggunakan dua fitur tugas:

1. Kami tertarik pada duplikat yang jelas dengan panjang tetap.
2. Dalam dokumen yang bagus, sirap yang sama tidak terlalu sering diduplikasi.

Kondisi kedua diperlukan untuk membatasi jumlah duplikat yang ditemukan. Memang, satu yang muncul 1000 kali dalam dokumen dan dalam sumber akan memberikan 1.000.000 pasangan yang cocok. Sinanaga yang sering diulang seperti itu hanya dapat dilihat dalam dokumen yang tidak bersih dengan upaya perayapan.

Dokumen yang dibersihkan dari perayapan disajikan sebagai urutan kata-kata. Kami membawa kata-kata ke bentuk kata normal, lalu memotongnya. Kami mendapatkan urutan bilangan bulat (pada gif - urutan huruf). Semua sirap dari urutan ini adalah hash dan dimasukkan ke dalam tabel hash dengan nilai posisi awal substring. Kemudian, untuk setiap sirap dalam dokumen kandidat, kecocokan ditemukan di tabel hash. Ini membuat duplikat yang jelas dari panjang tetap. Pengujian menunjukkan akselerasi tiga kali lipat ketika menggunakan metode baru dibandingkan dengan array suffix.

Kami menghitung penjahat

- Apakah ada poin lain yang Anda sarankan agar saya perhatikan?
"Perilaku aneh anjing itu pada malam kejahatan."
- Anjing? Tapi dia tidak berperilaku dengan cara apa pun!
"Itu aneh," kata Holmes.

_{© Arthur Conan-Doyle, "Silver" (dari seri "Notes on Sherlock Holmes")}

Jadi, Fuzzy Search menemukan beberapa petunjuk yang digunakan untuk mengidentifikasi penjahat. Pahlawan kita menggunakan kemampuan deduktifnya sepenuhnya, untuk sedikit demi sedikit, secara bertahap mengembalikan citra penjahat sesuai dengan petunjuk yang ditemukan. Detektif itu secara bertahap memperluas gambaran tentang apa yang terjadi, menambahinya dengan perincian baru, menemukan semakin banyak bukti sampai foto ini akhirnya menjadi lengkap. Detektif kita kadang-kadang dibawa masuk, dan dia harus diturunkan dari surga ke bumi dan diyakinkan bahwa kita membutuhkan identitas penjahat, dan bukan biografi sepupunya. Fuzzy Search menggerutu, tetapi dengan rendah hati mempersempit gambar ke skala yang diinginkan.

Buku harian detektif tentang metode kerja. Tahap kedua

_{Sumber Gambar: pixabay.com}

Tahap kedua mendistribusikan duplikat kiri dan kanan di seluruh dokumen. Distribusi berasal dari "pusat" - ditemukan duplikat yang jelas. Untuk membandingkan sufiks, kami menggunakan jarak Levenshtein - jumlah minimum penghapusan / penggantian / penyisipan kata-kata yang diperlukan untuk membawa satu baris ke baris lainnya. Jarak dapat dihitung secara dinamis untuk sufiks duplikat menggunakan algoritma Wagner-Fisher , berdasarkan pada penentuan rekursif jarak Levenshtein. Namun, algoritma ini kuadratik dalam kompleksitas dan tidak memungkinkan mengontrol proporsi kesalahan. Masalah lain adalah definisi yang tepat dari batas duplikat. Untuk mengatasi masalah ini, kami menggunakan beberapa prosedur langsung yang sederhana, namun tetap efektif.

Pada langkah ini, pertama-tama diusulkan untuk secara berurutan mengisi Matriks Jarak Levenshtein untuk sufiks duplikat fuzzy (kemudian, demikian pula, untuk awalan). Karena kami memeriksa sufiks untuk “kesamaan”, kami hanya tertarik pada nilai di dekat diagonal dari matriks ini (jarak Levenshtein lebih besar dari atau sama dengan perbedaan panjang garis). Ini memungkinkan untuk kompleksitas linier. Setelah menetapkan jarak Levenshtein maksimum yang diijinkan, kami akan mengisi tabel sampai kami memenuhi kolom dengan nilai yang lebih besar dari yang diijinkan. Kolom seperti itu menunjukkan bahwa duplikat fuzzy kami baru-baru ini berakhir dan kata-katanya hampir sepenuhnya bertepatan. Setelah menyimpan yang optimal sebelumnya untuk setiap sel yang diisi, kami turun dari sel dengan penalti minimum di kolom kritis sampai kami menemukan beberapa kecocokan, setelah itu kesalahan mulai meningkat tajam. Ini akan menjadi batas duplikat fuzzy yang ditemukan.

Selain itu, agar kesalahan tidak menumpuk, prosedur diperkenalkan yang mengatur ulang jumlah kesalahan, memulai propagasi lagi jika kita menemukan "pulau" dari kebetulan yang berurutan.

Geng penjahat

- Besok kita berencana untuk bersama teman sekelas!
- Dalam satu teman sekelas besar?
- Apa?

_{© Bashorg}

Pencarian fuzzy tetap menjadi tugas sederhana: untuk menyatukan para penjahat yang ditangkap di tempat yang sama menjadi geng, untuk membenarkan tersangka yang tidak bersalah dan untuk mengumpulkan hasilnya.

_{Sumber Gambar: pixabay.com}

Merekatkan duplikat segera menyelesaikan 3 masalah. Pertama, tahap kedua "distribusi duplikat" menyerap modifikasi kata dan frasa, tetapi tidak seluruh kalimat. Jika Anda meningkatkan "kemampuan menyebar" dari algoritma, maka itu akan mulai menyebar pada kebetulan yang ditemukan pada jarak yang terlalu jauh, dan batas-batas duplikat akan ditentukan lebih buruk. Jadi, kami kehilangan Presisi yang begitu penting bagi kami, yang dimiliki pencarian yang jelas.

Kedua, tahap kedua tidak mengenali permutasi dua duplikat. Saya ingin permutasi dari dua kalimat di beberapa tempat untuk membentuk frase yang dekat dengan aslinya, tetapi untuk garis karakter unik, permutasi dari awalan dan akhiran di beberapa tempat mengarah ke garis yang sejauh mungkin dari aslinya (dalam metrik Levenshtein). Ternyata tahap kedua, saat menyusun ulang kalimat, menemukan dua duplikat yang terletak bersebelahan yang ingin Anda gabungkan menjadi satu.

Dan alasan ketiga adalah Granularity, atau Granularity. Granularity adalah metrik yang menentukan jumlah rata-rata duplikat yang ditemukan dalam satu pinjaman nyata yang kami temukan. Dengan kata lain, granularity menunjukkan seberapa baik kita menemukan seluruh pinjaman daripada beberapa bagian yang menutupinya. Definisi formal granularity, serta definisi akurasi dan kelengkapan mikro rata-rata, dapat ditemukan dalam artikel "Kerangka evaluasi untuk deteksi plagiarisme" .

Gifka menunjukkan bahwa terkadang dua duplikat dapat dilem hanya setelah salah satu dari mereka menempel pada duplikat ketiga. Dengan demikian, hanya satu lintasan dari kiri ke kanan pada dokumen tidak berfungsi untuk menyelesaikan perekatan.

Pelatihan Pemula

Detektif itu perlu beradaptasi dengan ciri-ciri kota kami, beradaptasi dengan medan, berjalan-jalan di sepanjang jalan-jalan yang tidak mencolok dan mengenal lebih baik penghuninya. Untuk ini, seorang pemula mengambil kursus pelatihan khusus di mana ia mempelajari situasi serupa di tempat pelatihan. Detektif dalam praktik mempelajari petunjuk, deduksi dan pembangunan ikatan sosial untuk menangkap penjahat yang paling efektif.

Model parametrik perlu dioptimalkan. Untuk menentukan parameter model optimal, sampel PlagEvalRus digunakan .

Sampel dibagi menjadi 4 koleksi:

• Generated_Copypast (4250 pasang) - kata kunci yang dihasilkan pinjaman
• Generated_Paraphrased (4250 pasangan) - pinjaman yang lemah dan modifikasi sedang yang dihasilkan oleh mesin menggunakan kebisingan dari bagian asli (penggantian / penghapusan / sisipan sewenang-wenang)
• Manually_Paraphrased (713 pasangan) Teks tulisan tangan dengan berbagai jenis pinjaman, sebagian besar pinjaman lemah dan modifikasi menengah (digantikan oleh tidak lebih dari 30% dari kata-kata dalam duplikat)
• Manually_Paraphrased 2 (198 pairs) Teks tulisan tangan dengan pinjaman sedang dan sangat dimodifikasi (lebih dari 30% kata)

Pencarian untuk parameter model optimal dilakukan dengan menggunakan metode multi-start descent. Dimaksimalkan $$$F_ \ beta$ukur dengan $$$\ beta ^ 2 = \ frac {1} {4}$(penekanan pada akurasi). Berikut adalah parameter optimal yang paling signifikan.

Sejarah Kasus

Masa percobaan Pencarian Fuzzy kami telah berakhir. Mari kita bandingkan produktivitasnya dengan detektif lain, Suffix Array. Kursus pelatihan Fuzzy Search berlangsung di program Manually_Paraphrased.

Di lapangan, pendatang baru menunjukkan keunggulan signifikan dalam proporsi kasus yang diselesaikan. Kecepatan karyanya juga tidak bisa tidak bersukacita. Agen kami tidak memiliki karyawan yang begitu berharga.

Membandingkan kualitas model dengan susunan sufiks, kami melihat peningkatan granularitas yang signifikan, serta deteksi yang lebih baik untuk pinjaman yang sedang dan sangat dimodifikasi.

Menguji dokumen hingga 10 ⁷ kata dalam ukuran, kami memverifikasi linearitas kedua algoritma. Pada prosesor i5-4460, program memproses sepasang "sumber dokumen" yang panjangnya sejuta kata dalam waktu kurang dari satu detik.

Setelah menghasilkan teks dengan jumlah pinjaman yang besar, kami yakin bahwa pencarian fuzzy (garis biru) tidak lebih lambat dari susunan akhiran (garis merah). Sebaliknya, array suffix menderita pada dokumen besar dari terlalu banyak duplikat. Kami membandingkan kinerja dengan panjang duplikat minimum 5 kata. Tetapi untuk cakupan pinjaman yang memadai, kami menggunakan pencarian yang jelas dengan panjang duplikat minimum 3 kata, yang pada dokumen raksasa menyebabkan penurunan produktivitas yang signifikan (garis oranye). Perlu dicatat bahwa dokumen biasa mengandung lebih sedikit pinjaman, dan dalam praktiknya efek ini jauh lebih jelas. Tetapi percobaan semacam itu memungkinkan kita untuk memahami perluasan penerapan model dengan pencarian fuzzy baru.

Contoh:

Dapat dilihat bahwa algoritme, meskipun kompleksitas komputasionalnya kecil, mengatasi deteksi penggantian / penghapusan / penyisipan, dan langkah ketiga memungkinkan Anda untuk mendeteksi pinjaman dengan permutasi kalimat dan bagian-bagiannya.

Epilog

Fuzzy Search bekerja dalam tim dengan alat kami yang lain: Pencarian Cepat untuk Dokumen Kandidat, Ekstraksi Pemformatan Dokumen, Penangkapan Skala Besar Upaya Bypass. Perintah ini memungkinkan Anda untuk dengan cepat menemukan potensi penjiplakan. Fuzzy Search telah berakar di tim ini dan melakukan fungsi pencariannya secara lebih kualitatif, dan yang lebih penting, lebih cepat daripada Suffix Array. Agensi kami akan mengatasi tugasnya dengan lebih baik, dan penulis yang tidak bermoral akan menghadapi masalah baru saat menggunakan teks yang tidak asli .

Buat dengan pikiran Anda sendiri!