Mesin Pencari yang Dibuat dengan 80 Baris Python

 (alexmolas.com)
6 poin oleh GN⁺ 2024-02-08 | 1 komentar | Bagikan ke WhatsApp
  • microsearch adalah implementasi mainan untuk memahami langsung bagian dalam mesin pencari; kelas inti mesin pencarinya kurang dari 80 baris, tetapi proyeknya lebih besar jika menyertakan crawler, API, dan template HTML
  • Dengan latar belakang masalah situs web kecil dan blog yang sulit ditemukan di mesin pencari besar, data pencarian dibuat dengan mengumpulkan artikel dari 642 RSS feed
  • Crawling asinkron berbasis asyncio memangkas waktu pengumpulan dari 20 menit menjadi 20 detik, dan isi teks yang sudah dibersihkan disimpan sebagai data Parquet
  • Pencarian berjalan di atas inverted index yang menghubungkan kata dengan jumlah kemunculannya per URL, dan pengurutan hasil menggunakan BM25 berbasis konten alih-alih PageRank berbasis tautan
  • UI FastAPI menyediakan kotak pencarian dan halaman hasil, tetapi fitur seperti operator kueri, indeks n-gram, ekspansi kueri/dokumen, dan pengindeksan saat crawling belum tersedia

Tujuan dan cakupan microsearch

  • microsearch adalah implementasi mesin pencari Python yang dipublikasikan di repositori GitHub
  • Tujuannya bukan membuat mesin pencari untuk produksi, melainkan membuat contoh mainan yang bisa digunakan untuk menunjukkan bagaimana mesin pencari bekerja di dalamnya
  • Target pencariannya lebih dekat ke situs web kecil dan blog yang sulit ditemukan dalam persaingan SEO Google
  • Implementasi inti mesin pencari kurang dari 80 baris, tetapi keseluruhan proyek lebih besar jika mencakup kode pendukung seperti crawler data, API, dan template HTML
  • Implementasi ini dibuat dalam proses mempelajari Solr dan Lucene serta memahami cara kerja mesin pencari secara lebih mendalam

Crawler berbasis RSS

  • Untuk membuat data yang akan dicari, crawler menjelajahi RSS feed blog
  • Feed yang digunakan berjumlah total 642 RSS feed
    • Sekitar 100 di antaranya adalah blog yang dibaca langsung, seperti ML, sains data, dan matematika
    • Sekitar 500 sisanya diambil dari proyek surprisetalk blogs.hn
  • Alur crawling adalah mengekstrak URL artikel dari tiap RSS feed, mengunduh HTML artikel, lalu membersihkan teks isi artikel
  • Pembersihan HTML menggunakan BeautifulSoup untuk menghapus script dan style, lalu merapikan baris baru dan spasi sebelum mengubahnya menjadi teks
  • Dengan crawling asinkron menggunakan aiohttp dan asyncio, waktu eksekusi turun dari 20 menit menjadi 20 detik
  • Hasilnya dibuat sebagai DataFrame berisi URL dan isi yang sudah dibersihkan, lalu disimpan ke output.parquet

Struktur inverted index

  • Struktur data inti pertama dari mesin pencari adalah inverted index
  • Inverted index memetakan kata kunci ke dokumen, sehingga dokumen mana yang berisi kata tertentu bisa ditemukan dengan cepat
  • Implementasinya menggunakan defaultdict berbentuk dict[str, dict[str, int]]
    • Kunci luar adalah kata
    • Kunci dalam adalah URL
    • Nilai dalam adalah jumlah kemunculan kata tersebut di dokumen pada URL itu
  • Kelas SearchEngine memiliki dua dictionary internal
    • _index: menyimpan jumlah kemunculan URL per kata
    • _documents: menyimpan konten asli per URL
  • index(url, content) menormalisasi konten lalu memisahkannya berdasarkan spasi, dan menambah jumlah kemunculan tiap kata per URL
  • bulk_index() menerima daftar URL dan konten untuk mengindeks banyak dokumen sekaligus
  • get_urls(keyword) menormalisasi kata kunci lalu mengembalikan URL yang berisi kata tersebut beserta jumlah kemunculannya

Normalisasi string dan pencarian dasar

  • Normalisasi string mengganti tanda baca dengan spasi, merapikan spasi berlebih, lalu mengubahnya menjadi huruf kecil
  • Untuk mengurangi perbedaan huruf besar-kecil, Foo dan foo diperlakukan sebagai kata kunci yang sama
  • Jika dua dokumen contoh diindeks, hasil pencarian foo mengembalikan kedua dokumen
    • Foo: Hello, World! My name is Foo!
    • Bar: Hello, World! My name is Bar, I'm not Foo!
  • Pada tahap ini, mesin hanya mengetahui apakah dokumen berisi kata pencarian dan berapa kali kata itu muncul, sehingga diperlukan pemeringkatan terpisah untuk menentukan urutan hasil

Ranker BM25

  • Untuk mengurutkan hasil pencarian digunakan BM25
  • PageRank memeringkat dokumen berdasarkan tautan, sedangkan BM25 menghitung skor berdasarkan konten dokumen
  • SearchEngine memiliki parameter default k1=1.5 dan b=0.75 untuk perhitungan BM25
  • Kelas ini menyediakan atribut yang dibutuhkan untuk perhitungan ranking
    • posts: daftar URL yang sudah diindeks
    • number_of_documents: jumlah total dokumen
    • avdl: panjang rata-rata dokumen
  • idf(kw) menghitung inverse document frequency untuk kata kunci tertentu
    • Jumlah total dokumen N
    • Jumlah dokumen yang berisi kata kunci tersebut n_kw
    • Menggunakan rumus log((N - n_kw + 0.5) / (n_kw + 0.5) + 1)
  • bm25(kw) menghitung skor BM25 untuk tiap URL yang berisi kata kunci tersebut
  • search(query) menormalisasi kueri dan memecahnya menjadi kata, lalu menjumlahkan skor BM25 tiap kata per URL dan mengembalikannya
  • Dalam contoh, jika hanya mencari foo, skor dokumen Foo lebih tinggi daripada Bar; jika mencari foo bar, skor dokumen Bar menjadi lebih tinggi

Antarmuka FastAPI

  • Mesin pencari diekspos sebagai aplikasi FastAPI kecil
  • Aplikasi membuat instance SearchEngine, lalu saat startup membaca URL dan konten dari data Parquet dan mengindeksnya dengan bulk_index()
  • Ada tiga route utama
    • /: merender halaman pencarian dan meneruskan daftar artikel yang sudah diindeks
    • /results/{query}: menjalankan pencarian untuk kueri dan menampilkan 5 URL teratas di halaman hasil
    • /about: merender halaman perkenalan
  • Hasil diurutkan menurun berdasarkan skor, lalu hanya URL top-N yang dipilih
  • UI dan UX masih punya banyak ruang untuk diperbaiki, tetapi pencarian berjalan cepat dan hasilnya juga cukup baik

Fitur yang belum ada dan keterbatasan

  • Implementasi ini belum memiliki banyak fitur yang bisa diharapkan dari mesin pencari nyata
  • Tidak ada operator kueri
    • Misalnya, pencarian seperti how to build a search engine -solr di Google, yang mengecualikan kata tertentu, belum didukung
  • Tidak ada indeks n-gram
    • Cara mencari hanya dokumen yang memuat dua kata dalam urutan tertentu, seperti "search engine", belum didukung
  • Tidak ada ekspansi kueri atau dokumen
    • Meski mencari engine, dokumen yang berisi engines tidak otomatis ikut ditemukan
  • Crawling dan pengindeksan masih terpisah
    • Keduanya bisa diintegrasikan dengan cara mengindeks dokumen segera setelah diterima, dan proses ini juga bisa dibuat asinkron

Langkah berikutnya

  • Melalui proyek ini, muncul intuisi yang lebih baik tentang bagaimana Solr bekerja di dalamnya
  • Terlihat juga bahwa kode asinkron sangat efektif untuk pekerjaan yang berpusat pada IO
  • Langkah berikutnya adalah menambahkan fitur semantic search ke mesin pencari
  • Eksperimen dengan model embedding dan ANN sudah dilakukan, dan pekerjaan berikutnya adalah memasukkan fitur itu ke microsearch

Bacaan terkait

1 komentar

 
GN⁺ 2024-02-08
Pendapat di Hacker News

  • Ini benar-benar keren. Saya sedang membuat mesin pencari BM25 yang cukup cepat untuk pengujian lokal dengan Pandas: https://github.com/softwaredoug/searcharray
    Alasan memakai Pandas adalah karena BM25 saja tidak cukup, dan saya ingin mudah menghitung serta menggabungkan faktor lain seperti kebaruan dan popularitas dengan pandas/numpy
    Sebagai catatan, pencarian frasa adalah bagian yang sulit. Pencocokan frasa punya banyak edge case, dan hal seperti slop juga harus dipertimbangkan. Informasi posisi juga harus dikompresi dengan memori seminimal mungkin: https://github.com/softwaredoug/searcharray/blob/main/searcharray/utils/roaringish.py

    • Saya pernah menangani pencocokan frasa di proyek mainan: https://github.com/vasilionjea/lofi-dx/blob/main/test/search/inverted-search.test.ts#L140
      Saya rasa sudah mengujinya cukup menyeluruh, tetapi akan senang mendapat masukan. Informasi posisi saya delta-encode lalu encode dengan base36
    • Saya penasaran apakah memasukkan analisis sentimen membantu pemrosesan frasa, atau justru merugikan. Frasa memang sulit ditangani, dan saya sedang memikirkan apa yang bisa dilakukan untuk meningkatkan performa
    • Saya penasaran bagaimana Anda menemukan tulisan ini dan berkomentar secepat ini. Ingin tahu apakah Anda memakai semacam alat pemantau pencarian yang memindai halaman pertama untuk mencari kata kunci yang diminati, atau hanya kebetulan

  • Benar. Sebagian besar hal sulit dalam pencarian ada pada penanganan skala data. Logikanya sendiri bisa sangat mudah, atau dibuat mudah
    Tentu saja bisa juga dibuat rumit tanpa akhir, tetapi proyek ini berhasil memangkas bagian yang tidak perlu. Jika pendekatannya bukan memperbesar mesin pencari, melainkan membuat data secara fisik lebih kecil atau meningkatkan rasio sinyal-terhadap-noise, kita bisa melangkah cukup jauh

  • Kalau melihat src/microsearch/engine.py, ada kode seperti SearchEngine.__init__(self, k1: float = 1.5, b: float = 0.75), tetapi saya sama sekali tidak tahu apa itu k1 atau b, dan tidak ada satu pun komentar di seluruh file
    Apakah komentar sekarang sudah tidak populer? _documents sepertinya key-nya URL dan value-nya isi URL tersebut, tetapi bisa saja saya salah. Ini bisa menjadi materi untuk belajar dan mengembangkan cara membuat mesin pencari, tetapi kualitas kodenya terasa disayangkan karena tidak didokumentasikan

    • Bagian itu dijelaskan di artikelnya, dan artikel itu sendiri berfungsi sebagai dokumentasi kode. Tautan BM25 mengarah ke latar belakang matematis, dan kalau sedikit mencari lagi tentang parameter BM25, akan muncul tulisan terkait yang membahas cara memilihnya
    • Agar judul artikel menarik perhatian, jumlah baris kode harus ditekan seminimal mungkin ;)
      Di luar bercanda, saya setuju bahwa biasanya lebih baik jika dokumentasi dan kode ada bersama. Namun dalam kasus ini, karena ini proyek edukatif, kode dan dokumentasi dipisah, lalu kodenya didokumentasikan di tulisan blog
    • Karena sedang di ponsel saya tidak bisa melihat detailnya, tetapi k1 dan b adalah nilai bobot standar yang dipakai dalam TF-IDF atau BM25, dan di sini yang dimaksud BM25
      Komentar tentu berguna, tetapi bagi orang yang akrab dengan masalah ini, nama itu juga langsung bisa dikenali
    • k1 dan b adalah parameter penyetel untuk fungsi peringkat BM25. Itu bukan nama yang baru dibuat oleh penulis asli, melainkan nama variabel yang dipakai di hampir semua implementasi dan buku teks
      Bagi orang yang memahami bidang temu kembali informasi, justru penamaan k1 dan b itulah yang tepat: https://en.wikipedia.org/wiki/Okapi_BM25
    • Melihat pola seperti a: float selalu mengingatkan saya pada ceramah Rich Hickey, “yang Anda butuhkan bukan tipe, melainkan nama yang tepat”
      Saya sangat tidak suka kecenderungan memakai nama variabel satu huruf tanpa penjelasan, yang terasa seperti berasal dari Go, lalu menyalahgunakan sistem tipe seolah-olah itu alat bantu penamaan. Nama dapat menyampaikan informasi semantik tentang apa yang dilakukan program, jadi harus dipakai dengan benar

  • Saya tidak mengerti apa artinya membanggakan jumlah baris kode, bukan jumlah total \r\n, sambil memakai dependensi eksternal
    Memang tidak ada satuan SI untuk mengukur codebase, tetapi menurut saya beban kognitif tetap harus diukur entah bagaimana

    • Ini bukan standar resmi, tetapi di tim kami kadang kami merujuk ke https://grugbrain.dev dan mengatakan “kode ini tidak grug” atau “kode ini cukup grug”
    • Mesin pencari 80 baris itu sendiri tidak memakai dependensi eksternal. Ia hanya mengimpor collections, math, dan string, semuanya pustaka standar
      Namun mungkin lebih tepat menyebutnya “engine mesin pencari”. Crawler dan antarmuka tidak termasuk dalam 80 baris itu, tetapi tetap diperlukan dalam satu bentuk atau lainnya, dan implementasi yang disajikan memang cukup menambah jumlah baris serta pustaka. Meski begitu, pustaka-pustaka itu tidak terkait dengan mesin pencari itu sendiri. Kalau kita mulai menghitung dependensi umum seperti pandas atau fastapi, mungkin kita juga harus menghitung jutaan baris dalam sistem operasi, firmware kartu jaringan, sampai kompleksitas hardware
    • Apakah ada alasan kita tidak boleh merayakan pencapaian industri yang memungkinkan hal seperti ini dibuat dalam 80 baris?
    • Di sini itu bermakna. Kalau judulnya “mesin pencari yang dibuat dengan 4000 baris Python”, kebanyakan orang mungkin akan melewatinya begitu saja, tetapi 80 baris cukup pendek untuk layak dilihat
    • Cara lama untuk hal semacam ini adalah kompleksitas siklomatik

  • Saya suka. Mesin rekomendasi di bawah 20 baris yang bisa dipakai bersama mesin pencari juga memungkinkan. Jika menyimpan log sesi URL yang diklik, Anda bisa melihat sliding window setelah URL saat ini di tiap sesi, memberi bobot lebih tinggi untuk tautan yang lebih dekat, lalu membuat daftar rekomendasi
    Jika hasil rekomendasi diurutkan dan hanya N teratas yang disisakan, Anda mendapatkan daftar URL rekomendasi untuk URL tertentu. Dengan sedikit penyesuaian, Anda juga bisa mencampurkan kueri pencarian yang dimasukkan dan URL yang diklik ke dalam log untuk menghasilkan saran ejaan

  • Sangat keren dan edukatif. Tapi jangan dipakai untuk deployment :-)
    Dulu saya pernah membutuhkan sesuatu yang mirip, tetapi skalanya sedikit lebih besar, sekitar puluhan ribu dokumen, dan jawabannya, seperti biasa, adalah sqlite. Secara struktural sama seperti yang ada di sini, hanya saja lapisan persistensi indeks terbalik-nya sudah ditulis oleh orang lain

    • Saya memakai SQLite FTS hampir di mana-mana, dan belum pernah mengecewakan
    • Ternyata bahkan rumus yang sama juga ada di sana. Berkat komentar ini saya merasakan semacam “getaran pemahaman”

  • Jika mencari dengan tanda kutip ganda seperti "search engine", Google hanya menampilkan hasil yang memuat dua kata itu dalam urutan tersebut
    Setidaknya begitu dalam sebagian kasus, tetapi sayangnya tidak selalu. Yang diinginkan pengguna mahir adalah “grep untuk web”, bukan “sesuatu yang memberi tahu apa yang ingin Google tampilkan”

    • Saya berani memastikan hampir tidak ada orang yang benar-benar menginginkan “grep untuk web”. Dibandingkan dengan mesin pencari yang hanya melakukan ekspansi kueri sangat kecil sekalipun, grep untuk web jelas lebih buruk
      Memang benar Google mengambil terlalu banyak kebebasan saat menafsirkan kueri, tetapi ada banyak pemrosesan yang jelas lebih baik dilakukan oleh mesin pencari mana pun daripada tidak dilakukan sama sekali. Masalah Google Search saat ini adalah sulit menebak mengapa hasil seperti itu muncul, dan tampaknya karena terlalu banyak bergantung pada embedding untuk perbandingan string. Menjengkelkan ketika "cat food" dicocokkan dengan "dog restaurant", misalnya: secara semantik dekat di ruang embedding, tetapi tidak cocok dengan penalaran manusia

  • Menurut saya tidak adil menyebutnya kode 80 baris kalau memakai library eksternal seperti feedparser, bs4, dan sebagainya

    • Kalau dibuat di atas elasticsearch, saya setuju, tetapi jika bagian mesin pencari yang sebenarnya diimplementasikan dalam 80 baris itu, menurut saya adil. Library yang diimpor memang jenis yang sebaiknya tidak diimplementasikan sendiri
      Kadang ada tulisan “membuat mesin pencari sendiri” yang sebenarnya hanya panduan instalasi searxng atau yacy, tetapi ini berbeda dari kasus seperti itu
    • Menurut saya tidak masalah kalau dependensinya sangat umum dan arus utama

  • Bagus. Menambahkan fitur pencarian fuzzy ke sini sepertinya juga tidak terlalu sulit. Misalnya, agar pencarian "hackrnew" cocok dengan "hackernews", caranya adalah mencari hasil yang jarak edit prefiksnya berada di bawah ambang tertentu
    Ide dasarnya adalah menambahkan satu indeks terbalik lagi, dengan kunci berupa n-gram (biasanya 3-gram) dari kata-kata dalam koleksi dokumen, dan posting berupa kata atau ID kata tempat n-gram itu muncul. Kita bisa memakai lema berikut: jika PED(x, y) <= delta, maka |N(x) ∩ N(y)| >= |N(x)| - n ∙ delta. Hitung n-gram dari input x, ambil posting untuk tiap n-gram, lalu gabungkan duplikatnya untuk mendapatkan jumlah n-gram yang sama dengan tiap kandidat kata y. Jika jumlah ini lebih besar dari batas, barulah hitung PED sebenarnya; jika lebih kecil, lewati, sehingga banyak mengurangi komputasi mahal
    Daftar kata yang diperoleh dengan cara ini kemudian cukup dipakai untuk menanyakan indeks yang sudah ada. Dulu saya memakai pendekatan ini saat membuat mesin pencari fuzzy JS sisi klien di https://dont.watch/. Jika melihat isi kode JS-nya, terlihat indeks terbalik dan indeks n-gram terkompresi dikirim apa adanya sebagai file JS. Mesin pencari sebenarnya sekitar 300 baris JS tanpa dependensi eksternal, dan hanya berisi heuristik yang sangat dasar untuk memperbaiki hasil pencarian

    • Dengan cara itu, seberapa besar ukuran indeks bertambah?