Kita semua membuat kesalahan: dalam hal ini kita berbicara tentang permintaan pencarian. Jumlah situs untuk penjualan barang dan jasa semakin meningkat seiring dengan kebutuhan pengguna, tetapi mereka tidak selalu dapat menemukan apa yang mereka cari - hanya karena mereka salah memasukkan nama produk yang diperlukan. Solusi untuk masalah ini dicapai dengan menerapkan pencarian fuzzy, yaitu menggunakan algoritma untuk menemukan nilai terdekat, dengan mempertimbangkan kemungkinan kesalahan atau kesalahan ketik pengguna. Cakupan pencarian semacam itu cukup luas - kami berhasil mengerjakan pencarian untuk toko online besar di segmen ritel makanan.
Status Pencarian Awal
Toko online dikembangkan pada platform 1C-Bitrix: Manajemen Situs. Untuk mengimplementasikan pencarian, kami menggunakan modul pencarian bitrix standar dan mesin teks lengkap sphinxsearch. Dalam sphinxsearch, tipe indeks Real Time (RT) digunakan, yang tidak memerlukan sumber data statis, tetapi dapat diisi kapan saja secara real time. Ini memungkinkan Anda memperbarui indeks pencarian secara fleksibel tanpa mengindeks ulang sepenuhnya. Karena indeks RT hanya menggunakan SphinxQL sebagai protokol kueri, integrasi dilakukan melalui itu. SphinxQL adalah protokol kueri seperti mysql yang mengimplementasikan kemampuan untuk terhubung melalui klien mysql standar, sambil memberikan sintaksis sql dengan beberapa batasan dan kekhasannya sendiri. Modul pencarian menggunakan select / insert / replace / delete queries.
Dalam sistem bitrix, proses pengindeksan data barang, kategori dan merek dilakukan. Informasi tentang entitas ini dipindahkan ke sphinx, yang pada gilirannya memperbarui indeks RT. Ketika data diperbarui di toko online, sebuah peristiwa dipicu yang memperbarui data di Sphinx. Konsistensi data dilakukan melalui pengenal entitas di toko online.
Ketika pengguna mencari di toko online, sistem membuat permintaan dengan frasa pencarian di Sphinx dan memperoleh pengidentifikasi entitas, juga memilih dari informasi database pada mereka dan membentuk halaman dengan hasil hasil pencarian.
Pada saat solusi untuk masalah pencarian fuzzy dimulai, skema umum arsitektur pencarian pada proyek adalah sebagai berikut:
Pemilihan teknologi
Tugas kami adalah menebak permintaan pengguna, yang mungkin mengandung kesalahan ketik. Untuk melakukan ini, kita perlu menganalisis setiap kata dalam permintaan dan memutuskan apakah pengguna menulisnya dengan benar atau tidak. Jika terjadi kesalahan, opsi yang paling cocok harus dipilih. Menentukan ejaan kata yang benar tidak mungkin tanpa database kata dan bentuk kata dari bahasa di mana kita ingin menebaknya. Secara sederhana, basis data seperti itu bisa disebut kamus - dialah yang kami butuhkan.
Untuk memilih opsi substitusi kata yang dimasukkan dengan kesalahan, formula penghitungan jarak Damerau - Levenshtein yang populer dipilih. Formula ini adalah algoritma untuk membandingkan dua kata. Hasil perbandingan adalah jumlah operasi untuk mengubah satu kata menjadi kata lain. Awalnya, jarak Levenshtein melibatkan penggunaan 3 operasi:
- penyisipan
- penghapusan
- penggantian
Jarak Damerau-Levenshtein adalah versi diperpanjang dari jarak Levenshtein dan menambahkan operasi lain: transposisi, yaitu permutasi dari dua karakter yang berdekatan.
Dengan demikian, jumlah operasi yang diterima menjadi jumlah kesalahan yang dibuat oleh pengguna saat menulis kata. Kami memilih batasan dua kesalahan, karena jumlah yang lebih besar tidak masuk akal: dalam hal ini kami mendapatkan terlalu banyak opsi untuk penggantian, yang meningkatkan kemungkinan kehilangan.
Untuk pencarian yang lebih relevan untuk varian kata yang mirip dalam suara, fungsi metafon digunakan - fungsi ini mengubah kata menjadi bentuk fonetisnya. Sayangnya, metafon hanya berfungsi dengan huruf-huruf alfabet Inggris, jadi sebelum menghitung bentuk fonetisnya, kami mentransliterasikan kata tersebut. Nilai bentuk fonetis disimpan dalam kamus, dan juga dihitung dalam permintaan pengguna. Nilai yang dihasilkan dibandingkan dengan fungsi jarak Damerau-Levenshtein.
Kamus disimpan dalam database MySQL. Agar tidak memuat kamus ke dalam memori aplikasi, diputuskan untuk menghitung jarak Damerau-Levenshtein di sisi dasar.
Fungsi yang ditentukan pengguna untuk menghitung jarak Damerau-Levenshtein , yang ditulis berdasarkan
fungsi C yang ditulis oleh Linus Torvalds , sepenuhnya memenuhi persyaratan kami. Dibuat oleh Diego Torres.
Setelah menghitung jarak Damerau-Levenshtein, perlu untuk mengurutkan hasil berdasarkan tingkat kesamaan untuk memilih yang paling cocok. Untuk melakukan ini, kami menggunakan algoritma Oliver: menghitung kesamaan dua baris. Dalam php, algoritma ini diwakili oleh fungsi similar_text. Dua parameter pertama dari fungsi menerima garis input yang perlu dibandingkan. Urutan perbandingan string penting, karena fungsi memberikan nilai yang berbeda tergantung pada urutan di mana garis dilewatkan ke fungsi. Parameter ketiga harus lulus variabel di mana hasil perbandingan ditempatkan. Ini akan menjadi angka dari 0 hingga 100, yang berarti persentase kesamaan antara dua baris. Setelah perhitungan, hasilnya diurutkan dalam urutan kesamaan, kemudian opsi dengan nilai terbaik dipilih.
Karena perhitungan jarak Damerau-Levenshtein dilakukan sesuai dengan transkripsi kata, kata-kata dengan makna yang tidak sepenuhnya relevan masuk ke dalam hasil. Dalam hal ini, kami membatasi pemilihan opsi dengan persentase kecocokan lebih dari 70%.
Selama proses pengembangan, kami perhatikan bahwa algoritma kami dapat menebak kata-kata dalam tata letak yang berbeda. Karena itu, kami perlu memperluas kamus dengan menambahkan arti kata pada tata letak terbalik. Persyaratan pencarian hanya menampilkan dua tata letak: Rusia dan Inggris. Kami menduplikasi setiap kata dari permintaan pencarian pengguna pada tata letak terbalik dan menambahkan pemrosesan untuk menghitung jarak Damerau-Levenshtein. Pilihan untuk tata letak langsung dan mundur diproses secara independen satu sama lain, opsi dengan persentase kemiripan tertinggi dipilih. Hanya untuk opsi tata letak terbalik nilai di tata letak langsung akan menjadi nilai untuk permintaan pencarian yang diperbaiki.
Algoritma pencarian fuzzy
Dengan demikian, algoritma tindakan 6 langkah utama dibentuk. Selama pengujian, kami menemukan bahwa tidak semua kata dalam permintaan pengguna perlu diproses dalam bentuk aslinya atau diproses secara umum. Untuk mengatasi kasus tersebut, langkah tambahan diperkenalkan, yang kami sebut konverter atau filter. Alhasil, algoritma terakhir terdiri dari 7 langkah:
- Pecahkan permintaan menjadi kata-kata yang terpisah;
- Lewati setiap kata melalui konverter (lebih lanjut tentang itu);
- Untuk setiap kata, buat formulirnya pada tata letak yang berbeda;
- Buat transkripsi;
- Buat kueri pencarian di tabel kamus, bandingkan setiap entri melalui jarak Damerau-Levenshtein;
- Hanya menyisakan catatan dengan jarak kurang dari atau sama dengan dua;
- Melalui algoritma Oliver, hanya menyisakan kata-kata dengan persentase kemiripan lebih dari 70%
Secara skematis, algoritma ini adalah sebagai berikut:
Konversi kata dan fungsi penyaringan
Ketika kami mulai menguji prototipe pertama tanpa konverter, menjadi jelas bahwa tidak perlu mencoba menebak semua kata dalam permintaan pengguna. Konverter telah dibuat untuk pembatasan ini. Ini memungkinkan Anda untuk mengubah kata ke bentuk yang kita butuhkan dan menyaring kata-kata yang, menurut pendapat kami, tidak perlu ditebak.
Awalnya, diputuskan bahwa panjang kata minimum yang harus dilalui algoritma harus setidaknya dua karakter. Lagipula, jika pengguna memasukkan dalih atau gabungan satu karakter, maka kemungkinan menebaknya praktis minimal. Langkah kedua adalah untuk membagi permintaan menjadi kata-kata. Pertama-tama, kami memilih serangkaian karakter yang dapat berisi kata-kata: huruf, angka, titik, dan tanda hubung (tanda hubung). Spasi dan karakter lain adalah pembatas kata.
Sangat sering, pengguna memasukkan angka untuk menunjukkan volume atau kuantitas. Dalam hal ini, akan salah untuk memperbaiki permintaan semacam itu. Misalnya, pengguna memasukkan kueri "air 1,1 liter". Jika kami memperbaiki permintaannya sebesar 1,5 atau 1,0, itu akan salah. Dalam kasus seperti itu, kami memutuskan untuk melewatkan kata dengan angka. Mereka, melewati algoritma kami, ditransfer ke pencarian teks lengkap Sphinx.
Konversi lain dikaitkan dengan titik-titik dalam nama merek - misalnya: Dr. Pepper atau Mr.Proper. Dalam kasus di mana ada simbol titik di tengah kata, maka kita memecahnya menjadi dua, menambahkan spasi. Kasus kedua dengan titik di tengah kata - di sini kita ingat merek singkatan. Misalnya, merek ROCS - dalam hal ini kami memotong titik-titik dan mendapatkan satu kata. Konversi ini berfungsi jika hanya ada satu huruf di antara titik-titik.
Dalam kasus di mana tanda hubung (tanda hubung) hadir dalam kata, Anda harus memecah kata menjadi beberapa dan mencoba menebaknya secara individual, dan kemudian rekatkan opsi terbaik.
Akibatnya, konverter dikembangkan untuk pengenalan permintaan yang paling akurat - sebagian besar pekerjaan pengaturan semua fungsi dilakukan oleh pengembangan khusus ini. Berkat dia, penyesuaian dan penyetelan seluruh pencarian fuzzy dilakukan. Secara singkat ulangi aturan dengan mana penyaringan dan konversi kata dilakukan:
- kata harus lebih dari 2 karakter
- kata tersebut harus hanya berisi huruf, karakter titik, dan tanda hubung (tanda hubung)
- jika titik ada di tengah kata, spasi ditambahkan setelahnya
- jika itu adalah singkatan, titik-titik dipotong dan huruf-huruf dilem bersama
- jangan mencoba menebak kata jika ada angka di dalamnya
- jika kata tersebut berisi tanda hubung (tanda hubung), kemudian pisahkan menjadi beberapa, cari secara terpisah dan tempel di bagian akhir
Kompilasi kamus
Seperti yang disebutkan sebelumnya, untuk memperbaiki permintaan pengguna, perlu untuk menentukan kata mana yang dieja salah dan mana yang tidak. Untuk ini, kamus dibuat dalam sistem di mana kata-kata dengan ejaan yang benar harus dimuat.
Pada tahap pertama, muncul pertanyaan untuk mengisi kamus - sebagai hasilnya, kami memutuskan untuk menggunakan konten katalog untuk menyusunnya. Karena informasi barang diimpor dari waktu ke waktu dari sistem eksternal dan diindeks untuk sistem pencarian teks lengkap Sphinx, diputuskan untuk menambahkan fungsionalitas kompilasi kamus pada tahap ini. Kami mengikuti logika berikut: jika kata itu tidak ada dalam konten barang, lalu mengapa mencoba menebaknya?
Informasi produk digabungkan menjadi teks umum dan dilakukan melalui konverter. Mode operasi konverter sedikit dimodifikasi: ketika memecah kata melalui tanda hubung (tanda hubung), masing-masing bagian disimpan dalam kamus secara terpisah, ketika mengganti titik dalam kamus, data asli dan yang diubah ditambahkan. Dan karena ketika membandingkan kata-kata untuk menghitung jarak Damerau-Levenshtein, transkripsi kata digunakan, selain kamus, transkripsi ditambahkan.
Ada banyak kesalahan ketik dalam konten produk, untuk tujuan ini bendera diletakkan di kamus, ketika dipasang, kata tersebut tidak lagi digunakan dalam pencarian. Konten dari 35 ribu produk diperbolehkan membuat kamus berisi 100 ribu kata unik, yang pada akhirnya tidak cukup untuk beberapa permintaan pengguna. Dalam hal ini, perlu untuk menyediakan fungsi pemuatan untuk pengayaannya. Perintah konsol dibuat untuk memuat kamus. Format file dengan data kamus harus sesuai dengan csv. Setiap entri hanya berisi satu bidang dengan bidang kamus itu sendiri. Untuk membedakan data yang diunduh dari data yang dihasilkan berdasarkan konten barang, bendera khusus ditambahkan.
Hasilnya, tabel kamus memiliki skema berikut:
| Nama bidang | Jenis bidang |
|---|
| Kata | tali |
| Transkripsi | tali |
| Ditambahkan secara manual | bool |
| Jangan gunakan | bool |
Sebelum pengembangan fungsi pencarian fuzzy, ada bidang dalam produk yang berisi serangkaian kata dengan kesalahan ketik. Pada generasi pertama pembuatan kamus, mereka memasuki isinya. Akibatnya, kamus dengan kesalahan ketik diperoleh, yang isinya tidak cocok untuk berfungsi dengan benar. Oleh karena itu, perintah konsol lain ditambahkan yang memiliki fungsi pembuatan kamus terbalik. Menggunakan konten dari bidang barang tertentu, tim mencari kata-kata dalam kamus dan membersihkannya dari kamus. Setelah dibersihkan, bidang tersebut dikeluarkan dari pengindeksan.
Integrasi Bitrix
Untuk menerapkan fungsi minimum yang disyaratkan, tiga kelas telah dibuat:
- DictionaryTable - sistem BitM ORM untuk bekerja dengan kamus
- Kamus - kelas pembuatan kamus
- Cari - cari kelas implementasi
Untuk integrasi ke dalam Bitrix, diperlukan untuk membuat perubahan pada 2 komponen:
- bitrix: search.page
- bitrix.search.title
Sebelum menjalankan permintaan, metode pemrosesan dipanggil untuk mendeteksi kesalahan dan memilih opsi yang sesuai:
Untuk mengkompilasi kamus, sebuah peristiwa direkam untuk mengindeks oleh modul pencarian elemen-elemen blok informasi dengan barang-barang (pencarian: BeforeIndex).
Rencana masa depan
Pendekatan ini tidak ideal dalam hal kinerja. Dengan peningkatan ukuran kamus menjadi 1M + kata, waktu respons basis data dapat meningkat secara signifikan. Meskipun kamusnya kecil, kinerjanya cocok untuk kami. Mungkin perlu untuk mengimplementasikan algoritma di masa depan melalui otomat Levenshtein atau pohon awalan.
Kesimpulan
Jadi, tidak ada mesin pencari yang dihindarkan dari penampilan kueri yang melanggar aturan ejaan yang diterima secara umum - baik itu kesalahan ketik acak atau benar-benar kurangnya pengetahuan tentang ejaan kata-kata. Oleh karena itu, tanpa beralih ke opsi pencarian fuzzy klasik Google atau Yandex, Anda dapat membuatnya sendiri, berkat pengguna dan pemilik situs dapat memperoleh hasil yang diinginkan.
Kode implementasi kami dapat dilihat di repositori:
github.com/qsoft-dev/damlev-bitrix