80 Satır Python ile Yapılmış Arama Motoru

 (alexmolas.com)
6 puan yazan GN⁺ 2024-02-08 | 1 yorum | WhatsApp'ta paylaş
  • microsearch, arama motorlarının iç işleyişini doğrudan anlamak için yapılmış oyuncak bir uygulama; çekirdek arama motoru sınıfı 80 satırdan az olsa da crawler, API ve HTML şablonları dahil edildiğinde proje daha büyük
  • Küçük web siteleri ve blogların büyük arama motorlarında iyi keşfedilememesi sorunundan yola çıkarak, 642 RSS feed’inden yazılar toplayıp arama verisi oluşturuyor
  • asyncio tabanlı asenkron crawling ile toplama süresi 20 dakikadan 20 saniyeye düştü; temizlenmiş metinler Parquet verisi olarak saklanıyor
  • Arama, kelimeleri URL bazında görülme sayılarına bağlayan ters indeks üzerinde çalışıyor; sonuç sıralamada bağlantı tabanlı PageRank yerine içerik tabanlı BM25 kullanılıyor
  • FastAPI UI ile arama kutusu ve sonuç sayfası sunuyor; ancak sorgu operatörleri, n-gram indeksleme, sorgu/belge genişletme ve crawling sırasında indeksleme gibi özellikler henüz yok

microsearch’ün amacı ve kapsamı

  • microsearch, GitHub deposunda yayımlanan bir Python arama motoru uygulamasıdır
  • Amaç, üretim kullanımı için bir arama motoru değil; arama motorlarının içeride nasıl çalıştığını gösteren kullanılabilir bir oyuncak örnek oluşturmaktır
  • Arama kapsamı, Google SEO rekabetinde iyi keşfedilemeyen küçük web siteleri ve bloglara daha yakındır
  • Çekirdek arama motoru uygulaması 80 satırdan azdır; ancak veri crawler’ı, API ve HTML şablonları gibi yardımcı kodlar dahil edildiğinde projenin tamamı daha büyüktür
  • Uygulama, Solr ve Lucene ile çalışırken arama motorlarının işleyişini daha derinden anlama sürecinde ortaya çıkmıştır

RSS tabanlı crawler

  • Aranacak veriyi oluşturmak için blog RSS feed’leri crawl edilir
  • Kullanılan feed sayısı toplam 642 RSS feed’idir
    • Yaklaşık 100’ü ML, veri bilimi, matematik gibi yazarın doğrudan okuduğu bloglardır
    • Kalan yaklaşık 500’ü surprisetalk blogs.hn projesinden alınmıştır
  • Crawling akışı, her RSS feed’inden yazı URL’lerini çıkarmak, yazının HTML’ini indirmek ve ardından gövde metnini temizlemek şeklindedir
  • HTML temizleme, BeautifulSoup ile script ve style öğelerini kaldırır; satır sonlarını ve boşlukları düzenleyerek metne dönüştürür
  • aiohttp ve asyncio kullanılan asenkron crawling sayesinde çalışma süresi 20 dakikadan 20 saniyeye düşmüştür
  • Sonuçlar, URL ve temizlenmiş gövde metnini içeren bir DataFrame haline getirilip output.parquet dosyasına kaydedilir

Ters indeks yapısı

  • Arama motorunun ilk temel veri yapısı ters indekstir
  • Ters indeks, anahtar kelimeleri belgelere eşleyerek belirli bir kelimenin hangi belgelerde geçtiğini hızlıca bulmayı sağlar
  • Uygulama, dict[str, dict[str, int]] biçiminde bir defaultdict kullanır
    • Dış anahtar kelimedir
    • İç anahtar URL’dir
    • İç değer, ilgili kelimenin o URL’deki belgede kaç kez geçtiğidir
  • SearchEngine sınıfının iki dahili sözlüğü vardır
    • _index: kelime bazında URL görülme sayılarını saklar
    • _documents: URL bazında orijinal içeriği saklar
  • index(url, content), içeriği normalize ettikten sonra boşluklara göre ayırır ve her kelimenin URL bazındaki görülme sayısını artırır
  • bulk_index(), URL ve içerik listelerini alarak birden fazla belgeyi tek seferde indeksler
  • get_urls(keyword), anahtar kelimeyi normalize ettikten sonra o kelimeyi içeren URL’leri ve görülme sayılarını döndürür

Dize normalizasyonu ve temel arama

  • Dize normalizasyonu, noktalama işaretlerini boşlukla değiştirir, yinelenen boşlukları temizler ve metni küçük harfe çevirir
  • Büyük/küçük harf farkını azaltmak için Foo ve foo aynı anahtar kelime olarak işlenir
  • İki örnek belge indekslendiğinde foo arama sonucu iki belgeyi de döndürür
    • Foo: Hello, World! My name is Foo!
    • Bar: Hello, World! My name is Bar, I'm not Foo!
  • Bu aşamada yalnızca belgenin arama terimini içerip içermediği ve kaç kez içerdiği bilinebildiğinden, sonuç sırasını belirlemek için ayrı bir sıralama gerekir

BM25 sıralayıcı

  • Arama sonuçlarını sıralamak için BM25 kullanılır
  • PageRank belgeleri bağlantılara göre sıralarken, BM25 puanı belge içeriğine göre hesaplar
  • SearchEngine, BM25 hesaplaması için varsayılan k1=1.5, b=0.75 parametrelerine sahiptir
  • Sınıf, sıralama hesaplaması için gerekli özellikleri sağlar
    • posts: indekslenmiş URL listesi
    • number_of_documents: toplam belge sayısı
    • avdl: ortalama belge uzunluğu
  • idf(kw), belirli bir anahtar kelimenin ters belge frekansını hesaplar
    • Toplam belge sayısı N
    • İlgili anahtar kelimeyi içeren belge sayısı n_kw
    • log((N - n_kw + 0.5) / (n_kw + 0.5) + 1) formülünü kullanır
  • bm25(kw), ilgili anahtar kelimeyi içeren her URL için BM25 puanını hesaplar
  • search(query), sorguyu normalize edip kelimelere ayırır; ardından her kelimenin BM25 puanını URL bazında toplayarak döndürür
  • Örnekte yalnızca foo arandığında Foo belgesinin puanı Bar’dan yüksektir; foo bar arandığında ise Bar belgesinin puanı daha yüksek olur

FastAPI arayüzü

  • Arama motoru küçük bir FastAPI uygulaması olarak sunulur
  • Uygulama bir SearchEngine örneği oluşturur ve başlangıçta Parquet verisinden URL ile içerikleri okuyup bulk_index() ile indeksler
  • Başlıca üç route vardır
    • /: arama sayfasını render eder ve indekslenmiş yazı listesini aktarır
    • /results/{query}: sorguyu arar ve en iyi 5 URL’yi sonuç sayfasında gösterir
    • /about: tanıtım sayfasını render eder
  • Sonuçlar puana göre azalan sırada sıralanır ve ardından yalnızca top-N URL seçilir
  • UI ve UX’in geliştirilebilecek çok yanı vardır; ancak arama hızlı çalışır ve sonuçlar da fena değildir

Eksik özellikler ve sınırlamalar

  • Uygulamada gerçek arama motorlarından beklenebilecek birçok özellik eksiktir
  • Sorgu operatörleri yoktur
    • Örneğin Google’daki how to build a search engine -solr gibi belirli bir kelimeyi hariç tutan aramaları desteklemez
  • n-gram indeksleme yoktur
    • "search engine" gibi iki kelimenin belirli bir sırayla geçtiği belgeleri bulma biçimi desteklenmez
  • Sorgu veya belge genişletme yoktur
    • engine arandığında engines içeren belgeler otomatik olarak bulunmaz
  • Crawling ve indeksleme ayrıdır
    • Belge alınır alınmaz indeksleme yapacak şekilde birleştirilebilir ve bu süreç de asenkron hale getirilebilir

Sonraki adımlar

  • Proje sayesinde Solr’ın içeride nasıl çalıştığına dair daha fazla sezgi kazanılmıştır
  • IO ağırlıklı işlerde asenkron kodun büyük etki yarattığı da görülmüştür
  • Sonraki adım, arama motoruna semantik arama özelliği eklemektir
  • Embedding modeli ve ANN ile denemeler yapılmıştır; bir sonraki iş bu özelliği microsearche eklemektir

İlgili okumalar

1 yorum

 
GN⁺ 2024-02-08
Hacker News yorumları

  • Bu gerçekten çok havalı. Yerelde test amaçlı, oldukça hızlı bir BM25 arama motorunu Pandas ile yapıyorum: https://github.com/softwaredoug/searcharray
    Pandas kullanmamın nedeni, sadece BM25’in yeterli olmaması ve güncellik, popülerlik gibi diğer etkenleri pandas/numpy ile kolayca hesaplayıp birleştirmek istemem
    Bu arada ifade araması zor kısım. İfade eşleştirmede çok fazla sınır durumu var ve slop gibi şeyleri de hesaba katmak gerekiyor. Konum bilgisini de mümkün olduğunca az bellekle sıkıştırmak lazım: https://github.com/softwaredoug/searcharray/blob/main/searcharray/utils/roaringish.py

    • Oyuncak bir projede ifade eşleştirme ile uğraşmıştım: https://github.com/vasilionjea/lofi-dx/blob/main/test/search/inverted-search.test.ts#L140
      Oldukça kapsamlı test ettiğimi düşünüyorum ama geri bildirim almak güzel olur. Konum bilgisini delta encoding ile kodladım ve base36 olarak kodladım
    • Duygu analizi eklemenin ifade işlemede yardımcı olup olmadığını, yoksa tersine zarar verip vermediğini merak ediyorum. İfadeleri ele almak zor; performansı iyileştirmek için ne yapılabileceğini düşünüyorum
    • Bu yazıyı bu kadar hızlı bulup yorum yapman merakımı çekti. İlgi anahtar kelimelerini bulmak için ilk sayfayı tarayan bir arama izleme aracı gibi bir şey mi kullanıyorsun, yoksa tamamen tesadüf mü?

  • Doğru bir nokta. Aramadaki zor kısmın çoğu veri ölçeğini yönetmekte yatıyor. Mantığın kendisi şaşırtıcı derecede kolay ya da kolaylaştırılabilir
    Elbette sonsuz derecede karmaşık hale getirilebilir ama bu proje gereksiz kısımları iyi budamış. Arama motorunu büyütme problemi olarak değil de veriyi fiziksel olarak küçültme veya sinyal-gürültü oranını artırma problemi olarak bakarsan oldukça ileri gidebilirsin

  • src/microsearch/engine.py içinde SearchEngine.__init__(self, k1: float = 1.5, b: float = 0.75) gibi kodlar var ama k1 ya da b’nin ne olduğunu hiç bilmiyorum ve dosyanın tamamında tek bir yorum bile yok
    Bu günlerde yorumlar moda değil mi? _documents anahtarı URL, değeri de o URL’nin içeriği gibi görünüyor ama yanılıyor da olabilirim. Arama motorunun nasıl yapıldığını öğrenmek ve üstüne koymak için iyi bir kaynak olabilirdi ama belgelendirme olmayınca kod kalitesi hayal kırıklığı yaratıyor

    • O kısım yazıda açıklanıyor ve yazının kendisi kodun belgesi işlevi görüyor. BM25 bağlantısı matematiksel arka plana gidiyor; BM25 parametrelerini biraz daha araştırırsan nasıl seçileceklerini anlatan ilgili yazılar da çıkıyor
    • Başlığı dikkat çekici yapmak için kod satırı sayısını olabildiğince düşük tutmak gerekiyordu ;)
      Şaka bir yana, normalde dokümantasyon ve kodun birlikte olmasının daha iyi olduğuna katılıyorum. Ama bu durumda bu bir eğitim projesi, bu yüzden kodla dokümantasyonu ayırıp blog yazısında kodu belgelemeyi seçtim
    • Mobildeyim, o yüzden ayrıntılı bakamıyorum ama k1 ve b, TF-IDF veya BM25’te kullanılan standart ağırlık değerleri; burada da BM25 tarafındalar
      Yorumlar faydalı olurdu ama bu probleme aşina biri için hemen tanınabilecek isimler bunlar
    • k1 ve b, BM25 sıralama fonksiyonunun ayar parametreleri. Orijinal yazının yazarının uydurduğu isimler değil; neredeyse tüm uygulama ve ders kitaplarında bu değişken adları kullanılır
      Bilgi erişimi alanını bilen birinin anlaması için aslında onlara k1 ve b demek daha doğru: https://en.wikipedia.org/wiki/Okapi_BM25
    • a: float gibi örnekleri görünce hep Rich Hickey’nin “ihtiyacınız olan şey tipler değil, doğru isimlerdir” konuşması aklıma geliyor
      Go’dan gelmiş gibi duran, açıklamasız tek harfli değişken adları kullanma ve tip sistemini isimlendirmeye yardımcı bir araç gibi kötüye kullanma eğiliminden gerçekten nefret ediyorum. İsimler, programın ne yaptığına dair anlamsal bilgi taşıyabilir; o yüzden düzgün kullanılmaları gerekir

  • Dış bağımlılıklar kullanırken toplam \r\n sayısı yerine kod satırı sayısıyla övünmenin ne anlamı var, bilmiyorum
    Kod tabanını ölçmek için SI birimi yok ama bilişsel yükün bir şekilde ölçülmesi gerektiğini düşünüyorum

    • Resmî bir ölçüt değil ama ekibimiz bazen https://grugbrain.dev’e atıfla “bu kod grug değil” ya da “bu kod bayağı grug” diyor
    • 80 satırlık arama motorunun kendisi dış bağımlılık kullanmıyor. Yalnızca collections, math, string içe aktarılıyor ve hepsi standart kütüphane
      Ama daha doğrusu buna bir “arama motoru motoru” demek gerekebilir. Tarayıcı ve arayüz o 80 satıra dahil değil ama bir şekilde gerekli ve sunulan uygulama bunlar yüzünden satır sayısını ve kütüphane sayısını epey artırıyor. Yine de bu kütüphaneler arama motorunun kendisiyle ilgili değil. pandas veya fastapi gibi genel bağımlılıkları saymaya başlarsan, işletim sisteminin milyonlarca satırını, ağ kartı firmware’ini ve donanım karmaşıklığını da sayman gerekebilir
    • Bunun 80 satırda yapılabilmesini sağlayan endüstriyel birikimi kutlamamak için bir neden var mı?
    • Burada bir anlamı var. “Python ile 4000 satırda yapılmış arama motoru” olsaydı çoğu kişi geçip giderdi ama 80 satır olunca bakmaya değer kadar kısa oluyor
    • Eski usul yöntemlerden biri çevrimsel karmaşıklık

  • Hoşuma gitti. Arama motoruyla birlikte kullanılabilecek 20 satırdan kısa bir öneri motoru da mümkün. Tıklanan URL’lerin oturum günlüklerini tutarsan, her oturumda mevcut URL’den sonraki sliding window’a bakıp yakın bağlantılara daha yüksek ağırlık vererek bir öneri listesi oluşturabilirsin
    Öneri sonuçlarını sıralayıp yalnızca en üstteki N tanesini bırakırsan, belirli bir URL için önerilen URL’ler listesi elde edersin. Biraz kurcalarsan, girilen arama sorgularını ve tıklanan URL’leri günlüğe karıştırıp yazım önerileri de çıkarabilirsin

  • Çok hoş ve öğretici. Yalnız bunu deploy etmeyin :-)
    Eskiden benzer bir şeye ihtiyacım olmuştu ama ölçek biraz daha büyüktü; on binlerce belge vardı ve cevap her zamanki gibi sqlite olmuştu. Yapısal olarak buradakiyle aynı, ama ters indeks kalıcılık katmanını benim yerime başka biri yazmıştı

    • SQLite FTS'i neredeyse her yerde kullanıyorum ve beni bir kez bile hayal kırıklığına uğratmadı
    • Hatta gerçekten aynı formül bile var. Bu yorum sayesinde “anlayış ürpertisi” gibi bir şey yaşadım

  • Google, "search engine" gibi çift tırnakla arama yaptığınızda yalnızca bu iki kelimenin o sırayla geçtiği sonuçları gösterir
    En azından bazı durumlarda öyle, ama ne yazık ki her zaman değil. İleri düzey kullanıcıların istediği şey “web için grep”, “Google'ın size göstermek istediğini söylemesi” değil

    • “Web için grep”i gerçekten isteyen insan sayısının çok az olduğuna bahse girebilirim. Çok küçük bir sorgu genişletmesi yapan bir arama motoruyla kıyaslandığında bile web için grep açıkça daha kötüdür
      Google'ın sorguyu yorumlarken fazla özgür davranması doğru, ama herhangi bir arama motorunun hiç yapmamasındansa kesinlikle daha iyi olan birçok işlem var. Bugünkü Google aramanın sorunu, sonuçların neden öyle çıktığını kestirmenin zor olması; bunun da string karşılaştırmasında embedding'lere fazla dayanmasından kaynaklandığı anlaşılıyor. "cat food" ifadesinin "dog restaurant" ile eşleşmesi gibi, embedding uzayında anlamsal olarak yakın ama insan muhakemesiyle örtüşmeyen sonuçlar çıktığında insanı gerçekten yoruyor

  • Dış kütüphaneler olan feedparser, bs4 vb. kullanırken buna 80 satır kod demek bence adil değil

    • elasticsearch üstüne yapılmış olsaydı katılırdım, ama gerçek arama motoru kısmı o 80 satırda uygulanmışsa bunun adil olduğunu düşünüyorum. İçeri aktarılan kütüphaneler zaten genelde elle yeniden yazılmaması gereken türden
      Bazen “kendi arama motorumu yapmak” diye yazılan bir yazı aslında searxng ya da yacy kurulum rehberi çıkıyor; bu ise öyle bir durum değil
    • Eğer bu bağımlılıklar çok yaygın ve ana akımsa, bence sorun yok

  • Güzel. Buraya bulanık arama özelliği eklemek de çok zor görünmüyor. Örneğin "hackrnew" aramasının "hackernews" ile eşleşmesini sağlamak için, önek düzenleme mesafesi belli bir eşik altında olan sonuçları bulabilirsiniz
    Temel fikir, bir ek ters indeks daha tutmak; burada anahtarlar belge koleksiyonundaki kelimelerin n-gramlarıdır (genellikle 3-gram), posting'ler ise bu n-gramın geçtiği kelimeler ya da kelime kimlikleridir. PED(x, y) <= delta ise |N(x) ∩ N(y)| >= |N(x)| - n ∙ delta yardımcı teoremi kullanılabilir. Girdi x'in n-gramlarını hesaplayıp her n-gram için posting'leri alır ve tekrarları birleştirirseniz, her aday kelime y ile paylaşılan n-gram sayısını elde edersiniz. Bu sayı eşikten büyükse ancak o zaman gerçek PED hesaplanır; küçükse atlanır, böylece pahalı hesaplama büyük ölçüde azaltılır
    Sonra bu şekilde elde edilen kelime listesini mevcut indekste sorgularsınız. Eskiden https://dont.watch/ üzerinde istemci taraflı bir JS bulanık arama motoru yaparken bu yaklaşımı kullanmıştım. JS koduna bakarsanız ters indeksin ve sıkıştırılmış n-gram indeksinin doğrudan JS dosyası olarak gönderildiğini görebilirsiniz. Gerçek arama motoru, dış bağımlılık olmadan yaklaşık 300 satır JS'ten oluşuyor ve yalnızca arama sonuçlarını iyileştirmeye yönelik çok temel sezgiseller içeriyor

    • O yöntemde indeks boyutu ne kadar artıyor?