Blogu' lu' Yeti idei trăznite, experienţe nebanale şi păreri subiective

News Search Engine / Proiect CI

CI este singura materie de an 5 pe care o fac toţi studenţii, indiferent de specializare (though, în funcţie de ce specializare ai, ai un alt profesor). Presupun materia asta are numele pe care îl are ca să ofere flexibilitate şcolii în a pune acolo conţinutul pentru care are profesori la un moment dat, but this is just a wild guess. Motivul care mă face să zic asta este că materia se ocupă cu Information Retrieval, şi numele ei n-are-a face cu asta.

Anyway, întâmplarea fericită a făcut ca specializările C1 şi C2 (eu sunt la C1) să îl aibă ca profesor pe first-time appeareance Paul Chiriţă, care e un meseriaş în domeniu şi care a lucrat pe la tot soiu de meseriaşi (like Yahoo) şi care acum s-a întors în Bucureşti şi lucrează la Adobe. Anyway, cursu a fost interesant, am şi reuşit să merg la câteva, dar era lunea, la 8, în Leu, ceea ce nu este prea compatibil cu mine :).

Am ales, împreună cu Gia, Micvs şi Miki să alegem calea interesantă şi să facem un proiect (alternativa era un referat). Evident, materia a început în octombrie, noi am aproximativ ales tema prin noiembrie şi am avut prima întâlnire pe 17 decembrie, cand deadline-ul era 12 ianuarie. Tema pe care ne-am ales-o a fost un news search engine, adică partea de crawl (spidering), partea de indexare, partea de gestiune a queryurilor, şi chiar şi o interfaţă de test.

Contribuţia mea la proiect nu a fost atât de mare pe cât mi-aş fi dorit, şi am ajuns la Bucureşti la aproape o săptămână dupa ce Micvs şi Gia s-or apucat deja de treabă, dar totuşi sper ca am ajutat :).

So, un pic despre proiectul nostru: ne-am propus sa re-inventăm roata ca să ne dăm seama cam cum era făcută, aşa că părţile esenţiale le-am facut de la 0. Motorul nostru de căutare de ştiri este scris în Java, şi foloseşte RMI între diferitele module (web-crawler, indexer, clienţi) şi JDBC cu baza de date în care menţinem un cache. Practic, ce ne-am pornit la drum să facem a fost o reinventare a roţii (sau, ca să citez din ceva ce-am citit pe net: ce rost are să te apuci să reinventezi roata, hai să reinventăm motorul - de căutare :P).

Crawlerul nostru este antrenat acum pe două site-uri: bbc.co.uk şi theguardian.co.uk. Am mers pe conţinut în engleză pentru că e mai uşor de găsit, mai corect format şi stufos decât ce găseam în română, dar mai ales pentru că anumite componente ale unui SE (stemming, spre exemplu) funcţionează ca în teorie când le aplici pe limba engleză. Practic, un "spider" porneşte de la site-ul principal, şi găseşte link-uri către categoriile principale ale site-ului, de unde obţine linkuri către ştiri. Se extrage textul şi titlul ştirii din pagină (cu o expresie regulată, pentru fiecare site), şi se trimite, printr-un apel RMI, server-ului de indexare. După ce termină toate linkurile, se semnalizează server-ului că s-a încheiat parcurgerea site-urilor şi crawler-ul este apelat din nou după câteva ore.

Server-ul de indexare întreţine, evident :), un inverted index. Index-ul este reprezentat în memorie ca un hashtable, în care cheile sunt hashuri (int) ale cuvintelor trecute printr-un stemmer simplu de limbă engleză, şi valorile sunt liste înlănţuite de referinţe la documente şi un vector de apariţii (poziţii în document în care apare cuvântul respectiv). De fapt, se menţine câte un vector de apariţii pentru titlu, conţinut şi sumar.

În timp ce primeşte toate ştirile dintr-o "transmisie", serverul foloseşte un pachet numit classifier4j pentru a calcula asemănările între două texte pe care le primeşte. Dacă asemănările sunt prea mari ( > 95%), ştirea este considerată duplicată şi se ignoră. Dacă ştirea seamănă în proporţie > 80% cu un text, se consideră ca este despre acelaşi eveniment sau aceeaşi serie de evenimente ca şi ştirea cu care este comparată, astfel făcându-se clustering bazat pe evenimente. Comparaţia se face folosind un motor care se foloseşte de teorema cosinusului într-un vector space de cuvinte (classifier4j mai poate folosi un comparator bazat pe teorema lui bayes, dar nu ştiam despre ce era vorba şi era mai complicat de folosit pentru ce voiam noi). La indexing-time se mai calculează şi un sumar static al textului, reprezentat din cele mai importante două propoziţii din text (calculate şi ele folosind un algoritm bazat pe teorema cosinusului aplicată pe spaţiul documentului respectiv). La fiecare indexare, cache-ul este înlocuit (în mod sincronizat) cu cache-ul nou.

Aspectul la care micvs a insistat la construirea indexului a fost performanţa: parsări minime ( = 1) a oricărei liste, oricărui string, şi optimizări pentru tratare de queryuri, în detrimentul performanţei indexării, dacă a fost cazul.

Pentru tratarea query-urilor, server-ul primeşte de la aplicaţiile client o listă de cuvinte cheie, printr-un apel RMI. Serverul foloseşte inverted index-ul pentru a găsi documentele care conţin cuvintele respective, şi aceste liste sunt apoi intersectate. Fiecare document primeşte o notă, la query-time, bazată pe numărul de apariţii a cuvântului în textul documentului şi pe existenţa sau absenţa cuvântului căutat în titlu şi în sumarul documentului. Dacă căutarea se face după mai multe cuvinte, nota se acordă şi în funcţie de apropierea în cadrul documentului între cuvinte (adică e mai relevant un document care contine termenii de căutare mai apropiaţi - în special unul lângă celălalt).

Pentru prezentare, miki a lucrat la o interfaţă în java, aşa, de POC (proof of concept) ca să putem să arătăm cum se obţin rezultatele şi cum se grupează. Pe mine m-a ros nonstop faptu că nu am făcut ceva webbased pentru căutare, că pentru mine făcea mai mult sens să fie webbased, aşa că, după predarea proiectului, m-am jucat un pic, pentru prima dată ever cu nişte Servlet-uri. Promit că dacă o să chiar termin ceva o să le pun la mine pe site să le poată testa cine vrea :).

Oricum, a fost un proiect instructiv, şi, pe cât îmi displace mie Java, trebuie să recunosc că munca în echipă e mult mai clar definită când se programează în limbaje gen Java. Proiectul ăsta a fost şi primul proiect la care am reuşit să-i conving pe ceilalţi să folosim SVN pentru controlul codului, ceea ce pentru mine a fost o reuşită personală.

Partea mai puţin reuşită a fost prezentarea efectivă a proiectului, unde am mers direct după o noapte nedormită cu o prezentare încropită şi un proiect semi-finalizat. M-am bâlbâit nonstop la prezentare, şi când i s-o terminat la Gia bateria de la laptopu de pe care prezentam I froze. Evident, se pare că prezentările astea erau oarecum mai puţin colegiale şi mai mult "oficiale" aşa ca mi-am luat bobârnacu necesar peste nas, dar îl meritam pentru că am mers, într-adevăr nepregătit pentru o prezentare.