Bayangkan hari pertama Anda di pekerjaan baru. Kantor ini terletak di area stasiun metro Kurskaya yang sama sekali tidak dikenal. Makan siang mendekat. Anda membuka aplikasi pencarian, menulis
"makan di Kursk" dan mendapatkan pilihan opsi di mana Anda dapat makan.
Apa yang ada di balik permintaan
"makan di Kursk" dan bagaimana diproses untuk menemukan apa yang Anda butuhkan? Dalam artikel ini saya akan memberi tahu Anda bagaimana tim Pencarian 2GIS melakukan segala yang mungkin untuk membuat kehidupan di kota lebih nyaman dan nyaman bagi pengguna.
Penting untuk dipahami bahwa teks permintaan pencarian hanyalah puncak gunung es, sebagian kecil dari apa yang berinteraksi langsung dengan pengguna. Permintaan pencarian itu sendiri, selain teks, berisi banyak data lainnya. Mereka termasuk informasi yang dipersonalisasi tentang lokasi pengguna, area peta yang dilihatnya, serangkaian catatan dari favoritnya, dan informasi tentang mode pencarian. Misalnya, pencarian di peta atau di gedung, atau mungkin pencarian untuk arah. Data adalah kunci keberhasilan fungsionalitas pencarian yang baik.
Kami sangat memperhatikan data dan strukturnya. Selain itu, kami menyebut algoritma pencarian dalam pencarian struktural 2GIS, karena dipertajam oleh pencarian yang efektif dan cepat dalam data terstruktur kami. Kami secara khusus menyiapkan indeks pencarian dan data dari mana ia dibangun. Saya tidak akan merinci, saya hanya bisa mengatakan bahwa data diatur sedemikian rupa agar cukup sederhana untuk diproses, terkompresi dengan baik, dan yang paling penting, ini memungkinkan kita untuk memprosesnya dengan cepat bahkan pada perangkat seluler.
Selain itu, pencarian dapat bekerja offline, dan karenanya membuat tuntutan khusus pada kecepatan dan volume indeks pencarian. Kami sangat memperhatikan fitur ini - kami terus-menerus mengompres indeks pencarian, mengevaluasi kinerja pada semua jenis platform dan mempercepat fungsionalitas di mana kasus pencarian spesifik melebihi batas waktu yang ditentukan. Ngomong-ngomong, kita dapat menyombongkan bahwa permintaan pencarian biasa di 2GIS pada perangkat seluler lebih cepat daripada aplikasi menggambar daftar drop-down berdasarkan hasil.
Di bawah ini saya akan mengungkap tabir kerahasiaan yang menutupi keajaiban pencarian kami. Sebagai contoh, kami menerima permintaan yang disebutkan
"makan di Kursk" . Pertimbangkan tahapan prosesnya dan apa yang terjadi pada masing-masingnya. Jadi ayo pergi!
Tahap 1. Parsing
Parameter input: permintaan
"eat on Kursk"Pertama-tama, kita perlu mem-parsing teks permintaan. Ini penting, karena setelah parsing kita dapat bekerja bukan dengan teks permintaan, tetapi dengan set token yang berisinya. Token adalah kata permintaan tunggal. Dalam kasus kami, kami akan menerima satu set tiga token:
"eat" ,
"on" ,
"Kursk" . Tampaknya semuanya sederhana, tetapi iblis ada dalam perinciannya. Dan kadang-kadang tidak begitu jelas: misalnya, dalam kueri "wi-fi" atau "ke-2", kita harus memahami bahwa kita harus menangani kombinasi tersebut secara keseluruhan.
Token itu sendiri berisi informasi tentang teks kata, tentang posisi dalam permintaan, tentang keberadaan pemisah yang mengikuti kata dan beberapa karakteristik kata - register karakternya, apakah kata itu angka, nomor urut, nomor telepon, alamat atau data lainnya.
Tahap 2. Pencarian Kamus
Parameter input: token
“eat” ,
“on” ,
“Kursk”Dengan daftar token permintaan yang siap, kami melanjutkan ke tahap pencarian kamus, yaitu, ke tahap di mana untuk setiap token kami menemukan daftar bentuk kata dari data kami. Bentuk kata adalah informasi yang dikodekan tentang akar kata dan akhirnya.
Kami menyajikan pencarian kamus sebagai algoritme untuk menganalisis kamus, disajikan dalam bentuk grafik. Node di dalamnya adalah huruf, atau lebih tepatnya, simbol. Grafik terdiri dari simbol node dan transisi antara node ini. Hasil dari berkeliling grafik kamus kami adalah banyak bentuk kata yang bisa kita dapatkan berdasarkan token yang ditransfer dari tahap sebelumnya. Jadi kami mencoba menemukan di dalam kamus kami urutan karakter yang cocok dengan token berikutnya dari permintaan. Pada saat yang sama, seperti yang kita semua tahu, pengguna membuat kesalahan ketik, kehilangan huruf atau bahkan membuat kesalahan dalam tata letak keyboard. Karena itu, ketika berkeliling kamus, kami menerapkan beberapa manipulasi untuk memperhitungkan faktor manusia yang mungkin atau mencoba menebak apa yang diperoleh seseorang saat ini. Berbagai transformasi rantai karakter digunakan: menyisipkan, penggantian, menambahkan karakter, dan sejenisnya.
Akibatnya, untuk setiap token permintaan dari grafik, kami mengekstrak sekumpulan bentuk kata dengan informasi tentang akar dan akhir kata, informasi tentang jumlah karakter dalam bentuk kata, dan perkiraan yang ditemukan. Estimasi temuan - penilaian yang mengkarakterisasi jarak kosa kata dari urutan karakter yang ditemukan ke urutan yang diinginkan. Evaluasi mencirikan seberapa banyak string karakter yang ditemukan berbeda dari token permintaan.
Jadi untuk token kita menemukan bentuk kata:
- 13 formulir untuk "makan" : "makan", "makan", "paese", "payot", ...
- 3 formulir untuk "on" : "na", "nu", "on"
- 48 formulir untuk "Kursk" : "Kursk", "Kursk", "Kursk", "Kursk", "Kurako", ...
Selanjutnya, bentuk kata yang ditemukan disaring tergantung pada penilaian mereka. Yang terbaik dari mereka, yaitu, sedekat mungkin dengan kata-kata dari permintaan, termasuk dalam daftar istilah. Yang kami maksud adalah bentuk kata dan estimasi temuan. Plus, selain bentuk kata yang ditemukan, istilah yang ditambahkan menggunakan aturan morfologi ditambahkan ke daftar. Langkah penting dalam pemrosesan morfologis adalah penambahan penilaian morfologis. Faktanya adalah bahwa pencarian kami menggunakan mekanisme pemrosesan morfologis yang kuat yang memungkinkan kami tidak hanya untuk menemukan kata-kata yang mirip dari kamus, tetapi menurut aturan bahasa alami, lebih akurat untuk menemukan apa yang sebenarnya menarik minat pengguna dengan makna, dan bukan hanya dengan kesamaan kata.
Jadi untuk token, ketentuan akan dibuat:
- "Makan" : "makan", "makan", "makan", "makan", "makan"
- "Aktif" : "hidup", "na", "nu"
- "Kursk" : "Kursk", "Kursk", "Kursk", "Kursk", "Kursk"
Pada tahap ini, pencarian kamus berakhir. Kami telah memproses permintaan dan meminta setiap token daftar istilah yang akan diproses lebih lanjut. Istilah-istilah ini mengandung semua informasi tentang kata yang diwakilinya, dan memiliki penilaian tentang bagaimana masing-masing ditemukan.
Langkah 3. Menemukan Entri Data
Input: serangkaian istilah untuk setiap bagian dari permintaan
- "Makan" : "makan", "makan", "makan", "makan", "makan"
- "Aktif" : "hidup", "na", "nu"
- "Kursk" : "Kursk", "Kursk", "Kursk", "Kursk", "Kursk"
Setelah menerima serangkaian istilah untuk setiap bagian dari permintaan dari tahap sebelumnya, kami melanjutkan untuk mencarinya dengan indeks kami. Setiap dokumen dalam data memiliki banyak judul dan ditulis dalam
indeks terbalik sehingga kita dapat dengan mudah menemukan semua referensi ke istilah yang diinginkan dalam dokumen spesifik yang mewakili organisasi, alamat atau yang lainnya.
Untuk setiap bagian dari permintaan dan untuk setiap persyaratan dari bagian-bagian ini, kami sedang mencari dokumen yang mengandung kata-kata yang dikodekan dalam istilah. Jadi, untuk sebagian permintaan, entri akan ditemukan dalam semua ketentuan:
- "Makan" : 18 entri
- Pada : 4.304 entri
- Kursk : 79 entri
Jelas, preposisi
"on" terjadi berkali-kali dan karenanya jatuh ke dalam banyak judul dokumen - "take-out coffee", "play
on the console", "registrasi the machine".
"Makan" dan
"Kursk" juga digunakan berulang kali. Kata kedua dengan istilahnya ditemukan dalam data kami jauh lebih sering daripada yang pertama.
Dengan klik, kami menganggap kecocokan kata dari permintaan pencarian dengan kata dari dokumen tertentu. Hit ini disimpan dalam daftar, yang akan dianalisis pada langkah selanjutnya. Saat menambahkan klik, kami tidak hanya menyalin data tentang kata dalam dokumen dari istilah tersebut, tetapi juga menghitung estimasi terbaik tentang bagaimana kata itu dapat ditemukan. Dengan kata lain, kami memilih penilaian morfologis dari istilah tersebut, atau penilaian tentang bagaimana istilah itu ditemukan dalam kamus, tergantung pada peringkat mana yang lebih dekat dengan token permintaan.
Tahap ini merupakan awal dari awal pencarian itu sendiri. Kami telah menyiapkan serangkaian klik dalam dokumen tertentu, berdasarkan algoritma mana yang akan memilih dan mengevaluasi apa yang perlu diberikan kepada pengguna sebagai hasilnya.
Tahap 4. Jantung pencarian
Pintu masuk: daftar sasaran
- "Makan" : 18 entri
- Pada : 4.304 entri
- Kursk : 79 entri
Bahkan, daftar sasaran dalam implementasi kami adalah wadah yang cukup rumit. Penting untuk dipahami bahwa ketika menambahkan klik ke sana, node khusus dibuat di mana hit itu direkam, dan tautan ke dokumen tempat hit tersebut jatuh.
Oleh karena itu, akan lebih tepat untuk menampilkan data input sebagai berikut:
Pintu masuk: wadah simpul dokumen
- document1: {hits, ...}
- document2: {hits, ...}
- document3: {hits, ...}
- document4: {hits, ...}
- ...
Pertama-tama, pencarian mulai melewati pohon dokumen dan setiap node mengirimkannya ke penganalisa, yang mengevaluasi apakah dokumen dari simpul ini cocok untuk menjadi hasil untuk masuk ke output. Untuk memahami volume yang harus dianalisa oleh penganalisa, saya akan mengatakan bahwa pada awalnya wadah tersebut berisi lebih dari 3000 node! Tetapi node dapat ditambahkan selama proses crawl, oleh karena itu, sebenarnya diproses lebih lanjut. Tidak berlebihan untuk mengatakan bahwa analisis adalah bagian yang paling mahal dari pencarian dan pada saat yang sama salah satu fungsi proyek yang paling kompleks dan besar. Namun demikian, ini berjalan sangat cepat bahkan pada perangkat seluler.
Tahap 5. Analisis
Input: Node
dokumen: {hits, ...}Analisis dimulai dengan mendapatkan daftar judul dari node. Judul adalah judul dan daftar klik yang termasuk dalam judul dokumen ini. Judul-judul ini akan dievaluasi pada tahap pertama. Penting bagi kita untuk mengetahui manfaat dari setiap judul. Kegunaan bisa baik, lemah dan sampah.
Untuk setiap judul, yang terbaik dari rantai hit dipilih - yang terbaik dalam panjang dan skor kosa kata, terdiri dari kesamaan dari hit. Berdasarkan rantai terbaik, judul akan dievaluasi utilitasnya. Untuk menentukan kegunaan rantai, kami juga menggunakan mekanisme berdasarkan frekuensi kata dalam dokumen. Secara kasar, semakin sering sebuah kata muncul di dokumen, semakin penting artinya (
TF-IDF ). Jadi, jika rantai berisi kata penting dari judul dokumen tanpa perbedaan morfologis yang kuat, misalnya, jumlah yang sangat baik atau jenis kelamin, kami menganggap judul tersebut berguna. Judul juga dapat bermanfaat jika hitnya sepenuhnya mencakup kata-kata dari judul dokumen.
Menggunakan utilitas, semua judul membentuk topeng utilitas untuk node. Topeng ini memberi kita gambaran tentang token permintaan yang dicakup oleh simpul yang dianalisis. Dan dengan bantuannya, kami sangat menentukan apakah akan menganalisis node lebih lanjut.
Sebagai hasilnya, kami tidak hanya memiliki satu dokumen dari indeks, tetapi satu set data struktural yang mewakili hasil potensial dengan informasi tentang bagaimana ia dapat ditemukan.
Langkah 6. Evaluasi
Input: Node
dokumen: {hits, ...}Bergantung pada topeng utilitas, kami akan memproses node, atau segera melanjutkan ke yang berikutnya. Dari sekian banyak node yang diproses, kami mengumpulkan berbagai informasi tentang totalitasnya. Misalnya, banyak judul node, hubungan antara node dan beberapa data lainnya.
Selanjutnya dimulai analisis judul-judul node yang saling berhubungan satu sama lain. Faktanya, banyak node digabungkan ke dalam grafik node, yang kami evaluasi.
Dari simpul-simpul dari simpul-simpul grafik, kita mendapatkan daftar judul-judul peringkat. Sederhananya, dari berbagai node kami menyusun satu daftar judul, di mana untuk setiap elemen kami juga menambahkan perkiraan dan kombinasi faktor dari hits judul semua node yang berpartisipasi.
Evaluasi - suatu struktur dengan informasi tentang jumlah kata yang terlibat dalam suatu judul dari suatu permintaan dan banyak faktor lain tentang bagaimana kata itu ditemukan dan diproses - mulai dari tahap pencarian kamus. Adalah penting bahwa nilai-nilai ini dari judul peringkat akan berpartisipasi dalam pemilihan nilai terbaik. Beberapa dari mereka akan ditandai sebagai dipilih dan akan berkontribusi pada penilaian akhir dari hasil yang dilihat pengguna.
Penilaian keseluruhan memberikan informasi hasil yang akan sangat penting dalam menyortir seluruh output. Ini berisi faktor-faktor seperti, misalnya, kata-kata yang hilang dari kueri. Ukuran ini mencirikan jumlah kata yang tidak tercakup oleh simpul dengan informasi strukturalnya.
Berdasarkan informasi tentang kegunaan judul, kejelasan hasilnya ditentukan. Kejelasan bisa baik, lemah dan buruk. Dan itu dihitung dengan partisipasi semua judul yang dipilih untuk simpul yang diproses. Semua data ini memiliki efek dramatis pada nasib hasil dan urutan penerbitannya.
Secara bertahap, kami mendekati akhir analisis node. Sebelum node akhirnya meninggalkan analisa dan menjadi hasil yang potensial, kami melakukan beberapa manipulasi yang lebih spesifik. Misalnya, kompatibilitas judul dokumen yang dipilih.
Node yang telah melewati semua lingkaran alat analisa membentuk hasil yang berisi informasi tentang header dan dokumen yang dipilih. Hasilnya, yang memberikan cakupan yang baik dari permintaan pencarian, dikirim ke post-processing.
Langkah 7. Post Processing
Input: hasil dibangun dari simpul
Analisator menyaring banyak catatan dari indeks sebelum hasilnya. Namun, selama analisis, banyak hasil potensial dapat dievaluasi dan dikirim untuk diproses. Untuk menunjukkan kepada pengguna satu-satunya yang paling berguna dalam urutan relevansi, kita perlu memotong opsi terburuk yang ditemukan oleh penganalisa.
Pada langkah sebelumnya, penilaian umum dari hasil disebutkan. Penilaian umum memungkinkan kita untuk memotong hasil terburuk pada tahap pasca-pemrosesan. Gradasinya adalah sebagai berikut. Hasil yang tidak mencakup token permintaan apa pun jelas lebih buruk daripada token yang sepenuhnya mencakup permintaan pengguna. Hasil dengan kejelasan yang lebih buruk jelas kurang diinginkan daripada hasil dengan kejelasan yang baik. Post-prosesor mengumpulkan informasi tentang hasil yang masuk dan menghilangkan yang jelas lebih buruk. Sisanya menambah daftar.
Sebelum kami memberikan informasi pengguna yang lapar tentang kafe, kami melakukan pemrosesan akhir - urutkan berdasarkan relevansi. Penyortiran melibatkan banyak faktor, dihitung dan dikumpulkan pada berbagai tahap pencarian. Dan pada akhirnya, hasil pencarian untuk
"makan di Kursk" adalah lebih dari 500 hasil. Banyak dari mereka ditemukan dengan cara yang sama, dan karenanya memiliki peringkat yang sama. Mereka akan diurutkan berdasarkan popularitas pengguna.
Kesimpulan
Kami menerima ekstradisi dengan banyak kafe dan restoran dan, senangnya, kami pergi makan malam. Kami mendapatkan semua hasil dalam sepersekian detik. Kami bahkan tidak memerlukan koneksi internet.
Aplikasi menyimpan indeks pencarian di perangkat. Skema semacam itu memberi kita tugas-tugas non-sepele mengoptimalkan kompresi data dan kecepatan pemrosesan - lagipula, pencarian harus bekerja dengan cepat pada berbagai macam perangkat seluler! Namun, ini adalah kisah yang sangat berbeda.
Hari ini saya mencoba membuka kap mesin pencari kami dan menunjukkan bagaimana kami membantu pengguna menemukan apa yang mereka butuhkan di kota, dan melakukannya dengan cepat dan mudah. Saya harap ini informatif.