🎴 🌦️ 👨‍🔧 Algoritma pencarian fuzzy TextRadar. Artefak (Bagian 2) 👸🏽 👨 🥗

Dalam publikasi sebelumnya, Algoritma Pencarian Fuzzy TextRadar. Pendekatan utama (Bagian 1) dianggap sebagai pendekatan utama. Ketika memecahkan masalah praktis, situasi diidentifikasi di mana penggunaan hanya metodologi dasar tidak memberikan kualitas pencarian yang diperlukan. Akibatnya, add-on (opsi algoritme) dibuat, yang akan dibahas.

Fragmen dari satu kata string pencarian berada dalam beberapa kata string data

Biarkan string pencarian menjadi ABCD dan string data menjadi ABCE DFG.

gambar

Penerapan algoritma dasar akan memberikan hasil sebagai berikut:

gambar

Ketika tabrakan tersebut terjadi, grup tambahan dihapus. Pilihan grup untuk dihapus adalah pertanyaan yang terpisah dan kompleks. Akibatnya, kelompok yang paling signifikan harus tetap ada. Dalam kasus contoh di atas, jawabannya sudah jelas - kelompok terkecil harus dihapus.

gambar

Fragmen awal kata string pencarian terletak di dalam kata string data

Perhatikan contoh menemukan string ABC dalam string XYZAB.

gambar

Algoritma dasar akan menghasilkan yang berikut:

gambar

Sebagai aturan, hasil seperti itu tidak memiliki nilai praktis dan harus dibuang.

Tidak cukup cakupan kata dalam baris data dengan fragmen yang ditemukan

Jika kami mencari di baris ABCDEF untuk kata ABXYZ,

gambar

kami mendapatkan:

gambar

Hasil ini juga tidak bernilai dan harus dibuang.

Overgroup

Diberikan string pencarian ABCXEF dan string data ABCEF ABCDEF.

gambar

Dari sudut pandang algoritma dasar, kedua kata dari string data adalah setara, tetapi yang pertama akan memiliki prioritas (jika, ceteris paribus, kata pertama yang ditemui dipilih) dan kemudian hasil pencarian akan menjadi sebagai berikut:

gambar

Jika kami memperkenalkan konsep grup super sebagai gabungan grup kata yang terletak di diagonal yang sama (atau bergeser, lihat publikasi sebelumnya, yang membahas dasar-dasar algoritma) dan meningkatkan prioritas grup yang termasuk dalam grup super melalui parameter ukuran ukuran grup super yang dihitung untuk setiap grup dan menganggap bahwa jika grup bukan bagian dari grup super, maka ukuran grup super untuk itu akan sama dengan ukuran grup itu sendiri - sebagai contoh, kita mendapatkan hasil sebagai berikut:

gambar

Kata-kata Panjang yang Berlebihan

Saat mencari frasa yang berisi kata panjang dan pendek, fragmen kata panjang yang ditemukan dapat "mengaburkan" fragmen kata pendek. Ini disebabkan oleh penggunaan fungsi kuadratik dalam menghitung koefisien relevansi.

gambar

Selain itu, dari sudut pandang kualitas pencarian, kata yang lebih panjang tidak selalu lebih bermakna.

Pertimbangkan sebuah contoh. Misalkan Anda perlu menemukan string ABCDEFG XYZ dalam teks yang terdiri dari dua halaman:

1. ABCDEFG ... QWE

gambar

2. ABCDEFO ... XYZ

gambar

Pembilang dari koefisien komposisi grup (penyebut tidak memiliki efek kualitatif pada hasil, lihat rumus di atas) untuk halaman pertama adalah 49, untuk yang kedua - 36 + 9 = 45. Artinya, jika kita menghilangkan pengaruh pada hasil faktor panjang, hasil pencarian pada halaman pertama akan lebih relevan, yang tidak memenuhi harapan - dalam beberapa kasus, hasil pencarian di halaman 2 akan lebih berharga.

Salah satu solusinya adalah dengan memperkenalkan batasan pada panjang grup maksimum . Dalam contoh kami, jika panjang grup maksimum dibatasi hingga 6, misalnya, kami mendapatkan 36 untuk halaman pertama dan 45 untuk yang kedua, yang akan memberikan hasil yang kami harapkan - relevansi halaman kedua akan lebih tinggi dari yang pertama.

Cara lain untuk menyelesaikan masalah ketidakkonsistenan arti kata-kata dari frasa pencarian dalam keseluruhan hasil dari panjangnya adalah dengan menghitung relevansi frasa pencarian sebagai rata-rata relevansi kata-kata yang termasuk di dalamnya , dihitung secara independen. Namun di sini muncul masalah yang berlawanan - kebutuhan untuk mengurangi signifikansi kata-kata pendek, yang dapat diselesaikan dengan cara yang sama - dengan menetapkan nilai ambang batas terhadap panjang kata yang terlibat dalam pembentukan relevansi umum, tetapi sudah pada nilai minimum.

Pengulangan fragmen yang diinginkan

Sebagai berikut dari pernyataan, tugasnya adalah untuk mencari string pencarian yang paling relevan untuk satu set fragmen, oleh karena itu fakta pengulangan fragmen yang diinginkan dalam teks tidak mempengaruhi hasil - fragmen yang cocok pertama akan digunakan sebagai hasil pencarian, sisanya akan dibuang selama pemrosesan. Pertimbangkan contoh menemukan string ABC dalam string ABCD ABCE ABCF ABCG.

gambar

Penerapan algoritma dasar akan memberikan hasil sebagai berikut:

gambar

Dari sudut pandang pencarian untuk halaman yang paling relevan, ini benar, tetapi ketika membentuk presentasi terperinci dari hasil pencarian, perlu untuk menemukan dan memilih semua fragmen yang sesuai. Untuk melakukan ini, Anda dapat menggunakan beberapa pengulangan dari prosedur pencarian pada halaman yang ditampilkan dengan shutdown berurutan dari fragmen yang ditemukan dalam iterasi sebelumnya. Dalam contoh kita, ini akan memungkinkan kita untuk menemukan semua kemunculan string yang diinginkan.

gambar

Kecepatan pemrosesan data

Pemrosesan data on-the-fly memiliki persyaratan kecepatan tertentu - pencarian tidak boleh terlalu lama.

Membatasi ukuran minimum grup yang diproses, menonaktifkan opsi pencarian

Untuk meningkatkan kecepatan pencarian, Anda dapat membatasi panjang minimum grup yang diproses.

Dalam praktiknya, pendekatan berikut diterapkan - pertama pass "kasar" pertama dibuat dengan batasan pada ukuran grup minimum dan menonaktifkan beberapa opsi dari seluruh array data pencarian dan mengidentifikasi bagian data pertama (ukuran bagian data optimal ditentukan dari konteks masalah yang dipecahkan), dan kemudian yang kedua, lebih teliti hanya melewati halaman bagian ini, sudah tanpa batasan pada ukuran grup dan dengan memasukkan semua opsi yang diperlukan.

Pemrosesan data paralel

Cara lain untuk meningkatkan kecepatan pencarian adalah pemrosesan data paralel. Akibatnya, dengan database pencarian yang besar, total waktu pemrosesan yang dapat diterima dapat dicapai dengan meningkatkan jumlah proses paralel, yang secara alami akan membutuhkan peningkatan kapasitas peralatan.

hasil

Penerapan pendekatan yang dijelaskan memungkinkan kami untuk secara signifikan meningkatkan kualitas pencarian, untuk mengurangi ketergantungan hasilnya pada berbagai jenis kesalahan ketik - karakter berlebihan, karakter yang hilang, permutasi, dll., Dan, yang lebih penting, di mana pun kesalahan tersebut terletak - di bilah pencarian itu sendiri atau dalam teks, yang sedang dicari.

Hasil penerapan pendekatan yang dijelaskan dapat dilihat pada demo yang digunakan di situs web textradar.ru . Pada contoh pencarian dalam teks novel L.N. "War and Peace" Tolstoy dapat membandingkan hasil pencarian menggunakan versi dasar dan lanjutan dari algoritma.

gambar

Unduh atau tonton proyek demo dengan fungsionalitas tingkat lanjut (C # ASP.NET MVC) di sini .

Algoritma pencarian fuzzy TextRadar. Artefak (Bagian 2)