Apa sajakah cara efisien untuk menemukan perbedaan antara dua corpus besar teks yang memiliki konten serupa, tetapi berbeda urutan?

Saya memiliki dua file besar yang berisi paragraf teks bahasa Inggris:

1. Teks pertama panjangnya sekitar 200 halaman dan memiliki sekitar 10 paragraf per halaman (setiap paragraf panjangnya 5 kalimat).
2. Teks kedua berisi paragraf dan teks yang hampir sama persis dengan paragraf pertama. Panjangnya juga 200 halaman dengan 10 paragraf per halaman. Namun, paragraf diacak dan dalam urutan yang berbeda bila dibandingkan dengan teks pertama. Juga, sebagian besar paragraf memiliki perubahan kecil dalam susunan kata dibandingkan dengan paragraf serupa. Misalnya, paragraf dalam teks pertama mungkin memiliki kalimat seperti Like Jimmy, I wanted to go to the palacesementara kalimat yang sesuai dalam paragraf teks kedua akan dibaca Like Jimmy, I really wanted to go to the castle.

Saya ingin dapat menangkap perubahan di sini seperti penambahan reallydan penghapusan palacedengan penggantian castle. Jika paragraf rata-rata disejajarkan, maka ini akan sangat sepele karena ada banyak cara untuk membedakan teks. Namun, karena paragraf tidak selaras, itu tidak terjadi.

Jika file-file itu kecil (beberapa paragraf), Levenshtein Distance mungkin akan berfungsi dengan baik, tetapi karena file-file itu besar, itu tidak efisien untuk membandingkan setiap paragraf teks 1 dengan setiap paragraf teks 2 untuk mengetahui paragraf mana yang cocok.

Apa yang akan menjadi pendekatan lain untuk mengatasi masalah ini secara efisien?

Membandingkan 2000 paragraf dengan 2000 paragraf hanya empat juta perbandingan.

Kunci dari masalahnya adalah bukan menggunakan fungsi yang menghitung jarak Levenshtein tetapi menggunakan fungsi yang menghitung jarak Levenshtein jika jaraknya kurang dari ambang tertentu , dan gagal (atau, lebih tepatnya, mengembalikan + ∞) jika jaraknya adalah lebih besar dari ambang batas.

Ini karena Anda hanya tertarik pada paragraf yang hampir mirip. Anda sama sekali tidak tertarik pada jarak yang tepat antara paragraf yang cukup berbeda untuk tidak berhubungan. Jadi, begitu jarak sudah cukup tinggi sehingga tidak menarik, fungsi dapat keluar sekaligus; dan ini sebagian besar akan terjadi sangat awal memang selama pelaksanaan fungsi.

Semakin tinggi ambang, semakin lama waktu berjalan tetapi semakin kecil proporsi negatif palsu.

Jika Anda mengetahui lebih banyak tentang dokumen (seperti setiap paragraf cocok dengan paling banyak satu paragraf di dokumen lain) maka Anda dapat membuat satu pass dengan ambang rendah, mengecualikan paragraf yang cocok dari pertimbangan lebih lanjut, membuat satu pass untuk Anda yang sekarang dikurangi corpus dengan batas yang lebih tinggi, termasuk orang-orang paragraf berkurang, dan sebagainya.

Detail implementasi: Mungkin Anda akan menghitung jarak Levenshtein pada kata-kata dan bukan pada karakter. Jika demikian, Anda harus terlebih dahulu menetapkan angka untuk setiap kata - misalnya, dengan menyortir seluruh korpus, memanggil kata pertama '1', kata kedua '2', dan seterusnya. Dengan begitu perbandingan paragraf Anda akan dilakukan dengan membandingkan angka daripada kata-kata, yang lebih cepat.

Mungkin saja menggunakan pendekatan majemuk. Mungkin seseorang dapat membangun ini ...

Hash isi paragraf sedemikian rupa sehingga paragraf dengan hanya sedikit perbedaan memiliki hash yang sama, kemudian memerintahkan hash untuk menentukan paragraf mana yang akan dibandingkan melalui metode yang lebih tepat (beda atau serupa).

Misalnya, sebagai algoritma hash yang belum sempurna, bagaimana jika Anda menambahkan nilai-nilai ascii dari karakter dan kemudian memodulasi jumlah dengan jumlah besar seperti 2.000.000.000? Ini akan menyebabkan 2 paragraf dengan hanya beberapa kata yang ditambahkan atau dikurangi memiliki nilai hash yang cenderung lebih dekat daripada paragraf dengan kata-kata yang sangat berbeda, dan dengan demikian, mereka akan lebih dekat bersama-sama dalam daftar daripada paragraf yang sangat berbeda (Anda mungkin mengatakan hash terdekat dalam kasus ini diperlukan tetapi tidak cukup untuk paragraf yang sama). Jelas Anda harus memperhitungkan pembungkusan yang disebabkan oleh modulo dan menganggap paragraf dengan nilai hash 1.999.999.999 karena hanya berjarak 1 dari satu dengan nilai 0, dll.

Akibatnya, dapat mengurangi jumlah perbandingan antara paragraf yang perlu Anda lakukan dengan jumlah yang substansial (Anda tidak perlu membandingkan setiap paragraf dalam satu teks dengan setiap paragraf dalam teks lainnya) - Anda dapat membandingkan paragraf dengan paragraf dalam teks 2 dalam urutan seberapa dekat hash mereka (lakukan yang bernilai terdekat hash pertama) dan gunakan algoritma yang lebih mahal di sini untuk menentukan apakah mereka "cukup mirip" untuk dianggap sama.