Wednesday 14 January 2009
Tuesday 13 January 2009
usor off topic, despre indexare
Unul din obiectivele avute in vedere in realizarea unei interfete este crearea unui timp de raspuns cat mai bun. Usor off topic pentru ca nu e "ce se vede", indirect relevant insa.
Indexarea e modalitatea de a stoca informatie intr-un mod organizat, principalul obiectiv fiind extragerea informatiilor din index intr-un timp optimal. Unde se foloseste ? Peste tot ! Google news de ex. De bun simt e ca daca ai multe cautari de stiri, nu stai sa crawlezi tot netul pentru fiecare cautare, e mai "cinstit" sa faci asta o singura data, informatiile sa le pastrezi cumva structurat, diminuand extrem de mult timpul de cautare.
Cum ar trebui sa arate un index ? Depinde extrem de mult de modalitatea de cautare a informatiei. Exista mai multe tipuri de cautare (de ex keywords, fraza, cautare booleana, cautare cu expresii regulate, etc), stabilirea modului de cautare influentand structura indexului. In general indexul ca structura de date e un Hashtable, key fiind cuvantul, value fiind un obiect ce ar trebui sa descrie dependintele intre acel cuvant si toate documentele in care apare, pozitiile in care apare in fiecare doc, etc. Acest value e influentat de modalitatea de cautare.
In general intr-un index nu sunt tinute valori de tip text. Pentru optimizare la comparare, se folosesc hashcode-uri, cautarea pe int-uri fiind mult mai eficienta. Cuvintele care sunt indexate sufera o serie de prelucrari. Se aplica algoritmi de eliminare caractere nerelevante(".", ",", ";", etc.), eliminare de stop words, stemming, lemmatisation, etc. Stringul rezultat va fi codificat la int si retinut in index. Algoritmii prezentati reduc dimensiunea textului ce trebuie indexat la ceva considerat "relevant". De exemplu, regula celor 30 spune ca din 30% din cuvintele cu cele mai multe aparitii dintr-un document, 30% sunt cuvinte cheie (stop words), cuvinte cu relevanta mica la cautare.
De asemeni, pe partea de value in hashtable pot fi mai multe abordari. Documente sunt tinute fie sub forma de liste, obligatoriu sortate, pentru ca la cautarea a 2 cuvinte de ex, rezultatul ar trebui sa fie intersectia listelor de documente in care apare fiecare cuvant, intersectia pe 2 liste sortate facandu-se in O(m+n) fata de O(m*n) pentru liste nesortate. Tradeoff pentru listele sortate e dificultatea la adaugare si stergere, listele trebuie resortate dupa fiecare operatie de acest fel. O alta varianta ar fi folosirea unor arbori (binari de cautare, rosu-negru, etc.), adaugarea si eliminarea unei intrari rebalansand arborele, iar cautarea facandu-se rapid. Mai greu de implementat si cu mai multe resurse in memorie.
usor off topic, dar sper interesant :)
Indexarea e modalitatea de a stoca informatie intr-un mod organizat, principalul obiectiv fiind extragerea informatiilor din index intr-un timp optimal. Unde se foloseste ? Peste tot ! Google news de ex. De bun simt e ca daca ai multe cautari de stiri, nu stai sa crawlezi tot netul pentru fiecare cautare, e mai "cinstit" sa faci asta o singura data, informatiile sa le pastrezi cumva structurat, diminuand extrem de mult timpul de cautare.
Cum ar trebui sa arate un index ? Depinde extrem de mult de modalitatea de cautare a informatiei. Exista mai multe tipuri de cautare (de ex keywords, fraza, cautare booleana, cautare cu expresii regulate, etc), stabilirea modului de cautare influentand structura indexului. In general indexul ca structura de date e un Hashtable, key fiind cuvantul, value fiind un obiect ce ar trebui sa descrie dependintele intre acel cuvant si toate documentele in care apare, pozitiile in care apare in fiecare doc, etc. Acest value e influentat de modalitatea de cautare.
In general intr-un index nu sunt tinute valori de tip text. Pentru optimizare la comparare, se folosesc hashcode-uri, cautarea pe int-uri fiind mult mai eficienta. Cuvintele care sunt indexate sufera o serie de prelucrari. Se aplica algoritmi de eliminare caractere nerelevante(".", ",", ";", etc.), eliminare de stop words, stemming, lemmatisation, etc. Stringul rezultat va fi codificat la int si retinut in index. Algoritmii prezentati reduc dimensiunea textului ce trebuie indexat la ceva considerat "relevant". De exemplu, regula celor 30 spune ca din 30% din cuvintele cu cele mai multe aparitii dintr-un document, 30% sunt cuvinte cheie (stop words), cuvinte cu relevanta mica la cautare.
De asemeni, pe partea de value in hashtable pot fi mai multe abordari. Documente sunt tinute fie sub forma de liste, obligatoriu sortate, pentru ca la cautarea a 2 cuvinte de ex, rezultatul ar trebui sa fie intersectia listelor de documente in care apare fiecare cuvant, intersectia pe 2 liste sortate facandu-se in O(m+n) fata de O(m*n) pentru liste nesortate. Tradeoff pentru listele sortate e dificultatea la adaugare si stergere, listele trebuie resortate dupa fiecare operatie de acest fel. O alta varianta ar fi folosirea unor arbori (binari de cautare, rosu-negru, etc.), adaugarea si eliminarea unei intrari rebalansand arborele, iar cautarea facandu-se rapid. Mai greu de implementat si cu mai multe resurse in memorie.
usor off topic, dar sper interesant :)
A few insights on Web pay-per-click advertising
Pentru inceput as vrea sa mentionez ca ideea articolului a aparut ca urmare a citirii documentatiei necesare pentru realizarea referatului de la Complemente de Informatica. Aceasta trata, printre altele, si cateva probleme de securitate legate de web advertising, in special cele care afecteaza tehnicile de "click through payment"(pay-per-click), astazi una dintre cele mai raspandite metode de realizare a publicitatii pe Internet.
Pentru cei care nu stiu inca in ce consta metoda (inainte de citirea articolului si eu ma numaram printre ei :)) o sa incerc sa le ofer o explicatie succinta. In linii mari, totul arata cam asa: administratorul unui site T (target site) accepa sa plateasca un alt site R, care ii face publicitate, cu o anumita suma de bani direct proportionala cu numarul de click-uri pe care utilizatorii care intra pe site-ul R il dau pe bannerele publicitare care ii redirecteaza catre T. Prin urmare, "gsp.ro" primeste bani de fiecare data cand tu dai click pe bannerul care te anunta de ultima oferta de la Orange sau de existenta unui showroom now in Bucuresti.
Si aici intervine partea interesanta! Studiile au aratat ca in general, rata click-urilor pentru bannere publicitare este una foarte mica, de doar 1-3%. Pana la urma tu ai vrut sa afli ce a facut Steaua la ultimul meci si nu te intereseaza sa-ti cumperi o combina frigorifica chiar daca aceasta este la incredibilul pret de XXX RON!! Rata fiind atat de mica, si pretul pentru fiecare click este calculat in consecinta. De aceea R este interesat sa produca cat mai multe cereri catre T pentru a-si imbunatati click-rate-ul si poate incerca sa realizeze acest lucru si prin metode mai putin "cinstite".
Cea mai simpla abordare ar fi ca administratorul lui R sa ruleze un program care emite periodic cereri catre T sub forma unui click fictiv. Ideea este insa ineficienta, deoarece, in cele mai multe cazuri administratorul lui T va stipula in contract o clauza conform careia alege sa plateasca doar pentru cereri cu IP-uri unice. Bineinteles, un atacator mai sofisticat poate incerca sa pacaleasca sistemul si de data aceasta, generand cereri cu IP-uri diferite. Metoda presupune un efort suplimentar, este mai dificil de implementat si de cele mai multe ori poate fi detectatata usor de catre T. Si asta deoarece, in majoritatea cazurilor nu va exista nici un browser la celalalt capat al conexiunii care sa primeasca raspunsul lui T. Administratorul lui R nu este interesat de continutul paginii "pageT.html". Iar daca aceasta contine si link-uri catre imagini sau alte elemente HTML, link-uri pe care un browser web le-ar interpreta in consecinta, atunci o cerere pentru "pageT.html" nu va mai fi urmata si de o alta cerere pentru elementele HTML continute in aceasta. Prin urmare, administratorul lui T poate afla daca cererea este sau nu valida si poate lua masuri.
Din aceasta cauza, poate una dintre cele mai utilizate metode de "pacalire" a site-ului target folosite azi este aceea de obligare a user-ului sa aceseze "pageT.html" prin realizarea unei pagini "pageR.html" care sa creasca click-count-ul de fiecare data cand un nou utilizator ajunge aici. In plus, intregul proces poate fi ascuns utilizatorului, care nu va afla niciodata ca este folosit de R pentru a obtine recompense financiare de la T. Dar, chiar daca atacurile sunt sau nu vizibile utilizatorului, si acestea pot fi depistate de administratorul lui T daca acesta hotaraste sa-si inspecteze colaboratorii. Daca admin-ul lui T intra pe site-ul lui R el va descoperii frauda si poate actiona in consecina, rupand contractul cu R pentru a-si cauta un partener mai serios.
Si acum, pentru ca am salvat ce este mai bun pentru final, pot sa afirm ca exista si o metoda de generare a click-urilor fictive care este imposibil de detectat de catre administratorul site-ului target. Metoda presupune existenta unui site suplimentar S cu care R sa colaboreze. Procedeul este simplu si inglobeaza 2 click-uri simulate: in momentul in care un utilizator face o cerere pentru "pageS.html" , S trimite un click fictiv catre R care la randul sau va genera un click pe baza celui primi de la S pe care il trimite lui T. Ultimul click are menirea de a-l pacali pe acesta din urma facandu-l sa creada ca S este sursa cereri => metoda de generare este destul de complicata, dar realizabila. In plus, atacul are si "avantajul" ca face site-urile target susceptibile la "spamming" indirect (daca prin contract R este obligat sa nu foloseasca spamming-ul pentru a-si mari click-count-ul, acum o poate face mascat, prin intermediul lui S. Administratorul lui T nu poate sa demonstreze ca exista o legatura intre S si R si prin urmare nu-l poate acuza pe R de practici necinstite).
Totusi, atacul are si unele "dezavantaje": este complet nefolositor in cazul advertising-ului de tip pay-per-sale (utilizatorul trebuie sa si achizitioneze unul din item-urile expuse la vanzare pe site-ul target) sau pay-per-lead ((utilizatorul trebuie sa aiba activitate suplimentara pe pagina pentru ca click-ul sa fie validat). Si avand in vedere ca siguranta advertisementului de tip pay-per-click poate fi sparta foarte usor, tot mai multi utilizatori isi indreapta atentia catre celelalte 2 metode de publicitate ...
Pentru cei care nu stiu inca in ce consta metoda (inainte de citirea articolului si eu ma numaram printre ei :)) o sa incerc sa le ofer o explicatie succinta. In linii mari, totul arata cam asa: administratorul unui site T (target site) accepa sa plateasca un alt site R, care ii face publicitate, cu o anumita suma de bani direct proportionala cu numarul de click-uri pe care utilizatorii care intra pe site-ul R il dau pe bannerele publicitare care ii redirecteaza catre T. Prin urmare, "gsp.ro" primeste bani de fiecare data cand tu dai click pe bannerul care te anunta de ultima oferta de la Orange sau de existenta unui showroom now in Bucuresti.
Si aici intervine partea interesanta! Studiile au aratat ca in general, rata click-urilor pentru bannere publicitare este una foarte mica, de doar 1-3%. Pana la urma tu ai vrut sa afli ce a facut Steaua la ultimul meci si nu te intereseaza sa-ti cumperi o combina frigorifica chiar daca aceasta este la incredibilul pret de XXX RON!! Rata fiind atat de mica, si pretul pentru fiecare click este calculat in consecinta. De aceea R este interesat sa produca cat mai multe cereri catre T pentru a-si imbunatati click-rate-ul si poate incerca sa realizeze acest lucru si prin metode mai putin "cinstite".
Cea mai simpla abordare ar fi ca administratorul lui R sa ruleze un program care emite periodic cereri catre T sub forma unui click fictiv. Ideea este insa ineficienta, deoarece, in cele mai multe cazuri administratorul lui T va stipula in contract o clauza conform careia alege sa plateasca doar pentru cereri cu IP-uri unice. Bineinteles, un atacator mai sofisticat poate incerca sa pacaleasca sistemul si de data aceasta, generand cereri cu IP-uri diferite. Metoda presupune un efort suplimentar, este mai dificil de implementat si de cele mai multe ori poate fi detectatata usor de catre T. Si asta deoarece, in majoritatea cazurilor nu va exista nici un browser la celalalt capat al conexiunii care sa primeasca raspunsul lui T. Administratorul lui R nu este interesat de continutul paginii "pageT.html". Iar daca aceasta contine si link-uri catre imagini sau alte elemente HTML, link-uri pe care un browser web le-ar interpreta in consecinta, atunci o cerere pentru "pageT.html" nu va mai fi urmata si de o alta cerere pentru elementele HTML continute in aceasta. Prin urmare, administratorul lui T poate afla daca cererea este sau nu valida si poate lua masuri.
Din aceasta cauza, poate una dintre cele mai utilizate metode de "pacalire" a site-ului target folosite azi este aceea de obligare a user-ului sa aceseze "pageT.html" prin realizarea unei pagini "pageR.html" care sa creasca click-count-ul de fiecare data cand un nou utilizator ajunge aici. In plus, intregul proces poate fi ascuns utilizatorului, care nu va afla niciodata ca este folosit de R pentru a obtine recompense financiare de la T. Dar, chiar daca atacurile sunt sau nu vizibile utilizatorului, si acestea pot fi depistate de administratorul lui T daca acesta hotaraste sa-si inspecteze colaboratorii. Daca admin-ul lui T intra pe site-ul lui R el va descoperii frauda si poate actiona in consecina, rupand contractul cu R pentru a-si cauta un partener mai serios.
Si acum, pentru ca am salvat ce este mai bun pentru final, pot sa afirm ca exista si o metoda de generare a click-urilor fictive care este imposibil de detectat de catre administratorul site-ului target. Metoda presupune existenta unui site suplimentar S cu care R sa colaboreze. Procedeul este simplu si inglobeaza 2 click-uri simulate: in momentul in care un utilizator face o cerere pentru "pageS.html" , S trimite un click fictiv catre R care la randul sau va genera un click pe baza celui primi de la S pe care il trimite lui T. Ultimul click are menirea de a-l pacali pe acesta din urma facandu-l sa creada ca S este sursa cereri => metoda de generare este destul de complicata, dar realizabila. In plus, atacul are si "avantajul" ca face site-urile target susceptibile la "spamming" indirect (daca prin contract R este obligat sa nu foloseasca spamming-ul pentru a-si mari click-count-ul, acum o poate face mascat, prin intermediul lui S. Administratorul lui T nu poate sa demonstreze ca exista o legatura intre S si R si prin urmare nu-l poate acuza pe R de practici necinstite).
Totusi, atacul are si unele "dezavantaje": este complet nefolositor in cazul advertising-ului de tip pay-per-sale (utilizatorul trebuie sa si achizitioneze unul din item-urile expuse la vanzare pe site-ul target) sau pay-per-lead ((utilizatorul trebuie sa aiba activitate suplimentara pe pagina pentru ca click-ul sa fie validat). Si avand in vedere ca siguranta advertisementului de tip pay-per-click poate fi sparta foarte usor, tot mai multi utilizatori isi indreapta atentia catre celelalte 2 metode de publicitate ...
Monday 12 January 2009
Cate ceva despre web crawling
Ultimul proiect la care am lucrat presupunea realizarea unei aplicatii care sa permita "cautare de stiri". Mai precis: trebuia facuta o aplicatie care sa adune stirile de pe anumite site-uri specializate ( noi am ales BBC Online si The Guardian ), sa le indexeze si apoi sa permita cautarea de stiri care sa contina anumite cuvinte cheie. Pe langa lucrurile astea de baza, aplicatia noastra facea si sumarizarea unei stiri si impartirea stirilor in categorii ( nu erau categorii prestabilite, ci in functie de gradul de asemanare al stirilor erau considerate a fi pe aceeasi tema-tratand acelasi eveniment- sau independente una de cealalta) - dar deja intru in alta poveste.
Partea care mi-a revenit mie a fost cea de crawl-are a paginilor de stiri si de extragere a a link-urilor stirilor si apoi de obtinere a continutului stirii ( eliminand tot ce nu tinea de stirea in format text - filmulete, poze, link-uri catre alte stiri, mesaje publicitare etc): de aceea am ales drept topic al acestui articol crawl-area pe internet.
O definitie pe care o puteti gasi pe wikipedia zice ca web crawler-ul este o aplicatie care face cautari in lumea WWW intr-o maniera automata pentru a aduna un anumit tip de informatie - actiunea in sine poarta denumirea de web crawling sau spidering. Site-uri care utilizeaza crawl-area pe internet sunt in special motoarele de cautare precum google. Evident, crawl-area in sine nu prea este utila daca nu se face ceva cu informatia adunata, cel mai adesea ea fiind indexata pentru a putea fi accesata intr-o maniera eficienta mai tarziu.Crawl-area este folosita si in spam-uirea utilizatorilor: pentru a aduna adrese de e-mail pe care vor fi trimise apoi tot felul de mesaje publicitare, de promovare a diverse site-uri sau produse ( chestiile din e-mail pe care multi dintre noi le sterg instant).
Cum functioneaza un Crawler?
Principial, trebuie sa existe un link sau o lista de link-uri de la care sa se plece: paginile asociate vor fi parsate, prelucrate si se vor extrage de aici anumite informatii, dar si link-urile care ne pot duce catre alte site-uri care sa fie prelucrate in aceeasi maniera - daca se doreste o crawl-are in adancime, altfel se poate rezuma totul la prelucrarea paginii principale. In cazul nostru s-a plecat de la 2 site-uri de stiri si s-au adunat continuturile stirilor - titlu + text, dar se pot extrage adrese de e-mail , preturile anumitor produse, review-urile unor filme - depinde de scopul aplicatiei + paginile din site unde putem gasi link-uri catre alte stiri. Am gasit un articol de la sun unde se spune ca de obicei crawler-ele ruleaza pe o singura masina si sunt mai putin inteligente decat virusii spre exemplu: un crawler pur si simplu trimite o cerere http pentru a obtine informatii de pe alte masini din Internet - la fel cum fac browser-ele web atunci cand introducem adresa unei pagini.
Lucrurile par nu foarte complicate, dar sunt anumite aspecte asupra carora ar trebui sa se insiste:
Partea care mi-a revenit mie a fost cea de crawl-are a paginilor de stiri si de extragere a a link-urilor stirilor si apoi de obtinere a continutului stirii ( eliminand tot ce nu tinea de stirea in format text - filmulete, poze, link-uri catre alte stiri, mesaje publicitare etc): de aceea am ales drept topic al acestui articol crawl-area pe internet.
O definitie pe care o puteti gasi pe wikipedia zice ca web crawler-ul este o aplicatie care face cautari in lumea WWW intr-o maniera automata pentru a aduna un anumit tip de informatie - actiunea in sine poarta denumirea de web crawling sau spidering. Site-uri care utilizeaza crawl-area pe internet sunt in special motoarele de cautare precum google. Evident, crawl-area in sine nu prea este utila daca nu se face ceva cu informatia adunata, cel mai adesea ea fiind indexata pentru a putea fi accesata intr-o maniera eficienta mai tarziu.Crawl-area este folosita si in spam-uirea utilizatorilor: pentru a aduna adrese de e-mail pe care vor fi trimise apoi tot felul de mesaje publicitare, de promovare a diverse site-uri sau produse ( chestiile din e-mail pe care multi dintre noi le sterg instant).
Cum functioneaza un Crawler?
Principial, trebuie sa existe un link sau o lista de link-uri de la care sa se plece: paginile asociate vor fi parsate, prelucrate si se vor extrage de aici anumite informatii, dar si link-urile care ne pot duce catre alte site-uri care sa fie prelucrate in aceeasi maniera - daca se doreste o crawl-are in adancime, altfel se poate rezuma totul la prelucrarea paginii principale. In cazul nostru s-a plecat de la 2 site-uri de stiri si s-au adunat continuturile stirilor - titlu + text, dar se pot extrage adrese de e-mail , preturile anumitor produse, review-urile unor filme - depinde de scopul aplicatiei + paginile din site unde putem gasi link-uri catre alte stiri. Am gasit un articol de la sun unde se spune ca de obicei crawler-ele ruleaza pe o singura masina si sunt mai putin inteligente decat virusii spre exemplu: un crawler pur si simplu trimite o cerere http pentru a obtine informatii de pe alte masini din Internet - la fel cum fac browser-ele web atunci cand introducem adresa unei pagini.
Lucrurile par nu foarte complicate, dar sunt anumite aspecte asupra carora ar trebui sa se insiste:
- trebuie sa existe o politica de selectionare a informatiei ce prezinta interes;
- pe de alta parte internet-ul este intr-o continua schimbare si ceea ce gasesti astazi pe o pagina se poate schimba in urmatoarea zi in mod considerabil( iar stirile pot fi updatate la fiecare ora sau la un interval relativ mic de timp) - trebuie stabilite niste criterii pentru recrawl-are;
- crawler-ul trebuie sa fie "politicos" si sa tina cont de anumite aspecte cum ar fi ca un anumit site nu poate primi mai mult de 1000 de cereri HTTP de la acelasi IP intr-un intervar de 30 secunde sau ca este indicat sa nu fie adunate informatii de pe anumite pagini - chestiile astea sunt mentionate in fisierul robots.txt ( mai multe detalii aici).
Subscribe to:
Posts (Atom)