p , ≤p , ≥p jako lexikografick´e ˇrazen´ı prefix˚ uop prvc´ıch. Pokud chceme vyhledat vˇsechny instance ˇretˇezce W = w0 , . . . , wp−1 v A, kde p ≤ N , pak provedeme n´ asleduj´ıc´ı: Necht’ LW = min(k : W ≤p AP os[k] or k = N ) a RW = max(k : AP os[k] ≤p W or k = −1). D´ıky tomu, ˇze naˇse pole W je lexikograficky seˇrazen´e, plat´ı, ˇze pro kaˇzd´e i = P os[k] je k ∈ [LW , RW ]. Takˇze pokud, dok´ aˇzeme rychle naj´ıt LW a RW , pak poˇcet shodn´ ych ˇretˇezc˚ u, kter´e najdeme je RW − LW + 1 a jejich lev´e koncov´e pozice jsou d´any jako P os[LW ], . . . , P os[RW ]. Nav´ıc d´ıky ˇrazen´ı ≤p jsme schopni LW a RW naj´ıt metodou porovn´ an´ı ˇretˇezc˚ u v ˇcase O(logN ), kde kaˇzd´e porovn´an´ı vyˇzaduje O(logP ) operac´ı. T´ım p´ adem jsme schopni v poli P os vyhledat vˇsechny v´ yskyty ˇretˇezce v ˇcase O(P logN ). Nyn´ı se pod´ıv´ ame, jak se takov´e suffixov´e pole sestavuje. Vylepˇsen´ı pomoc´ı sestavov´ an´ı lcp zde rozeb´ırat nebudeme, nebot’ to nen´ı pˇredmˇetem t´eto pr´ace. ˇ Razen´ ı prob´ıh´ a v nejhorˇs´ım pˇr´ıpadˇe v log2 (N + 1) f´az´ıch. V prvn´ı f´azi seˇrad´ıme suffixy skupin podle jejich prvn´ıho symbolu. Pot´e stejn´ ym zp˚ usobem dˇel´ıme tyto skupiny podle dvojn´ asobn´eho poˇctu n´asleduj´ıc´ıch symbol˚ u. Pro zjednoduˇsen´ı 12 podˇ retˇ ezec 13 angl.
pˇripona, v textu ale nebudu pˇrekl´ adat
15
oznaˇc´ıme tyto f´ aze 1, 2, 4, 8 atd. abychom t´ım vyznaˇcili poˇcet ovlivnˇen´ ych symbol˚ u. Takˇze f´ aze H-t´ a f´ aze znaˇc´ı, ˇze jsme provedli ˇrazen´ı do stupnˇe leqH . D´ale jeˇstˇe dopn´ıme vˇsechny suffixy mezerami tak, aby jejich d´elka byla N + 1. V prvn´ı f´ azi m´ ame pole P os seˇrazeno podle prvn´ıch symbol˚ u a v dalˇs´ım poli si uchov´ av´ ame logick´e hodnoty, kter´e oznaˇcuj´ı dˇelen´ı suffix˚ u do m1 skupin. Pole P os bude st´ ale v´ıce seˇrazen´e a v H-t´e f´azi budou suffixy rozˇrazeny do mH skupin, kde v kaˇzd´e budou suffixy se stejn´ ymi H prvn´ımi symboly, a nav´ıc jsou v r´ amci kaˇzd´e skupiny suffixy seˇrazeny do stupnˇe ≤H . Podrobnˇejˇs´ıho postup pˇri tvoˇren´ı a pouˇzit´ı suffixov´ ych pol´ı se lze doˇc´ıst napˇr. v [MM90] nebo [YC01]. Hlavn´ı v´ yhodou t´eto metody je niˇzˇs´ı v´ ypoˇcetn´ı sloˇzitost iu ´spora m´ısta na disku, protoˇze nemus´ıme uchov´avat vˇsechny texty a ˇretˇezce v pol´ıch, ale staˇc´ı n´ am pouze hlavn´ı text a nˇekolik pol´ı ˇc´ısel, kter´e symbolizuj´ı ukazatele do nˇej.
2.6
ˇ alovatelnost Sk´
Pˇri masivn´ım crawlingu by se boti mˇely d´ıvat do souboru ”robots.txt”, kter´ y je um´ıstˇen v root adres´ aˇri t´emˇeˇr kaˇzd´e vˇetˇs´ı str´anky. Podle nˇeho se zjist´ı, zda m˚ uˇze b´ yt dan´ a str´ anka v˚ ubec prohled´av´ana. D´ale by se mˇelo pˇredej´ıt tomu, aby byl server zahlcen dotazy ke staˇzen´ı str´anek, coˇz se m˚ uˇze lehce st´at, pokud se k nˇemu snaˇz´ı pˇripojit velk´e mnoˇzstv´ı crawler˚ u najednou. Implementace jednoduch´e verze crawleru, kter´ y pouze stahuje a ukl´ad´a obsah str´ anek je pomˇernˇe trivi´ aln´ı. Pokud ale chceme vybudovat syst´em, kter´ y by zpracov´ aval vˇetˇs´ı mnoˇzstv´ı str´anek (jako to dˇelaj´ı napˇr. webov´e vyhled´avaˇce), m´ ame pˇred sebou nesnadn´ yu ´kol. Pr˚ umˇern´a velikost jedn´e str´anky je cca 20KB (miliarda str´ anek pak m˚ uˇze m´ıt i 20 000GB), takˇze je nutn´e cel´ y obsah ukl´adat na distribuovan´e s´ıti poˇc´ıtaˇc˚ u nebo podobn´em obrovsk´em u ´loˇziˇsti. Nejd˚ uleˇzitˇejˇs´ım u ´kolem je ale navrˇzen´ı syst´emu pro koordinaci velk´eho mnoˇzstv´ı crawler˚ u. Podrobnˇe se t´ımto t´ematem zab´ yv´a napˇr. studie z roku 2003[Bos03].
16
3
Hodnocen´ı str´ anek
V t´eto kapitole se zamˇeˇr´ıme na to, jak naloˇzit se z´ıskan´ ymi daty. Existuje mnoho zp˚ usob˚ u jak hodnotit str´anky a ˇradit je podle obsahu od nejlepˇs´ı po nejhorˇs´ı (resp. podle relevance). Zde postupnˇe pop´ıˇseme nˇekolik z nich se vˇsemi v´ yhodami a nev´ yhodami. V prvn´ı ˇradˇe je nutn´e zm´ınit, ˇze je rozd´ıl mezi pojmy data retrievel a information retrievel (IR). Pˇredpokl´adejme, ˇze uˇzivatel do vyhled´avaˇce zad´a nˇejak´ y dotaz (query). V data retrievel hled´ame v dokumentech pˇresnou shodu - to znamen´ a, ˇze ovˇeˇrujeme, zda se dan´a informace v dokumentu nach´az´ı ˇci ne. V information retrievel hled´ ame ty dokumenty, kter´e alespoˇ n ˇc´asteˇcnˇe vyhovuj´ı zadan´emu dotazu a n´ aslednˇe z nich vybereme ty s nejlepˇs´ı shodou. Dˇr´ıve pracovaly strategie IR na principu lexik´aln´ıho porovn´an´ı dotazu, kter´ y se skl´ adal z mal´eho mnoˇzstv´ı kl´ıˇcov´ ych slov (keywords), s dokumenty a jejich indexovan´ ymi slovy. Vˇetˇsina vyhled´avaˇc˚ u nyn´ı ale pracuje jeˇstˇe s hyperlinkovou strukturou dokument˚ u, coˇz je dnes s velk´ ym poˇctem webov´ ych str´anek jiˇz takˇrka nutnost´ı. Velmi dobr´ ym pˇrehledem tˇechto technik je napˇr´ıklad ˇcl´anek ze ScienceDirect od autor˚ u z ˇreck´e univerzity v Thessaloniki[AKP06].
3.1
TF-IDF
TF-IDF, neboli Term Frequency - Inverse Document Frequency, je zp˚ usob hodnocen´ı str´ anek na z´ akladˇe relevance nalezen´eho textu. N´aˇs crawler tento algoritmus implementoval formou nec´ılen´eho i c´ılen´eho vyhled´av´an´ı. Pokud tedy spust´ıme crawling session bez jak´ekoli specifikace hledan´ ych v´ yraz˚ u, spust´ı se pr´ avˇe tato forma hodnocen´ı. Idea je, ˇze str´anky, kter´e obsahuj´ı v´ıce relevantn´ıch (jakkoli) informac´ı se objev´ı nahoˇre ve v´ ysledc´ıch. TF sloˇzka vyjadˇruje, jak ˇcasto se v´ yraz vyskytuje v dokumentu z datab´aze. Vˇetˇsinou se normalizuje vydˇelen´ım d´elkou (poˇctem slov) dokumentu, aby se pˇredeˇslo nadhodnocov´ an´ı dlouh´ ych dokument˚ u, ve kter´ ych se v´ yraz m˚ uˇze vyskytovat ˇcastˇeji neˇz v kratˇs´ıch, aniˇz by byl dokument relevantnˇejˇs´ı. T´ım z´ısk´av´ame n´ asleduj´ıc´ı definici tf: tfi,j = Ni,j
(1)
kde Ni,j je poˇcet v´ yskut˚ u v´ yrazu i na str´ance j. Pˇri normalizaci se vˇetˇsinou pouˇz´ıv´ a Euklidovsk´ a norma. Idf sloˇzka reprezentuje ”d˚ uleˇzitost”slova (tento term´ın ale berme s rezervou, ˇ ım ˇcastˇeji se slovo vyskytuje v dokumentech, t´ım m´enˇe je d˚ viz d´ ale). C´ uleˇzit´e (slovo, kter´e se vyskytuje ve vˇsech dokumentech je vˇetˇsinou pro vyhled´av´an´ı nepouˇziteln´e). Idf pro slovo i spoˇc´ıt´ame podle vzorce:
17
idfi = log
N , Ni
(2)
kde N je celkov´ y poˇcet str´ anek a jmenovatel vyjadˇruje poˇcet str´anek, na kter´ ych se vyskytuje v´ yraz i. Ze vzorc˚ u14 vypl´ yv´ a, ˇze slovo, kter´e se vyskytuje na vˇsech str´ank´ach, bude m´ıt niˇzˇs´ı hodnotu IDF a tud´ıˇz bude hodnoceno m´enˇe, neˇz slovo, kter´e se vyskytuje v´ yjmeˇcnˇe. Str´ anky s vˇetˇs´ım poˇctem unik´atn´ıch v´ yraz˚ u by proto mohly obsahovat relevantnˇejˇs´ı informace, neˇz ostatn´ı, kter´e obsahuj´ı jen n´ızce hodnocen´a slova. V naˇs´ı implementaci jsme napoˇc´ıtali TF-IDF hodnotu pro vektor vˇsech slov napˇr´ıˇc prohledan´ ymi str´ ankami a to sam´e jsme udˇelali pro vektory slov na jednotliv´ ych str´ ank´ ach. Relevanci obsahu pak spoˇc´ıt´ame jako kosinovou vzd´alenost15 tˇechto vektor˚ u (tj. kosinovou vzd´alenost hodnocen´ı slov na dan´e str´ance a vektoru vˇsech nalezen´ ych slov). Pouˇzijeme vzorec: cosθ =
dq , kdkkqk
(3)
kde d je vektor TF-IDF hodnocen´e str´anky, q je vektor TF-IDF vˇsech nalezen´ ych slov. Tato metoda jde samozˇrejmˇe pouˇz´ıt i pro c´ılen´e vyhled´av´an´ı. Rating jednotliv´ ych str´ anek je d´ an souˇctem TF-IDF hodnocen´ı hledan´ ych slov, kter´e str´anka obsahuje. TF-IDF se v praxi pouˇz´ıv´a velmi ˇcasto (v r˚ uzn´ ych modifikac´ıch) spolu s page-rank algoritmy. Tento zp˚ usob hodnocen´ı str´anek (pokud je pouˇzit samostatnˇe) m´a ale ˇradu nev´ yhod. Jak jsme jiˇz uvedli, pojem ”d˚ uleˇzitost slova”je nutno br´at s rezervou. TF-IDF m´ıra pro v´ yraz i na str´ance j (ai,j = tfi,j idfi ) kombinuje dva r˚ uzn´e prostory (prostor slov v TF a prostor str´anek v IDF)16 . Pro danou hodnotu IDF je vztah ai,j a tfi,j line´arn´ı, ale slovo, kter´e se na str´ance j vyskytuje xkr´ at nemus´ı (a pravdˇepodobnˇe ani nen´ı) x-kr´at relevantnˇejˇs´ı, neˇz slovo, kter´e se na dan´e str´ ance vyskytuje jen jednou. Kdyˇz se pod´ıv´ ame na vztah IDF a TF-IDF, tak zjist´ıme, ˇze IDF tak´e nem´a ˇz´ adnou spojitost s relevanc´ı slov. Je to vlastnˇe logaritmick´ y odhad, ˇze n´ahodnˇe vybran´ a str´ anka ni z kolekce str´anek N bude obsahovat slovo i. D˚ uleˇzitost slova v dokumentu z´avis´ı na spoustˇe faktor˚ u, jako napˇr. v´ yznam, entropie (mnoˇzstv´ı informace, kterou obsahuje), ale i uˇzivatelsk´e dotazy na toto slovo. TF-IDF samo o sobˇe nezohledˇ nuje ˇz´adn´ y z tˇechto faktor˚ u. Neposledn´ı 14 Vzoreˇ cky pˇrevzat´ e z http://www.ardendertat.com/2011/07/17/how-to-implement-asearch-engine-part-3-ranking-tf-idf/ 15 Cosine distance 16 http://irthoughts.wordpress.com/2008/07/07/understanding-tfidf/
18
nev´ yhodou implementace tohoto hodnocen´ı je i v´ ypoˇcetn´ı sloˇzitost, protoˇze je nutn´e jednak sb´ırat informace o v´ yskytech slov na jednotliv´ ych str´ank´ach, ale nav´ıc jeˇstˇe po skonˇcen´ı session proj´ıt vˇsechny str´anky znovu spoˇc´ıtat IDF. I pˇresto se ale TF-IDF hojnˇe pouˇz´ıv´a (a v´ ypoˇcet kosinov´ ych podobnost´ı), protoˇze v kombinaci s dalˇs´ımi pˇr´ıstupy pˇrin´aˇs´ı velmi sluˇsn´e v´ ysledky a je st´ale m´enˇe n´ aroˇcn´e neˇz jin´e m´ıry, kter´e zohledˇ nuj´ı i modely s entropi´ı slov. Na cel´e TF-IDF by se dalo nahl´ıˇzet jako na entropii. Lze lehce ovˇeˇrit, ˇze pˇr´ıliˇs velk´ y poˇcet slov ve vektoru (kter´ y urˇcuje dimenzi prohled´avan´eho prostoru) spolu s menˇs´ım poˇctem dokument˚ u v kolekci zp˚ usob´ı, ˇze spoˇc´ıtan´e hodnocen´ı str´ anek formou kosinov´ ych vzd´alenost´ı v sobˇe neponese ˇz´adnou informaci. Stejnˇe tak pˇr´ıliˇs hustˇe zaplnˇen´ y prostor zp˚ usob´ı tento probl´em.
3.2
Latent semantic indexing (LSI)
LSI je dalˇs´ım z pˇr´ıklad˚ u text-based IR technik, kter´a pouˇz´ıv´a matematickou techniku SVD (Singular value decomposition). Ve vyhled´av´an´ı se ˇcasto pouˇz´ıv´a tzv. term-document matice A o velikosti m × n, kde ˇr´adky reprezentuj´ı v´ yskyt dan´eho slova ve vˇsech dokumentech a sloupce reprezentuj´ı jednotliv´e dokumenty. Prvek matice A na pozici ai,j je tedy vztah mezi i-t´ ym slovem a j-t´ ym dokumentem. V bin´ arn´ım modelu jsou na jednotliv´ ych pozic´ıch jedniˇcky tam, kde se slovo vyskytuje v pˇr´ısluˇsn´em dokumentu a nuly jinde. Ve vektorov´em modelu jsou vˇetˇsinou na pozic´ıch matice relativn´ı ˇcetnosti slov v dokumentech. Probl´em s pouˇzit´ım jednoduch´e formy t´eto term-document matice je, ˇze d´ıky velk´emu mnoˇzstv´ı slov ve slovn´ıku a poˇctu dokument˚ u m˚ uˇze b´ yt tato reprezentace velmi v´ ypoˇcetnˇe n´ aroˇcn´a. Je tedy v´ yhodn´e pro u ´ˇcely vyhled´av´an´ı tento prostor co nejv´ıce zredukovat. LSI nab´ız´ı moˇznost, jak identifikovat vztahy mezi jednotliv´ ymi slovy v textu a zbavit se zbyteˇcn´ ych slov, kter´a tvoˇr´ı dokument. Vych´ az´ıme z pˇredpokladu, ˇze slova, kter´a jsou pouˇzita ve stejn´ ych kontextech maj´ı vˇetˇsinou podobn´ y v´ yznam. Zmenˇsen´ı dimenze prostoru slov je dosaˇzeno pouˇzit´ım SVD rozkladu. Z´akladn´ı tvar SVD je d´ an vzorcem[AKP06]: A = U SV T ,
(4)
kde U, V jsou matice velikosti m × k0 a n × k0 s ortonorm´aln´ımi sloupci, kter´e reprezentuj´ı ortonorm´ aln´ı vlastn´ı vektory pˇr´ısluˇsn´e nenulov´ ym vlastn´ım ˇc´ısl˚ um matic AT A a AAT , rank(A) = k0 . S je diagon´aln´ı matice (velikosti k0 × k0 ), kter´ a na diagon´ ale obsahuje vlastn´ı ˇc´ısla seˇrazen´a od nejvˇetˇs´ıho po nejmenˇs´ı. My se budeme snaˇzit zredukovat n´aˇs prostor t´ım, ˇze vybereme pouze k nejvyˇsˇs´ıch vlastn´ıch ˇc´ısel (k < k0 ) a k nim pˇr´ısluˇsn´ ych vlastn´ıch vektor˚ u, ˇc´ımˇz vznikne odhad matice A: Ak = Uk Sk VkT .
19
(5)
V SVD reprezentuj´ı vlastn´ı vektory pˇr´ısluˇsn´e nejvyˇsˇs´ım vlastn´ım ˇc´ısl˚ um smˇery nejvˇetˇs´ıho rozptylu dat. Pokud tedy zanedb´ame vlastn´ı ˇc´ısla nejniˇzˇs´ıch hodnot, pˇrijdeme jen o minimum s´emantick´ ych aspekt˚ u textu a z´aroveˇ n sn´ıˇz´ıme nutn´ y v´ ypoˇcetn´ı v´ ykon. Pro nalezen´ı podobnosti dotazu a jednotliv´ ych dokument˚ u je pouˇzita opˇet kosinov´ a vzd´ alenost, a to mezi vektorem dotazu a jednotliv´ ymi sloupci matice Ak . Takov´ ato jednoduch´ a implementace m´a jednu nev´ yhodu. Pro obrovsk´e mnoˇzstv´ı prohledan´ ych dat nen´ı tˇreba reorganizovat staˇzen´a data ani struktury, ve kter´ ych m´ ame uloˇzen´e v´ ysledky (jako napˇr. naˇs´ı term-document matici). Pro menˇs´ı poˇcet dat si ale nem˚ uˇzeme dovolit ignorovat slova, kter´a nem´ame zahrnuta ve slovn´ıku a novˇe nalezen´e dokumenty nelze povaˇzovat za ned˚ uleˇzit´e. Je proto nutn´e pˇri budov´ an´ı indexu do naˇseho algoritmu zahrnout i moˇznost aktualizovat naˇse struktury - tzn. pˇrid´avat nov´e dokumenty a slova a aktualizovat ty st´ avaj´ıc´ı. Mezi takov´e metody patˇr´ı napˇr. fold-in nebo SVD updating.
3.3
PageRank
Algoritmus PageRank byl navrˇzen´ y Larry Pagem a Sergeyem Brinem a tvoˇr´ı z´ aklad vyhled´ avaˇce Google. Jedna se o typick´ y pˇr´ıklad hyperlink-based algoritmu, kter´ y vyuˇz´ıv´ a strukturu odkaz˚ u mezi webov´ ymi str´ankami pro jejich hodnocen´ı. D˚ uleˇzitost str´ anky je urˇcena podle poˇctu dalˇs´ıch str´anek, kter´e na n´ı ukazuj´ı. Z´ aroveˇ n je ale br´ ano v u ´vahu i hodnocen´ı odkazuj´ıc´ıch str´anek. Cel´ y vzorec vypad´ a takto17 : P R(A) = (1 − d) + d
P R(T ) P R(Tn ) 1 + ··· + , C(T 1) C(Tn )
(6)
kde P R(A) je PageRank str´ anky A, P R(Ti ) je PageRank str´anky Ti , kter´a odkazuje na A, C(Ti ) je mnoˇzstv´ı odkaz˚ u vedouc´ı ze str´anky Ti a d je tzv. damping factor - ˇc´ıslo mezi 0 a 1. Ze vzorce vid´ıme, ˇze hodnocen´ı str´anek Ti neovlivˇ nuje PageRank str´anky A rovnomˇernˇe, ale z´ avis´ı i na poˇctu odkaz˚ u vedouc´ı z Ti . Pokud tedy z nˇejak´e str´anky vede velk´e mnoˇzstv´ı odkaz˚ u, budou se tyto odkazy na PageRanku prom´ıtat pouze minim´ alnˇe. Vzorec je rekurzivn´ı, ale pˇri jak´ ychkoli vstupn´ıch dat postupnˇe konverguje k v´ ysledku. Existuje jeˇstˇe druh´ a verze algoritmu, jej´ıˇz vzorec vypad´a takto: P R(A) =
P R(T ) P R(Tn ) (1 − d) 1 +d + ··· + , N C(T 1) C(Tn )
(7)
kde N je poˇcat str´ anek na webu. Od prvn´ı verze se tento vzorec pˇr´ıliˇs neliˇs´ı, ale d´ıky vydˇelen´ı N ud´ av´ a opravdovou pravdˇepodobnost, ˇze se uˇzivatel pˇri 17 http://pr.efactory.de/e-pagerank-algorithm.shtml
20
n´ ahodn´em surfov´ an´ı dostane na danou str´anku. Algoritmus pak reprezentuje pravdˇepodobnostn´ı rozdˇelen´ı nad vˇsemi str´ankami na webu, takˇze suma PageRanku vˇsech str´ anek se sˇc´ıt´ a do jedniˇcky. P˚ uvodnˇe byl algoritmus PageRank pops´an jako model chov´an´ı uˇzivatele pˇri surfov´ an´ı webu, kde dan´ y uˇzivatel n´ahodnˇe klik´a na odkazy, aniˇz by mu z´aleˇzelo na obsahu str´ anek18 . Uˇzivatel s pravdˇepodobnost´ı d bude pokraˇcovat v surfov´an´ı a s pravdˇepodobnost´ı 1 − d skonˇc´ı svou session. Kromˇe toho slouˇz´ı damping factor d k normalizaci hodnocen´ı - souˇcet jednotliv´ ych PageRank vˇsech prohledan´ ych str´ anek je konstantn´ı. Sergey Brin navrhl d = 0.85, coˇz je hodnota, kter´a se nejˇcastˇeji pouˇz´ıv´ a a byla spoˇc´ıt´ana statistick´ ymi metodami. Podrobnou studii o hodnotˇe faktoru d a jeho moˇzn´ ych alternativ´ach udˇelali v roce 2006 vˇedci z univerzity Shu-Te na Taiwanu[FLT06]. Jedno ze zaj´ımav´ ych vylepˇsen´ı popsal napˇr´ıklad Taher H. Haveliwala ve sv´e studii TopicSensitive PageRank [Hav02], ve kter´e navrhuje napoˇc´ıt´av´an´ı v´ıce neˇz pouze jednoho PageRank vektoru pro vˇetˇs´ı pˇresnost v z´avislosti na hledan´em dotazu. Nejprve se mus´ı urˇcit jednotliv´a t´emata (okruhy), pro kter´e se bude PageRank vektor poˇc´ıtat. N´aslednˇe se pˇri zpracov´an´ı dotazu vyhodnot´ı, do kter´eho t´ematu tento dotaz spad´a, a pouˇzije se odpov´ıdaj´ıc´ı vektor. Vytvoˇren´ım topic-sensitive19 verze PageRank algoritmu pˇredejdeme vysok´emu hodnocen´ı str´ anek, na kter´e vede hodnˇe odkaz˚ u a kter´e obsahuj´ı nˇekter´e z hledan´ ych slov, ale ve skuteˇcnosti nemaj´ı ˇz´adnou spojitost s hledan´ ym t´ematem. Tento postup se d´ a uplatnit napˇr. pˇri vyhled´av´an´ı slov v nˇejak´em kontextu. Ve zm´ınˇen´e studii je uveden hezk´ y pˇr´ıklad, kdy uˇzivatel proch´az´ı nˇejak´ y dokument zab´ yvaj´ıc´ı se slavn´ ymi architekty na str´ance pomoc´ı vyhled´av´an´ı zv´ yrazn´ı slovo ”architektura”, ke kter´emu chce naj´ıt dalˇs´ı informace. V tomto kontextu by bylo vhodn´e, aby v´ ysledek takov´eho vyhled´av´an´ı byl odliˇsn´ y od toho, kdyˇz si takov´ y uˇzivatel vyhled´ a term´ın ”architektura”pouˇzit´ y v ˇcl´anku o procesorech. Ve zkratce se topic-sensitive PageRank d´a popsat takto: Bˇehem offline zpracov´ an´ı naˇseho prohled´ av´ an´ı (web crawl) vygenerujeme urˇcit´ y poˇcet topic-sensitive PageRank vektor˚ u. Bˇehem zpracov´an´ı dotazu spoˇc´ıt´ame podobnost dotazu (query similarity, moˇzn´e zahrnout i kontext, ve kter´em hled´ame) s kaˇzd´ ym t´ematem a m´ısto pouˇzit´ı jednoho glob´ aln´ıho PageRank vektoru pouˇzijeme line´arn´ı kombinaci naˇs´ı mnoˇziny vektor˚ u v´ aˇzenou spoˇcten´ ymi podobnostmi. D˚ uleˇzit´ ym faktem je to, ˇze naˇse mnoˇziny pro zvolen´a t´emata musej´ı b´ yt vych´ ylen´a (biased ). Toho dos´ ahneme n´ asleduj´ıc´ım postupem: ( 1 , i ∈ Tj (8) vi,j = |Tj | 0, i ∈ / Tj , kde Tj je mnoˇzina URLs v nˇejak´em top-level directory v kategorii cj (m´ame j kategori´ı). D´ ale vj je vektor, kter´ y pouˇzijeme bˇehem v´ ypoˇctu PageRanku 18 random 19 citliv´ e
surfer na t´ ema, tento v´ yraz se obt´ıˇ znˇ e pˇrekl´ ad´ a do ˇ cesk´ eho jazyka
21
nam´ısto jednoho obecn´eho vektoru.
3.4
HITS
HITS patˇr´ı mezi dalˇs´ı ze tˇr´ıdy hyperlink-based algoritm˚ u pro identifikaci skupin str´ anek zab´ yvaj´ıc´ıch se stejn´ ym t´ematem na webu. Algoritmus dˇel´ı jednotliv´e str´ anky na ”authorities”a ”hubs”20 . Authorities jsou str´anky s bohat´ ym obsahem, kter´e mezi sebou vˇetˇsinou nemaj´ı odkazy. Oproti tomu hubs jsou str´anky slouˇz´ıc´ı jako adres´ aˇr odkazuj´ıc´ı na mnoho autoritativn´ıch str´anek. Dobr´ y hub je proto takov´ a str´ anka, kter´ a m´a co nejv´ıce odkaz˚ u na dobr´e authorities, a dobr´a authority je str´ anka, na kterou je odkazov´ano z mnoha hubs. Tyto dva typy dokument˚ u jsou separov´ any dvˇemi n´asleduj´ıc´ımi operacemi[NOHI04]: X xp = yq (9) q,q→p
yp =
X
xq
(10)
q,p→q
Pro str´ anku p je v´ aha xp upravena podle poˇctu yq napˇr´ıˇc vˇsemi str´ankami q, kter´e na p odkazuj´ı. Stejn´ ym zp˚ usobem jsou poˇc´ıt´any i v´ahy yp . T´ım jsou spoˇc´ıt´ any v´ ahy jednotliv´ ych hubs i authorities. Algoritmus HITS byl navrˇzen Jonem Kleinbergem za doby jeho p˚ usoben´ı v IBM a byl v podstatˇe pˇredch˚ udcem algoritmu PageRank.
20 Tyto
ˇ stiny term´ıny nebudu pˇrekl´ adat do Ceˇ
22
4
Existuj´ıc´ı software
Zde se pod´ıv´ ame, jak´ y software v kategorii webcrawlingu a vyhled´av´an´ı jiˇz existuje, a udˇel´ ame struˇcn´ y pˇrehled. Nejprve uvedeme pˇr´ıklad na velk´ ych vyhled´ avac´ıch syst´emech a pot´e zm´ın´ıme nˇekolik odkaz˚ u na existuj´ıc´ı crawlery a boty.
4.1
Google
Google bˇeˇz´ı na distribuovan´e s´ıti milion˚ u levn´ ych poˇc´ıtaˇc˚ u, takˇze dok´aˇze zpracov´ avat velk´e mnoˇzstv´ı proces˚ u souˇcasnˇe21 . Google se skl´ad´a ze tˇr´ı hlavn´ıch ˇc´ ast´ı: • Google-bot - web crawler • Indexer - analyzuje slova na str´ank´ach a star´a se o index • Query processor - porovn´av´a dotazy od uˇzivatele i indexem a vrac´ı relevantn´ı dokumenty Google-bot Google-bot se skl´ ad´ a z mnoha poˇc´ıtaˇc˚ u, kteˇr´ı bez pˇrest´avky stahuj´ı tis´ıce r˚ uzn´ ych str´ anek souˇcasnˇe. Aby se zabr´anilo pˇrehlcen´ı server˚ u, tak Google-bot pos´ıl´a na jednotliv´e servery poˇzadavky pomaleji, neˇz je jeho opravdov´ y v´ ykon. Existuj´ı dva zp˚ usoby, jak tento bot nal´ez´a nov´e str´anky: skrze formul´aˇr na adrese www.google.com/addurl.html a skrze URL, kter´e se nach´azej´ı na prohledan´ ych str´ ank´ ach. Tento formul´ aˇr obsahuje test, kter´ y m´a za u ´kol rozpoznat, zda se jedn´a o uˇzivatele ˇci jin´eho bota, aby se zabr´anilo zneuˇz´ıv´an´ı pro spam a komerˇcn´ı u ´ˇcely. Hodnˇe spammer˚ u totiˇz zaˇcalo vym´ yˇslet taktiky, jak zv´ yˇsit viditelnost sv´ ych str´ anek v Google indexu. Google-bot provozuje tzv. deep crawling, takˇze n´asleduje jednotliv´e linky do velk´e hloubky, coˇz mu umoˇzn ˇuje prozkoumat velkou ˇc´ast webu. Jelikoˇz je ale str´ anek obrovsk´e mnoˇzstv´ı, prob´ıh´a crawling dan´e str´anky pouze jednou za ˇcas - napˇr. jednou za mˇes´ıc. Str´ anky, kter´e m´ a Google-bot v pl´anu navˇst´ıvit mus´ı b´ yt permanentnˇe porovn´ av´ any s jiˇz navˇst´ıven´ ymi, aby se zabr´anilo duplicitˇe. Str´anky, kter´e jsou navˇstˇevovanˇejˇs´ı a mˇen´ı se dynamicky jsou navˇstˇevov´any a analyzov´any ˇcastˇeji neˇz ty statick´e a m´enˇe popul´arn´ı, aby byl idnex st´ale aktu´aln´ı. Tomu se ˇr´ık´a tzv. fresh crawl. Napˇr´ıklad r˚ uzn´e str´anky zab´ yvaj´ıc´ı se zpr´avami a jin´ ym ˇcasto se mˇen´ıc´ı obsahem jsou stahov´any kaˇzd´ y den. Fresh crawls samozˇrejmˇe st´ahnou mnohem m´enˇe str´ anek neˇz deep crawls, takˇze pro optim´aln´ı strategii je pouˇzita kombinace obou technik. 21 parallel
processing
23
Indexer Indexer dost´ av´ a od crawleru kompletn´ı obsah staˇzen´e str´anky. Tyto str´anky jsou uloˇzeny v indexu. Index je seˇrazen abecednˇe podle hledan´ ych v´ yraz˚ u, kde ke kaˇzd´emu slovu existuje list str´anek, jeˇz toto slovo obsahuj´ı. Google tak´e pouˇz´ıv´ a stop words, aby se vyhnul zbyteˇcn´e anal´ yze v´ yraz˚ u, kter´e nesou jen minim´ aln´ı informaci a jsou pro relevanci v´ ysledn´eho hodnocen´ı str´anek ned˚ uleˇzit´e. Query Processor Query processor se skl´ ad´ a z v´ıce ˇc´ast´ı. Prvn´ı z nich je uˇzivatelsk´e rozhran´ı (tedy formul´ aˇr), do kter´eho uˇzivatel zad´av´a sv˚ uj dotaz. Dalˇs´ı ˇc´asti se pak jiˇz vˇenuj´ı vyhodnocen´ı zadan´eho dotazu pomoc´ı algoritmu PageRank, kter´ ym jsme se zab´ avali v dˇr´ıvˇejˇs´ı kapitole. Google tak´e pouˇz´ıv´a r˚ uzn´e algoritmy, kter´ ymi se uˇc´ı rozpoznat vztahy mezi r˚ uzn´ ymi slovy, a mimo jin´e tak´e implementuje automatick´e opravy pravopisn´ ych chyb. Seznam bot˚ u, kter´e Google pouˇz´ıv´a m˚ uˇze b´ yt nalezenem na str´ank´ach Google support22 . Bliˇzˇs´ı shrnut´ı toho, jak cel´ y vyhled´avaˇc funguje, se lze doˇc´ıst napˇr´ıklad zde23 . Dobr´ ym zdrojem m˚ uˇze b´ yt tak´e ˇcl´anek od samotn´ ych zakladatel˚ u Google[BP98].
4.2
Yahoo
Yahoo p˚ uvodnˇe zaˇcalo jako velk´ y webov´ y adres´aˇr s webov´ ymi str´ankami, kter´e byly hierarchicky organizovan´e do jednotliv´ ych skupin. Koncem devades´at´ ych let se z Yahoo stal plnohodnotn´ y vyhled´avaˇc. Podobnˇe jako Google se i Yahoo architektura skl´ad´a z v´ıce ˇc´ast´ı. Tˇemi nejd˚ uleˇzitˇejˇs´ımi jsou tyto dvˇe: • Spider - web crawler, u Yahoo se mu ˇr´ık´a Slurp • Indexer -vyhodnocuje obsah str´anek a buduje index Funkce jednotliv´ ych ˇc´ ast´ı je velmi podobn´a jako u Google, takˇze ji zde jiˇz nebudu podrobnˇe rozepisovat. Pro podrobnˇejˇs´ı informace ohlednˇe vyhled´avaˇc˚ u a jejich historie doporuˇcuji napˇr´ıklad pˇrehled, kter´ y udˇelali vˇedci z Minot State University v USA roku 2011[SFK11]. 22 http://support.google.com/webmasters/bin/answer.py?hl=en&answer=1061943 23 http://www.googleguide.com/google
works.html
24
4.3
Lydia
Lydia[LKS05] je projekt, kter´ y buduje relaˇcn´ı model lid´ı, m´ıst a publikac´ı pomoc´ı natural language processing str´anek zab´ yvaj´ıc´ıch se zpr´avami. Projekt dˇel´a statistickou anal´ yzu ˇcetnost´ı slov a ko-lokac´ı. Moment´alnˇe je v syst´emu cca 500 str´ anek zab´ yvaj´ıc´ıch se online zpravodajstv´ım. Lydia zjiˇst’uje, o kom se ve zpr´ av´ ach p´ıˇse, k´ ym, kde a kdy. Cel´ y syst´em je optimalizov´ an tak, aby byl schopen analyzovat obrovsk´e mnoˇzstv´ı textu ve velmi kr´ atk´em ˇcase, jelikoˇz je nutn´e zpracovat cel´ y obsah online zpravodajsk´eho port´ alu kaˇzd´ y den (a tˇechto port´al˚ u je tak´e velk´e mnoˇzstv´ı). Aktu´aln´ı informace jsou na adrese http://www.textmap.com/. Nejprve crawler z´ısk´ a text str´anky, pot´e se identifikuje, kde se dan´e objekty (lidi, m´ısta, spoleˇcnosti apod.) nach´azej´ı v textu. Pro kaˇzd´ y takov´ y objekt se zjiˇst’uje, jak´e dalˇs´ı objekty se vyskytuj´ı pobl´ıˇz. Kaˇzd´ y objekt m˚ uˇze b´ yt pouˇzit v´ıce r˚ uzn´ ymi zp˚ usoby, a proto se jeˇstˇe mus´ı identifikovat synonyma. Nakonec n´ asleduj´ı r˚ uzn´e anal´ yzy, kter´ ymi se vypoˇc´ıt´a, jak ˇcasto se objekty objevuj´ı na jednotliv´ ych str´ ank´ ach. Pˇrehled vˇsech aktivit ohlednˇe syst´emu Lydia je na str´ank´ach http://www.cs.sunysb.edu/∼skiena/lydia/.
4.4
Dalˇ s´ı boti
Kaˇzd´ y vyhled´ avaˇc m´ a sv´e boty, ale vzhledem k tomu, ˇze vˇsichni funguj´ı velmi podobnˇe, nem´ a smysl je zde podrobnˇe rozeb´ırat, nebot’ to nen´ı c´ılem t´eto pr´ace. Kromˇe bot˚ u, kteˇr´ı pracuj´ı pro velk´e vyhled´avaˇce existuje ale i mnoho dalˇs´ıch, kteˇr´ı mohou b´ yt vyvinuty pro specieln´ı druh pr´ace. Vzhledem k velk´emu poˇctu a r˚ uznorodosti zde uvedu nˇekolik odkaz˚ u na seznam existuj´ıc´ıch bot˚ u. • http://www.robotstxt.org/db.html • http://www.user-agents.org/
4.5
Focused crawlery
V t´eto sekci se pod´ıv´ ame na pˇr´ıklady crawler˚ u, kter´e jsou naˇs´ı implementaci svou funkcionalitou nejbliˇzˇs´ı (mohou se ale v´ yraznˇe liˇsit pˇr´ıstupem k prohled´av´an´ı). Prvn´ım pˇr´ıkladem takov´eho crawleru je napˇr´ıklad Bingo!24 . Tato implementace pouˇz´ıv´ a klasifik´ ator, kter´ y pomoc´ı tr´enovac´ıch dat odhaluje archetypy v analyzovan´ ych str´ ank´ ach a ty n´aslednˇe porovn´av´a s novˇe nalezen´ ymi str´ankami. Jakmile byla str´ anka klasifikov´ana, jsou z n´ı extrahov´any vˇsechny linky, kter´e 24 http://www.mpi-inf.mpg.de/departments/d5/software/bingo/idx.htm
25
Obr´ azek 6: Diagram Lydia pipeline[LKS05]
jsou um´ıstˇeny do fronty. Bingo! pouˇz´ıv´a kombinaci strategi´ı pro priorizaci str´anek ve frontˇe, jako napˇr´ıklad prohled´av´an´ı do hloubky s fixn´ı hloubkou. K vyhled´ av´ an´ı jsou pouˇzity i takov´e str´anky, kter´e neproˇsly testem klasifik´atoru, nicm´enˇe je na nˇe aplikov´ ano prohled´av´an´ı do menˇs´ı hloubky. To se dˇel´a z d˚ uvodu, ˇze nˇekdy se k relevantn´ımu obsahu d´a dostat pouze skrz r˚ uzn´e uv´ıtac´ı str´ anky a rozcestn´ıky, kter´e samy o sobˇe nenesou ˇz´adn´e informace. Pro anal´ yzu dokument˚ u Bingo! pouˇz´ıv´ a kombinaci r˚ uzn´ ych strategi´ı, mimo jin´e i TF-IDF m´ıru. Dalˇs´ım pˇr´ıkladem je Win Web Crawler 225 , coˇz je n´astroj pro webmastery pro vytv´ aˇren´ı webov´ ych adres´aˇr˚ u a podporu webov´ ych port´al˚ u. Tento crawler extrahuje URL, meta tagy, text a dalˇs´ı cenn´e informace z prohledan´ ych str´anek a uloˇz´ı je na disk. Program nav´ıc podporuje ˇsirok´ y v´ ybˇer filtr˚ u a omezen´ı pro podrobnˇejˇs´ı specifikaci crawling session.
25 http://www.fileguru.com/Win-Web-Crawler/info
26
5
Implementace crawleru
V t´eto sekci se pod´ıv´ ame na implementaci konkr´etn´ıho crawleru a rozebereme si jednotliv´e struktury programu.
5.1
Popis
Nejprve si mus´ıme uvˇedomit, co n´aˇs crawler vlastnˇe bude umˇet, a ˇc´ım se bude odliˇsovat od ostatn´ıch crawlers. M´ ym c´ılem je navrhnout tzv. focused crawler, kter´ y bude vyhled´ avat zadan´a slova, pˇr´ıpadnˇe str´anky zab´ yvaj´ıc´ı se nˇejak´ ym bl´ıˇze nespecifikovan´ ym t´ematem. Kromˇe c´ılen´eho vyhled´av´an´ı bude moˇzno i vyhled´ av´ an´ı bez specifikace hledan´ ych v´ yraz˚ u - str´anky pak budou hodnoceny na z´ akladˇe mnoˇzstv´ı informac´ı, kter´e obsahuj´ı. Nebudeme m´ıt k dispozici dostateˇcn´ y v´ ypoˇcetn´ı v´ ykon ani mnoˇzstv´ı dat, abychom si mohli vybudovat rozs´ahl´ y index, ve kter´em bychom prov´adˇeli vyhled´av´an´ı - budeme tedy vyhled´avat za chodu. Vybudov´ an´ı indexu ale tak´e do naˇs´ı implementace zahrneme, abychom mohli v´ ysledky vyhled´ av´ an´ı pouˇz´ıt i offline. Narozd´ıl od vyhled´ avaˇc˚ u, kter´e pouˇz´ıvaj´ı velk´ y poˇcet bot˚ u k pravideln´emu prohled´ av´ an´ı Webu a tvorbˇe rozs´ahl´eho (a aktu´aln´ıho) indexu, nem´ame k dispozici takov´ y v´ ypoˇcetn´ı v´ ykon, aby naˇse v´ ysledky byly srovnateln´e napˇr. s Google. Proto zvol´ıme jin´ y pˇr´ıstup - budeme prohled´avat omezen´ y poˇcet str´anek, kter´e postupnˇe analyzujeme, a na konci session26 zobraz´ıme v´ ysleky. D´ıky n´ızk´emu poˇctu prohledan´ ych str´ anek (tis´ıce aˇz des´ıtky tis´ıc) budeme str´anky hodnotit jen na z´ akladˇe v´ yskyt˚ u hledan´ ych slov a zanedb´ame odkazy mezi nimi. Posledn´ı vˇec, kterou je nutn´e zm´ınit, je, ˇze v´ ysledek dan´e session je d´an hlavnˇe t´ım, jak´e zdrojov´e str´ anky (seed URLs) pouˇzijeme. D´ıky niˇzˇs´ımu poˇctu prohledan´ ych str´ anek nem˚ uˇzeme zaˇc´ıt s prohled´av´an´ım pˇr´ıliˇs daleko od zvolen´eho t´ematu (tzn. pokud hled´ ame informace o webov´em vyhled´av´an´ı, nem˚ uˇzeme oˇcek´ avat velk´ y u ´spˇech, zaˇcneme-li vyhled´avat na str´ank´ach, kter´e se zab´ yvaj´ı vaˇren´ım). Crawler bude ps´ an v jazyce Java. K parsov´an´ı HTML pouˇzijeme vestavˇen´e knihovny. Jejich dokumentace je dostupn´a na str´ank´ach Oracle27 . Souˇc´ast´ı bude i grafick´e uˇzivatelsk´e rozhran´ı a podpora v´ıce vl´akem pro spuˇstˇen´ı nˇekolika nez´ avisl´ ych crawler˚ u souˇcasnˇe.
5.2
Pr˚ ubˇ eh session
Crawler bude vykon´ avat jednoduch´ y cyklus: st´ahne zdrojov´ y k´od str´anky, zpracuje vˇsechen text na n´ı, uloˇz´ı si odkazy, kter´e ze str´anky vedou a pokraˇcuje takto d´ al. 26 jeden
cyklus prohled´ av´ an´ı
27 http://docs.oracle.com/javase/6/docs/api/javax/swing/text/html/parser/package-
summary.html
27
Obr´ azek 7: Z´akladn´ı cyklus webcrawling session Prvn´ı vˇec, kterou je tˇreba rozhodnout, je jakou strukturu pouˇz´ıt pro ukl´ad´an´ı novˇe z´ıskan´ ych URLs. Zde implementujeme frontu. D˚ uvody byly jiˇz rozebr´any v pˇredchoz´ıch kapitol´ ach. Na konci prohled´ av´ an´ı crawler vyhodnot´ı vˇsechny navˇst´ıven´e str´anky a na z´akladˇe TF-IDF metriky kaˇzd´e z nich pˇriˇrad´ı hodnocen´ı, kter´e odpov´ıd´a relevanci dan´e str´ anky. Tato hodnocen´ı budou uloˇzena spolu s dalˇs´ımi cenn´ ymi statistikami, jako napˇr. ˇcetnostmi slov na jednotliv´ ych str´ank´ach a graf˚ u pr˚ ubˇehu cel´e session. Nakonec program vyprodukuje v´ ystup, kde budou zobrazeny nejl´epe hodnocen´e str´ anky a umoˇzn´ı uˇzivateli dalˇs´ı interakci. Mimo to crawler vyprodukuje index, ve kter´em bude moˇzn´e vyhled´avat i po skonˇcen´ı session.
5.3
Reprezentace dat a struktura
Vzhledem k tomu, ˇze cel´ y program je ps´an v jazyce Java, pˇr´ımo se nab´ız´ı pr´ace s daty jakoˇzto s objekty. Za objekt budeme povaˇzovat u ´plnˇe vˇse - od jednotliv´ ych slov, pˇres str´ anky aˇz po samotn´ y crawler. V´ yhodou je, ˇze od vˇetˇsiny stuktur bude existovat mnoho instanc´ı a my si o nich budeme schopni velmi jednoduˇse pamatovat ˇradu informac´ı (napˇr. u str´anek seznamy slov, r˚ uzn´a hodnocen´ı, u slov poˇcty v´ yskyt˚ u apod.). Nev´ yhodou je pak v nˇekter´ ych pˇr´ıpadech menˇs´ı efektivita a pamˇet’ov´ a n´aroˇcnost. Na to se ale pod´ıv´ame aˇz na konci t´eto kapitoly, pˇr´ıpadnˇe se pod´ıv´ ame na statistiky v kapitole shrnuj´ıc´ı v´ ysledky pr´ace. Hlavn´ı entitou je Master Manager, kter´a m´a pod sebou vˇsechny crawlery (tˇech m˚ uˇze b´ yt v´ıce a kaˇzd´ y bˇeˇz´ı v separ´atn´ım vl´aknˇe). Tˇr´ıda Crawler je pak ˇr´ıd´ıc´ım objektem pro jednotliv´e crawling sessions, kter´a m´a pod sebou vˇsechny dalˇs´ı 28
komponenty programu. Celou z´akladn´ı strukturu si m˚ uˇzete prohl´ednout na obr´ azku.
Obr´ azek 8: Z´akladn´ı struktura programu N´ asleduje struˇcn´ y popis nejd˚ uleˇzitˇejˇs´ıch entit: Manager Toto je hlavn´ı tˇr´ıda, kter´ a spravuje glob´aln´ı informace a argumenty pro spuˇstˇen´ı jednotliv´ ych crawler˚ u. M˚ uˇzeme pustit v´ıce prohled´av´an´ı najednou, kter´e pobˇeˇz´ı nez´ avisle na sobˇe v oddˇelen´ ych vl´aknech. Crawler Hlavn´ı struktura, ve kter´e prob´ıhaj´ı vˇsechny procesy spjat´e s prohled´av´an´ım a anal´ yzou dat. URL processor Tˇr´ıda, kter´ a se star´ a o nalezen´e URL adresy. V pˇr´ıpadˇe invalidn´ı nebo ignorovan´e adresy (nˇekter´e str´ anky m˚ uˇzeme pˇri urˇcit´em nastaven´ı crawleru ignorovat) se postar´ a o v´ yjimku. Text processor Spravuje informace o nalezen´ ych str´ank´ach a slovech (pˇr´ıpadnˇe dvojic´ıch atd.),
29
kter´e se na nich nach´ azej´ı. Pages detector Analyzuje obsah str´ anek a pˇriˇrazuje jim rating podle zvolen´e metody. Urˇcuje, jak´e str´ anky se na konci session objev´ı na vrcholu. Index generator Po skonˇcen´ı posledn´ı crawling session vytvoˇr´ı index pro budouc´ı vyhled´av´an´ı v ”offline”reˇzimu, resp. pomoc´ı druh´eho klienta. Zbyl´e tˇr´ıdy jsou urˇceny pro grafickou reprezentaci nalezen´ ych dat a jin´e funkce.
5.4
V´ ystup crawleru
Kromˇe popsan´ ych moˇznost´ı crawlingu m´a program jeˇstˇe p´ar dalˇs´ıch funkc´ı. Pod´ıv´ ame se tedy ted’, co vˇse je v´ ystupem jednotliv´ ych crawling sessions: Hodnocen´ı str´ anek: S´ am crawler i bez pouˇzit´ı indexu (aˇc oproti vyhled´av´an´ı v indexu pomˇernˇe neefektivnˇe) um´ı vytvoˇrit hodnocen´ı jednotliv´ ych str´anek, a to pouˇzit´ım TF-IDF m´ıry pro jednotliv´a slova a dvojice slov. Tato hodnocen´ı jsou pouˇzita i v pˇr´ıpadˇe, ˇze se session nˇekolikr´at opakuje pro nalezen´ı optim´aln´ıch zdrojov´ ych URL. Statistiky ignorovan´ ych a chybov´ ych URL: Soubory, ve kter´ ych jsou uvedeny vˇsechny URL, kter´e byly v pr˚ ubˇehu crawling session ignorov´any nebo se k nim nepodaˇrilo pˇripojit. Graf pohybu po str´ ank´ ach: Graf ve form´atu XML28 a k nˇemu pˇr´ısluˇs´ıc´ı soubor se statistikami o stupn´ıch uzl˚ u v tomto grafu. Obr´ azek podobnosti jednotliv´ ych str´ anek: Na obr´azku jsou ve stupn´ıch ˇsedi zn´ azornˇeny podobnosti (kosinov´e vzd´alenosti TF-IDF) kaˇzd´ ych dvou str´anek, kter´e jsme navˇst´ıvili. Cel´ y obr´azek je symetrick´ y nebot’ na diagon´ale se vyskytuj´ı vˇzdy stejn´e str´ anky. Statistiky v´ yskyt˚ u slov: Crawler sleduje statistiky ˇcetnost´ı jednotliv´ ych slov a dvojic slov. Kromˇe toho rozliˇsuje tyto ˇcetnosti v r´amci vˇsech prozkouman´ ych str´ anek i jednotlivˇe na kaˇzd´e str´ance zvl´aˇst’. Index: Crawler na konci posledn´ı session vytvoˇr´ı matici a k n´ı pˇr´ısluˇsn´e soubory (viz dalˇs´ı kapitola). 28 optimalizovan´ y
pro prohl´ıˇ zen´ı v programu yED - http://www.yworks.com/en/products yed about.html
30
5.5
Stop words
Stop words jsou slova, kter´ a se v dan´em jazyce vyskytuj´ı ˇcasto, ale nenesou ˇz´ adnou v´ yznamovou informaci. Vˇetˇsinou se jedn´a o r˚ uzn´e pˇredloˇzky, spojky apod. Seznam tˇechto slov se oznaˇcuje jako stopwords a tato slova jsou zpravidla pˇri budov´ an´ı indexu a vyhled´av´an´ı zcela ignorov´ana. My m´ ame moˇznost na zaˇc´ atku session specifikovat cestu k souboru, kde m´ame n´ aˇs seznam stopwords uloˇzen, a t´ım tyto v´ yrazy pˇri zpracov´an´ı dat zanedbat. Kromˇe toho, pokud jsme nˇejak´ y takov´ y seznam vybrali, crawler n´am na konci session s´ am nab´ıdne nˇekolik des´ıtek nejˇcastˇejˇs´ıch v´ yraz˚ u (v tomto pˇr´ıpadˇe slov s nejvyˇsˇs´ım ratingem), ze kter´ ych m˚ uˇzeme vybrat libovoln´e mnoˇzstv´ı. Tato vybran´ a slova pak budou automaticky pˇrid´ana do naˇseho seznamu pro budouc´ı pouˇzit´ı.
5.6
Probl´ emy implementace
Asi nejvˇetˇs´ım z´ adrhelem m´e implementace ja v´ ypoˇcetn´ı sloˇzitost a ukl´ad´an´ı dat. Jelikoˇz ani pr´ ace se soubory ani r˚ uzn´e metody zab´ yvaj´ıc´ı se efektivitou vyuˇzit´ı v´ ypoˇcetn´ıho v´ ykonu nebyly pˇredmˇetem t´eto pr´ace, zvolil jsem pomˇernˇe jednoduch´e struktury. Tomu samozˇrejmˇe odpov´ıd´a i v´ ysledn´ y v´ ykon a pamˇet’ov´a n´ aroˇcnost. Kromˇe toho bˇehem kaˇzd´e session zpracov´av´am jeˇstˇe dalˇs´ı data - pˇredevˇs´ım r˚ uzn´e statistiky ˇcetnost´ı skupin slov, generov´an´ı graf˚ u a obr´azku apod., kter´e pro samotn´e vyhled´ av´ an´ı nejsou pˇr´ımo potˇrebn´e. Pr´ace by tedy ˇsla zefektivnit pouˇzit´ım jednoduˇsˇs´ıho crawleru, kter´ y by mˇel pouze ty funkce, kter´e jsou bezprostˇrednˇe nutn´e pro vytvoˇren´ı indexu.
5.7
Budov´ an´ı indexu
N´ aˇs crawler um´ı na konci dan´e crawling session zobrazit v´ ysledky, takˇze nˇejakou zpˇetnou vazbu jiˇz m´ ame. Pro dlouhodob´e uˇz´ıv´an´ı by ale bylo ponˇekud neˇsikovn´e, kdybychom pˇri kaˇzd´em vyhled´av´an´ı nˇejak´eho dotazu museli ˇcekat, neˇz probˇehne cel´ a session a my koneˇcnˇe uvid´ıme relevantn´ı v´ ysledky. Proto bychom si mˇeli vybudovat index, ve kter´em budeme moci vyhled´avat i po skonˇcen´ı vˇsech crawling session.
Obr´azek 9: Z´akladn´ı cyklus
31
5.8
Struktury indexu
Crawler si uchov´ av´ a ˇradu zaj´ımav´ ych informac´ı a statistik, kter´e nasb´ıral bˇehem prozkoum´ av´ an´ı webu. K vybudov´an´ı indexu n´am ale staˇc´ı jen nˇekter´e z nich. V prvn´ı ˇradˇe budeme potˇrebovat sestavit tzv. term-document matrix A = [ai,j ], kde ai,j znaˇc´ı term frequency slova i na str´ance j. Tato matice zat´ım nebyla standardn´ım v´ ystupem crawleru, a d´ıky uchov´av´an´ı velk´eho mnoˇzstv´ı informac´ı bˇehem prohled´ av´ an´ı, ji budeme tvoˇrit aˇz na konci posledn´ı session (kter´a by mˇela b´ yt ze vˇsech nejv´ıce relevantn´ı). Matice je uloˇzena jako textov´ y soubor, coˇz je sice pomˇernˇe neefektivn´ı, ale jednoduch´e (a my zat´ım pracujeme sp´ıˇse s menˇs´ım poˇctem dat29 ). Mus´ıme si tedy uvˇedomit, jak´e struktury budeme k reprezentaci dat potˇrebovat. Kromˇe samotn´eho souboru s matic´ı A to bude jeˇstˇe soubor s jednotliv´ ymi str´ankami a slovy, ke kter´ ym si mus´ıme pamatovat indexy (tzn. pozice v naˇs´ı matici) a IDF m´ıry jednotliv´ ych slov, abychom je mohli pouˇz´ıt pro vyhled´av´an´ı. Jakmile budeme m´ıt tyto v´ ysledky uloˇzen´e, vytvoˇr´ıme si klienta, kter´ y bude v indexu vyhled´ avat. Pˇri jeho spuˇstˇen´ı specifikujeme cestu k uloˇzen´ ym dat˚ um (tzn. m˚ uˇzeme m´ıt v´ıce speci´aln´ıch index˚ u) a n´aslednˇe m˚ uˇzeme zad´avat dotazy, jejichˇz v´ ysledkem budou jednotliv´e prozkouman´e str´anky seˇrazen´e podle relevance. Jako m´ıru budeme opˇet pouˇz´ıvat TF-IDF.
5.9
Klient
Uˇzivatel nejprve specifikuje cestu k soubor˚ um, kter´e jsme pro u ´ˇcely naˇseho indexu vytvoˇrili. N´ aslednˇe si klient do pamˇeti naˇcte soubory s jednotliv´ ymi slovy a url prozkouman´ ych str´ anek spolu s jejich indexy do term-document matrix. Samotnou matici si jiˇz do pamˇeti naˇc´ıtat nemus´ıme, nebot’ n´am staˇc´ı pouze naˇc´ıst ty jej´ı ˇr´ adky, kter´e budou odpov´ıdat slov˚ um obsaˇzen´ ych v dotazu30 od uˇzivatele. N´ aslednˇe jsme schopni t´emˇeˇr okamˇzitˇe napoˇc´ıtat vˇsem str´ank´am rating podle tf hledan´ ych slov, seˇradit str´anky sestupnˇe podle ratingu a zobrazit v´ ysledky.
29ˇ r´ adovˇ e
tis´ıce aˇ z desetitis´ıce str´ anek
30 query
32
6
Prezentace v´ ysledk˚ u
Jako prvn´ı uvedu nˇekolik praktick´ ych pˇr´ıklad˚ u z crawling sessions a n´asledn´em vyhled´ av´ an´ı r˚ uzn´ ych dotaz˚ u v indexech, kter´e jsem z nasb´ıran´ ych dat vytvoˇril. Hned na zaˇc´ atku mus´ım podotknout, ˇze m´e hodnocen´ı v´ ysledk˚ u bude velmi subjektivn´ı, nebot’ je obt´ıˇzn´e tyto v´ ysledky s nˇeˇc´ım porovnat. Vzhledem k n´ızk´emu rozsahu indexu (v ˇr´ adu tis´ıc˚ u str´anek a statis´ıc˚ u unik´atn´ıch slov) nelze tyto v´ ysledky porovn´ avat napˇr. s velk´ ymi internetov´ ymi vyhled´avaˇci. V pˇr´ıpadˇe menˇs´ıch str´ anek lze pro porovn´an´ı pouˇz´ıt lok´aln´ı vyhled´av´an´ı (podporuje-li ho prohled´ avan´ a dom´ena). Z hlediska pamˇet’opv´e n´aroˇcnosti, kter´a je z ˇc´asti zp˚ usoben´ a t´ım, ˇze m˚ uj crawler bˇehem session sb´ır´a spoustu dalˇs´ıch informac´ı, kter´e nejsou pro budov´ an´ı indexu pˇr´ımo potˇrebn´e, se omez´ım na prohled´av´an´ı pouze nˇekolika tis´ıc str´ anek.
6.1
Pˇ r´ıklad 1
Jako prvn´ı pˇr´ıklad jsem se rozhodl pouˇz´ıt str´anky zab´ yvaj´ıc´ı se vaˇren´ım spousta r˚ uzn´ ych str´ anek s recepty n´am poslouˇz´ı jako vhodn´e prostˇred´ı pro sbˇer dat a n´ asledn´ ym vyhled´av´an´ım v indexu budeme schopni alespoˇ n odhadnout, do jak´e m´ıry bylo naˇse vyhled´av´an´ı pˇresn´e. V´ yhodou je i to, ˇze jsem jako testovac´ı str´ anku vybral takovou, kter´a m´a vlastn´ı lok´aln´ı vyhled´avaˇc, takˇze m´ am moˇznost sv´e v´ ysledky i v menˇs´ı m´ıˇre porovn´avat s n´ım. Pro demonstraci v´ ysledk˚ u pouˇziji dva r˚ uzn´e dvouslovn´e dotazy. Dom´ ena: http://www.thekitchn.com/ Limit: 4000 str´ anek Lok´ aln´ı vyhled´ av´ an´ı: ANO Stopwords: ANO C´ılen´ e vyhled´ av´ an´ı: NE V´ıcen´ asobn´ e session: NE ˇ Cas: cca 45 min (vˇcetnˇe z´ apisu a zpracov´an´ı dat) Pamˇ et’ov´ a n´ aroˇ cnost na konci session: cca 1 GB Dotaz 1: Fried chicken31 Aˇckoli n´ ami prohledan´ ych 4000 str´anek nezahrnuje celou testovanou dom´enu, pro tento dotaz jsme dostali pˇrekvapivˇe dobr´e v´ ysledky. Tˇri z naˇsich pˇeti nejl´epe hodnocen´ ych str´ anek dokonce patˇr´ı mezi pˇetici nejl´epe hodnocen´ ych str´anek vestavˇen´eho vyhled´ avaˇce. Z naˇsich nalezen´ ych URL je jistˇe na prvn´ı pohled patrn´e, ˇze se vˇsechny t´ ykaj´ı (pˇr´ıpadnˇe je v receptu zahrnuto) smaˇzen´eho kuˇrete. Pojd’me se tedy pod´ıvat, jak dopadl n´aˇs druh´ y dotaz: 31 testov´ ano
dne 21. 2. 2013
33
Rank 1 2 3 4 5
My index http://www.thekitchn.com/dinner-recipe-baked-fried-chic152620 http://www.thekitchn.com/thomas-kellers-fried-chicken-r-80197 http://www.thekitchn.com/recipe-easy-chicken-marsala-116581 http://www.thekitchn.com/recipe-korean-f-159748 http://www.thekitchn.com/lighter-zucchini-fritti-olive-89272
Obr´azek 10: V´ ystup klienta Rank 1 2 3 4 5
Built-in search http://www.thekitchn.com/healthy-recipe-fake-fried-chicken165374 http://www.thekitchn.com/dinner-recipe-baked-fried-chic152620 http://www.thekitchn.com/thomas-kellers-fried-chicken-r-80197 http://www.thekitchn.com/recipe-korean-f-159748 http://www.thekitchn.com/recipe-fingerlicking-fried-chi-79965
Dotaz 2: Vegetarian meal Zde se naˇse v´ ysledky od jejich lok´aln´ıho vyhled´avaˇce jiˇz ponˇekud liˇs´ı, nicm´enˇe na prvn´ı pohled je oˇcividn´e, ˇze v´ ysledek naˇseho vyhled´av´an´ı pro tento dotaz byl pomˇernˇe u ´spˇeˇsn´ y a vˇsechny nalezen´e str´anky jsou naproto relevantn´ı. 34
Obr´ azek 11: V´ ystup lok´aln´ıho vyhled´av´an´ı Rank 1 2 3 4 5
My index http://www.thekitchn.com/recipes/vegetarian http://www.thekitchn.com/how-to-make-a-quick-vegetarian126712 http://www.thekitchn.com/vegetarian-recipes-72865 http://www.thekitchn.com/ideas-for-vegetarian-winter-recipesthat-can-be-served-cold-good-questions-184422 http://www.thekitchn.com/healthy-vegetarian-recipes-thatsatisfy-even-die-hard-meat-eaters-182827
35
Rank 1 2 3 4 5
6.2
Built-in search http://www.thekitchn.com/25-vegetarian-and-vegan-recipe104841 http://www.thekitchn.com/categories/vegetarian http://www.thekitchn.com/ideas-for-vegetarian-meals-with-nofruits-or-vegetables-good-questions-176647 http://www.thekitchn.com/meatless-recipe-163426 http://www.thekitchn.com/vegetarian-meals-to-satisfy-ronswanson-171323
Pˇ r´ıklad 2
Ve druh´em pˇr´ıkladu bych chtˇel uk´azat, jak funguje naˇse c´ılov´e vyhled´av´an´ı. Budeme opˇet vyhled´ avat lok´alnˇe, tentokr´at na anglick´e Wikipedii. N´aˇs crawler dostane nˇekolik kl´ıˇcov´ ych slov, podle kter´ ych na konci session ohodnot´ı prohledan´e str´ anky a zaˇcne dalˇs´ı session od tˇech nejslibnˇejˇs´ıch. Je to tedy nˇeco na zp˚ usob beam search32 . Wikipedii jsem vybral proto, ˇze je to obrovsk´a website, kde standardn´ı vyhled´ av´ an´ı v jedn´e session omezen´e shora limitem max prohledan´ ych str´ anek by pravdˇepodobnˇe nepˇrineslo uspokojiv´e v´ ysledky. Nav´ıc zde opˇet m˚ uˇzeme porovnat naˇse v´ ysledky s lok´aln´ım vyhled´av´an´ım, kter´e je na Wikipedii k dispozici. Dom´ ena: http://en.wikipedia.org/ Limit: 1500 str´ anek Lok´ aln´ı vyhled´ av´ an´ı: ANO Stopwords: ANO C´ılen´ e vyhled´ av´ an´ı: ANO V´ıcen´ asobn´ e session: 3x ˇ Cas: cca 50 min (vˇcetnˇe z´ apisu a zpracov´an´ı dat) Pamˇ et’ov´ a n´ aroˇ cnost na konci session: cca 1 GB Dotaz: Ancient Greek33 V´ ysledky pro tento dotaz si m˚ uˇzeme opˇet prohl´ednout v tabulce a srovnat je s v´ ysledky lok´ aln´ıho vyhled´ avaˇce. Vˇsechny nalezen´e nejlepˇs´ı v´ ysledky se t´ ykaj´ı hledan´eho dotazu. Str´ anka, kterou Wikipedie (a j´a osobnˇe tak´e) hodnot´ım jako nejv´ıce relevantn´ı skonˇcila na tˇret´ım m´ıstˇe. To je zp˚ usobeno vysok´ ymi frekvencemi slov ”ancient”a ”greek”na ostatn´ıch str´ank´ach a faktem, ˇze v naˇsem indexu nezohledˇ nujeme poˇrad´ı slov (tzn. zda hledan´e v´ yrazy jsou obsaˇzeny v textu str´ anky pˇr´ımo vedle sebe). 32 viz
kapitola 2 dne 28. 2. 2013
33 testov´ ano
36
Rank 1 2 3 4 5
My index http://en.wikipedia.org/wiki/Outline of ancient Greece http://en.wikipedia.org/wiki/Military of ancient Greece http://en.wikipedia.org/wiki/Ancient Greek http://en.wikipedia.org/wiki/Greek Evangelical Church http://en.wikipedia.org/wiki/List of ancient Greek theatres
Obr´ azek 12: Nejl´epe hodnocen´a str´anka dle naˇseho indexu
Tˇechto v´ ysledk˚ u bylo dosaˇzeno aˇz na konci tˇret´ı session. Pokud se pod´ıv´ame napˇr´ıklad na v´ ysledky nejl´epe hodnocen´ ych str´anek po prvn´ı session, kter´a zaˇc´ınala na tituln´ı str´ ance Wikipedie, uvid´ıme, ˇze pouze nˇekter´e z nich jsou relevantn´ı:
37
Rank 1 2 3 4 5
6.3
My index http://en.wikipedia.org/wiki/Greek Wikipedia http://en.wikipedia.org/wiki/Cyprus http://en.wikipedia.org/wiki/Portal:Arts http://en.wikipedia.org/wiki/Andrew Dalby http://en.wikipedia.org/wiki/Engineering
Pˇ r´ıklad 3
Jako sv˚ uj posledn´ı pˇr´ıklad jsem si vybral str´anku ˇzertovn´eho zpravodajstv´ı a politick´e satiry The Onion News Network, na kter´e provedu lok´aln´ı vyhled´av´an´ı a sestav´ım index. V´ ysledek pak ovˇeˇr´ım na dvou dotazech. Je zde opˇet moˇznost porovnat v´ ysledky s lok´ aln´ım vestavˇen´ ym vyhled´avaˇcem. Dom´ ena: http://www.theonion.com/ Limit: 6000 str´ anek Lok´ aln´ı vyhled´ av´ an´ı: ANO Stopwords: ANO C´ılen´ e vyhled´ av´ an´ı: NE V´ıcen´ asobn´ e session: NE ˇ Cas: cca 120 min (vˇcetnˇe z´ apisu a zpracov´an´ı dat) Pamˇ et’ov´ a n´ aroˇ cnost na konci session: cca 500 MB Dotaz: President Obama34 Tento dotaz pˇrinesl velmi vˇerohodn´e a pˇresn´e v´ ysledky, coˇz je d´ano hlavnˇe faktem, ˇze query ”president Obama”je pomˇernˇe aktu´aln´ı a tud´ıˇz se ve zpr´av´ach vyskytuje ˇcasto. Naˇse pokryt´ı 6000 str´anek tedy bylo dostateˇcn´e. Nav´ıc slova ”president”a ”Obama”se v textu ˇcasto vyskytuj´ı vedle sebe. Srovn´an´ı s lok´aln´ım vyhled´ avaˇcem zde ani nen´ı tˇreba. Rank 1 2 3 4 5
My index http://www.theonion.com/articles/biden-implores-obama-torub-one-out-before-debate,29785/ http://www.theonion.com/articles/obama-paranoid-governmentcoming-for-his-guns,30638/ http://www.theonion.com/articles/obama-reelectedpresident,30285/ http://www.theonion.com/articles/president-obama-mentionshed-like-to-see-lebron-ja,17512/ http://www.theonion.com/articles/president-obama-wonderingwhy-he-always-has-to-ini,27026/g
Dotaz: Peter Jackson Na tomto dotazu bych chtˇel pouk´azat na urˇcit´e nedostatky naˇseho vyhled´av´an´ı. 34 testov´ ano
dne 9. 3. 2013
38
Obr´ azek 13: Nejl´epe hodnocen´a str´anka dle naˇseho indexu Vybral jsem query ”Peter Jackson”, nebot’ je toto t´ema (d´ıky ned´avn´e premi´eˇre filmu Hobbit) pomˇernˇe aktu´aln´ı a n´aˇs crawler v t´eto t´ematice naˇsel nˇekolik str´ anek. ”Jackson”je ale pomˇernˇe frekventovan´e pˇr´ıjmen´ı, a kdyˇz se pod´ıv´ame na v´ ysledky naˇseho crawleru, tak z pˇeti nejl´epe hodnocen´ ych str´anek se spojen´ı ”Peter Jackson”objevuje pouze v jedn´e. Je to zp˚ usobeno t´ım, ˇze na nejl´epe hodnocen´e str´ance se pomˇernˇe frekventovanˇe vyskytuje slovo ”Jackson”, kter´e m´a nav´ıc o nˇeco vyˇsˇs´ı hodnocen´ı IDF neˇz ”Peter”(IDFjackson = 2.6321, IDFpeter = 2.3802). Rank 1 2 3 4 5
My index http://www.theonion.com/articles/reggie-jackson,18311/ http://www.theonion.com/articles/peter-jackson-opens-upabout-his-personal-hobbit-f,28487/ http://www.theonion.com/articles/phil-jackson-enjoyingretirement-on-montana-ranch,28021/ http://www.theonion.com/articles/lauren-jackson,28948/ http://www.theonion.com/articles/pet-dog-almost-likedisgusting-family-member,30794/
39
Obr´ azek 14: Pohyb crawleru bˇehem crawling session
40
7
Navrˇ zen´ı dalˇ s´ıho postupu
Bˇehem pr´ ace jsme implementovali funkˇcn´ı verzi crawleru, kter´ y je schopen vybudovat index, a klienta, kter´ y v nˇem um´ı vyhled´avat. V´ ysledky t´eto implementace jsou shrnuty v pˇredchoz´ıch kapitol´ach. Nyn´ı je ˇcas naznaˇcit, na co jiˇz v t´eto pr´aci nezbyl prostor. Zde tedy shrneme, jak´e u ´pravy je tˇreba udˇelat, aby se z naˇseho crawleru stal pouˇziteln´ y n´astroj, pˇr´ıpadnˇe i z´ aklad mal´eho specializovan´eho vyhled´avaˇce.
7.1
Pr´ ace s daty a v´ ykon
Jedn´ım z nejvˇetˇs´ıch probl´em˚ u souˇcasn´e implementace je pr´ace s daty. Jelikoˇz tato oblast nebyla tˇeˇziˇstˇem pr´ace, ˇreˇsili jsme ukl´ad´an´ı a naˇc´ıt´an´ı dat pomˇernˇe trivi´ aln´ım zp˚ usobem, coˇz se podepisuje i na souˇcasn´em v´ ykonu crawleru. Do budouc´ı verze softwaru (bude-li nˇejak´a) bude tˇreba zmˇenit zp˚ usob, jak´ ym ukl´ad´ame data, aby se s nimi dalo rychle a efektivnˇe pracovat. M´ısto textov´ ych soubor˚ u bude pouˇzita datab´ aze. Kromˇe toho by v´ ykon crawleru velmi vylepˇsilo, kdyby byla moˇznost si data v pr˚ ubˇehu session pravidelnˇe ukl´adat, jelikoˇz vˇetˇsina z nich bude potˇreba aˇz na u ´pln´em konci. Mimo jin´e by taky pomohlo, kdyby se cel´ y crawler v´ıce specializoval na vybudov´ an´ı indexu, nebot’ v souˇcasn´e dobˇe je trochu omezen faktem, ˇze bˇehem session zpracov´ av´a data, kter´a s indexem pˇr´ımo nesouvis´ı (anal´ yzy r˚ uzn´ ych skupin slov, grafy, obr´azky apod.). Zaj´ımav´e by t´eˇz bylo udˇelat takovou implementaci, kter´a by byla schopn´a efektivnˇeji vyuˇz´ıvat v´ıce vl´ aken a mohla b´ yt spustiteln´a na v´ıce poˇc´ıtaˇc´ıch souˇcasnˇe. Pak by se poˇcet zpracovan´ ych str´anek mohl pohybovat v ˇr´adovˇe vyˇsˇs´ıch ˇc´ıslech, ˇc´ımˇz by se zv´ yˇsila i relevance vr´acen´ ych v´ ysledk˚ u pˇri vyhled´av´an´ı.
7.2
Aktualizace indexu
V souˇcasn´e dobˇe je index vybudov´an na z´akladˇe jedn´e rozs´ahl´e crawling session. Pro lepˇs´ı v´ ysledky vyhled´ av´an´ı by ale bylo tˇreba implementovat moˇznost, jak tento index dynamicky rozˇsiˇrovat bˇehem jin´ ych session. Dalˇs´ı moˇznost´ı by bylo vybrat urˇcitou skupinu str´anek (ide´alnˇe takovou, kde se str´ anky ˇcasto mˇen´ı) a na n´ı prov´adˇet s ˇcasov´ ym odstupem opakovan´e prohled´ av´ an´ı a aktualizovat obsah indexu jednotliv´ ych str´anek. V kombinaci s rozˇsiˇrov´ an´ım indexu bychom tak mˇeli prvn´ı krok k vybudov´an´ı rozs´ahlejˇs´ıho vyhled´ avaˇce.
41
7.3
Podpora jazyk˚ u
Moment´ alnˇe n´ aˇs software funguje hlavnˇe na str´ank´ach v Angliˇctinˇe, nebot’ anglick´ a podstatn´ a jm´ena se neskloˇ nuj´ı, coˇz naˇsi pr´aci znaˇcnˇe usnadˇ nuje. Nicm´enˇe i zde by se dala udˇelat ˇrada vylepˇsen´ı, kter´e se t´ ykaj´ı gramatiky (v souˇcasn´e dobˇe n´ aˇs crawler napˇr. bere ”dog”a ”dogs”jako dvˇe naprosto odliˇsn´a slova). V pˇr´ıpadˇe nˇemeck´eho nebo ˇcesk´eho jazyka by n´aˇs software jiˇz ale narazil na ˇradu probl´em˚ u (kdyˇz pomineme problematiku zpracov´an´ı ˇcesk´e diakritiky) kv˚ uli rozliˇsov´an´ı p´ ad˚ u a r˚ uzn´ ych tvar˚ u slov. Tato t´ematika je znaˇcnˇe rozs´ahl´a a v pˇr´ıpadˇe budov´ an´ı vyhled´ avaˇce by bylo nutn´e se j´ı podrobnˇe zab´ yvat. V tomto ohledu se nab´ız´ı hned dalˇs´ı moˇzn´e rozˇs´ıˇren´ı, a to anal´ yza textu za u ´ˇcelem identifikace synonym. Pak by bylo moˇzn´e mnohem efektivnˇeji identifikovat str´ anky, kter´e se zab´ yvaj´ı podobnou t´ematikou. Identifikace synonym v textu se vˇetˇsinou dˇel´ a pomoc´ı hled´ an´ı slov, kter´e se vyskytuj´ı ve stejn´em kontextu (tzn. ve stejn´ ych vˇet´ ach na urˇcit´em m´ıstˇe). Touto t´ematikou se zab´ yv´a napˇr´ıklad tato studie[Cap03]. Jedn´ım z probl´em˚ u takov´e identifikace je ale napˇr´ıklad obt´ıˇzn´e rozliˇsov´ an´ı synonym a antonym. T´ım se zab´ yv´a napˇr´ıklad kr´atk´e shrnut´ı Identifying Synonyms among Distributionally SimilarWords z roku 2003[LZQZ03]. Jednou z metod takov´eho rozliˇsen´ı je napˇr´ıklad zasazen´ı potenci´aln´ıch synonym do nˇejak´eho kontextu (napˇr. dosazen´ım do slovn´ıho spojen´ı ”from X to Y”nebo ”either X or Y”). Pokud se slova X a Y vyskytuj´ı v takov´em v´ yznamu, zˇrejmˇe nep˚ ujde o synonyma (napˇr. ”from ally to foe”se bude vyskytovat sp´ıˇse neˇz ”from foe to opponent”). Jin´ ymi slovy existence takov´eho spojen´ı m˚ uˇze identifikovat antonyma.
7.4
Rozpozn´ av´ an´ı struktury str´ anek
Kl´ıˇcovˇe informace se na str´ ank´ach ˇcasto vyskytuj´ı pouze v urˇcit´ ych sekc´ıch. Velkou ˇc´ ast textov´eho obsahu mnoha str´anek tvoˇr´ı pro n´as naprosto nerelevantn´ı informace jako napˇr. reklamy, zpˇetn´e odkazy nebo r˚ uzn´e koment´aˇre apod. Identifikov´ an´ım tˇech kl´ıˇcov´ ych sekc´ı bychom dos´ahli mnohem efektivnˇejˇs´ıho vyuˇzit´ı ˇcasu i pamˇeti bˇehem crawling session, nebot’ bychom se vyhnuli zbyteˇcn´emu zpracov´ an´ı nadbyteˇcn´ ych dat. Kromˇe toho n´ aˇs crawler moment´alnˇe ignoruje hmtl syntax str´anky a vˇsem slov˚ um pˇriˇrazuje stejnou d˚ uleˇzitost. Pˇritom napˇr´ıklad se zv´ yraznˇenˇen´ ymi slovy a nadpisy by se mˇelo zach´ azet jinak neˇz s v´ yrazy, kter´e se vyskytuj´ı v bˇeˇzn´em textu.
7.5
Uˇ cen´ı
Je jasn´e, ˇze programovat crawler tak, aby se z nˇej stal plnohodnotn´ y vyhled´avaˇc, jako je napˇr. Google, asi nem´a smysl. My bychom se tedy potˇrebovali vydat takov´ ym smˇerem, abychom vytvoˇrili software, jeˇz bude budovat index specializovan´ y na urˇcit´e t´ema. Crawler by se tedy mˇel umˇet uˇcit (za podpory uˇzivatele)
42
indentifikovat takov´e str´ anky, kter´e jsou v dan´em t´ematu relevantn´ı. Jiˇz jsme zm´ınili tzv. beam search, coˇz je jedna z moˇznost´ı, jak pˇri vyhled´av´an´ı postupovat. Kromˇe toho je ale potˇreba implementovat nˇejakou heuristiku, kter´a by v kombinaci s pouˇzitou metrikou hodnocen´ı relevance str´anek crawleru smˇerovala k relevantn´ımu obsahu. Jiˇz jsme implementovali uˇcen´ı se nov´ ym stop words. Ted’ by mˇela pˇrij´ıt na ˇradu dalˇs´ı uˇcen´ı - oznaˇcen´ı relevantn´ıch str´anek, dynamick´e hodnocen´ı str´anek v pr˚ ubˇehu prohled´ av´ an´ı za pouˇzit´ı existuj´ıc´ıho indexu spoleˇcnˇe s implementac´ı prioritn´ı fronty, aby str´ anky, u kter´ ych je vyˇsˇs´ı pravdˇepodobnost obsahu relevantn´ıch informac´ı, byly staˇzeny pˇrednostnˇe. Souˇcasnˇe s t´ım by bylo tˇreba zmˇenit metriku z ˇcist´eho TF-IDF napˇr. na kombinaci TF-IDF a PageRanku, aby byla zohlednˇena i hyper-link struktura str´anek.
43
8
Z´ avˇ er
C´ılem t´eto bakal´ aˇrsk´e pr´ ace bylo navrhnout crawler, kter´ y bude schopen samostatnˇe vyhled´ avat informace na Webu a sv´e vyhled´av´an´ı zpˇresˇ novat na z´akladˇe interakce s uˇzivatelem. V prvn´ı kapitole je rozebr´ ana dneˇsn´ı podoba internetu a struˇcn´ yu ´vod do problematiky webcrawlingu. N´ asleduje pˇrehled technik pouˇz´ıvan´ ych pro c´ılen´e vyhled´ av´ an´ı informac´ı na Webu. Ve tˇret´ı kapitole n´asleduje pˇrehled zp˚ usob˚ u v´ ypoˇctu ˇ hodnocen´ı str´ anek na z´ akladˇe jejich relevance. Ctvrt´ a kapitola se vˇenuje nˇekolika pˇr´ıklad˚ um existuj´ıc´ıho softwaru vˇcetnˇe velk´ ych vyhled´avaˇc˚ u. Zbytek pr´ ace je vˇenov´ an popisu konkr´etn´ı implementace crawleru a prezentaci dosaˇzen´ ych v´ ysledk˚ u na tˇrech vyhled´avac´ıch sc´en´aˇr´ıch. Posledn´ı, sedm´ a, kapitola je vˇenov´ ana nast´ınˇen´ı dalˇs´ıho postupu, aby se z v´ ysledn´eho crawlera stal uˇziteˇcn´ y n´ astroj. Nyn´ı je ˇcas na shrnut´ı cel´e pr´ace. Podaˇrilo se vytvoˇrit funguj´ıc´ı implementaci, kter´ a samostatnˇe vyhled´av´a informace na Webu podle zadan´ ych specifikac´ı. Aplikace m´ a ale nˇekolik nedostatk˚ u, kter´e jiˇz byly zm´ınˇeny v pˇredchoz´ıch kapitol´ ach. Tou nejz´ avaˇznˇejˇs´ı je asi nutnost zapoˇc´ıt vyhled´av´an´ı pomˇernˇe bl´ızko hledan´eho t´ematu, aby byl v´ ystup relevantn´ı. To je d´ano hlavnˇe mal´ ym v´ ykonem, kter´ y je limitov´ an pouˇzit´ım crawlera na jedin´em poˇc´ıtaˇci. Vyhled´av´an´ı je pak tedy pˇr´ıliˇs pomal´e a neefektivn´ı. V sedm´e kapitole je ale pops´ano nˇekolik zp˚ usob˚ u, jak tohoto crawlera vylepˇsit a tyto nedostatky pˇrekonat. V souˇcasn´e dobˇe je tato aplikace vhodn´a pro podrobnˇejˇs´ı anal´ yzu stˇrednˇe velk´ ych kolekc´ı str´ anek (3 - 8 tis´ıc str´anek), pˇredevˇs´ım na lexikografick´em z´akladu. Kromˇe toho tento crawler produkuje ˇradu statistik t´ ykaj´ıc´ıch se v´ yskyt˚ u slov a podobnosti prohledan´ ych str´anek, coˇz z nˇej m˚ uˇze dˇelat n´astroj vhodn´ y pro zkoum´ an´ı struktury dneˇsn´ıho Webu. Tyto v´ ysledky si lze prohl´ednout na pˇriloˇzen´em CD. Jsem si vˇedom, ˇze nˇekter´e t´emata nejsou rozebr´ana pˇr´ıliˇs do hloubky. C´ılem pr´ ace bylo vytvoˇrit pˇrehled pouˇz´ıvan´ ych technik, kde podrobn´ y popis mnoh´ ych z nich by pˇrekroˇcil r´ amec t´eto pr´ace. Pr´ ace na tomto t´ematu mˇe velmi zaujala, bavila a byla pro mne velk´ ym pˇr´ınosem. Dozvˇedˇel jsem se o hlubˇs´ı podstatˇe c´ılen´eho vyhled´av´an´ı a jsem si jist, ˇze se mi z´ıskan´e poznatky budou hodit. Z´ avˇerem bych r´ ad podˇekoval Ing. Radku Maˇr´ıkovi, CSc. za veden´ı m´e bakal´aˇrsk´e pr´ ace a konzultace.
44
Reference [AKP06] G. Almpanidis, C. Kotropoulos, and I. Pitas. Combining text and link analysis for focused crawling-an application for vertical search engines. Inf. Syst., 32(6):886–908, September 2006. [Bos03]
Dustin Boswell. Distributed high-performance web crawlers: A survey of the state of the art. 2003.
[BP98]
Sergey Brin and Lawrence Page. The anatomy of a large-scale hypertextual web search engine. Comput. Netw. ISDN Syst., 30(1-7):107– 117, April 1998.
[BYC07] Ricardo Baeza-Yates and Carlos Castillo. Crawling the infinite web. J. Web Eng., 6(1):49–72, March 2007. [Cap03]
Carmela Cappelli. Identifying word senses from synonyms: a cluster analysis approach. 2003.
[FLT06]
Hwai-Hui Fu, Dennis K. J. Lin, and Hsien-Tang Tsai. Damping factor in google page ranking: Research articles. Appl. Stoch. Model. Bus. Ind., 22(5):431–444, September 2006.
[Hav02]
Taher H. Haveliwala. Topic-sensitive pagerank. In Proceedings of the 11th international conference on World Wide Web, WWW ’02, pages 517–526, New York, NY, USA, 2002. ACM.
[Lev06]
Mark Levene. An introduction to search engines and web navigation. addison wesley, pearson education (2006). isbn 0-321-306775. £39.99. 365 pp. softbound. Comput. J., 49(4):500–500, July 2006.
[LKS05]
Levon Lloyd, Dimitrios Kechagias, and Steven Skiena. Lydia: A system for large-scale news analysis. 2005.
[LZQZ03] Dekang Lin, Shaojun Zhao, Lijuan Qin, and Ming Zhou. Identifying synonyms among distributionally similar words. In Proceedings of the 18th international joint conference on Artificial intelligence, IJCAI’03, pages 1492–1493, San Francisco, CA, USA, 2003. Morgan Kaufmann Publishers Inc. [MM90]
Udi Manber and Gene Myers. Suffix arrays: a new method for online string searches. In Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, SODA ’90, pages 319–327, Philadelphia, PA, USA, 1990. Society for Industrial and Applied Mathematics.
[NOHI04] Saeko Nomura, Satoshi Oyama, Tetsuo Hayamizu, and Toru Ishida. Analysis and improvement of hits algorithm for detecting web communities. Syst. Comput. Japan, 35(13):32–42, November 2004. 45
[NW01]
Marc Najork and Janet L. Wiener. Breadth-first crawling yields highquality pages. In Proceedings of the 10th international conference on World Wide Web, WWW ’01, pages 114–118, New York, NY, USA, 2001. ACM.
[PSM04] Gautam Pant, Padmini Srinivasan, and Filippo Menczer. Crawling the web. In Mark Levene and Alexandra Poulovassilis, editors, Web Dynamics: Adapting to Change in Content, Size, Topology and Use, pages 153–178. Springer-Verlag, Berlin, Germany, November 2004. [SFK11]
Tom Seymour, Dean Frantsvog, and Satheesh Kumar. History of search engines. International Journal of Management & Information Systems, 2011.
[TN03]
Christoph Tillmann and Hermann Ney. Word reordering and a dynamic programming beam search algorithm for statistical machine translation. Comput. Linguist., 29(1):97–133, March 2003.
[YC01]
Mikio Yamamoto and Kenneth W. Church. Using suffix arrays to compute term frequency and document frequency for all substrings in a corpus. Comput. Linguist., 27(1):1–30, March 2001.
[ZH05]
Rong Zhou and Eric A. Hansen. Beam-stack search: Integrating backtracking with beam search. In Susanne Biundo, Karen L. Myers, and Kanna Rajan, editors, ICAPS, pages 90–98. AAAI, 2005.
46
Nastaven´ı parametr˚ u crawling session • Do pole seed URLs zadejte URL adresy str´anek (zad´avejte URL ve tvaru s ”http://”!), na kter´ ych crawler zaˇcne prohled´av´an´ı. Jednotliv´e adresy oddˇelujte kl´ avesou ENTER. Pokud zad´ate v´ıce neˇz jednu adresu, program vytvoˇr´ı pro kaˇzdou z nich jednu instanci crawler, kter´ y bude vyhled´avat nez´ avisle na ostatn´ıch v samostatn´em vl´aknˇe. V´ ysledky pak budou uloˇzeny pro kaˇzd´eho crawlera zvl´aˇst’. • Nastavte limit poˇctu prohledan´ ych str´anek. Nech´ate-li 0“, crawler bude ” prohled´ avat do t´e doby, dokud m´a nˇejak´e str´anky ve frontˇe, coˇz v pˇr´ıpadnˇe glob´ aln´ıho vyhled´ av´ an´ı m˚ uˇze i nekoneˇcnˇe dlouho. Pro z´atˇeˇz do 1GB se doporuˇcuje nastavit limit na 5000-10000 str´anek. • V pˇr´ıpadˇe, ˇze chcete nastavit opakov´an´ı session (pro c´ılen´e vyhled´av´an´ı spolu s nastaven´ım kl´ıˇcov´ ych slov), nastavte v poli number of crawling sessions cel´e ˇc´ıslo vˇetˇs´ı neˇz 1. Tato volba m´a smysl pouze, pokud v pokroˇcil´ ych nastaven´ıch (settings → advanced) zvol´ıte use requirements a v poli pod checkboxem nap´ıˇsete hledan´a slova oddˇelen´a kl´avesou ENTER. • Pokud si pˇrejete nastavit pouze lok´aln´ı vyhled´av´an´ı, zvolte v pokroˇcil´ ych nastaven´ı moˇznost search only local domains. • Nastavte cestu k adres´ aˇri, do kter´eho se budou ukl´adat v´ ysledky v settings → set directory. Pokud to neudˇel´ate, v´ ysledky se uloˇz´ı do sloˇzky de” fault“ ve stejn´em adres´aˇri, ze kter´eho jste crawler spustily. • Nastavte v settings → load stopwrods cestu k souboru se stop slovy, pokud si je pˇrejete pouˇz´ıt. • Stisknˇete tlaˇc´ıtko begin. • Pokud jste naˇcetli soubor se stop slovy, budete na konci session vyb´ıdnuti, abyste zvolili libovoln´ y poˇcet nejl´epe hodnocen´ ych slov na prohledan´ ych str´ ank´ ach, kter´e si pˇrejete pˇridat do vaˇseho souboru se stop slovy. • Pokud jste zvolili nˇejak´a hledan´a slova, m˚ uˇzete si v menu results pod´ıvat na nejl´epe hodnocen´e str´anky.
Nastaven´ı parametr˚ u klienta • Stisknˇete tlaˇc´ıtko load index a uved’te cestu do sloˇzky index vytvoˇren´e pˇri nˇekter´e minul´e crawling session. • Do pole v horn´ı liˇstˇe zadejte hledan´a slova a stisknˇete tlaˇc´ıtko search.
47
Pˇriloˇzen´e soubory • Thesis.pdf: elektronick´a verze t´eto pr´ace • Software: sloˇzka obsahuj´ıc´ı spustiteln´e .jar soubory (Webcrawler.jar, Client.jar) a soubor s n´ apovˇedou Help.pdf • Examples: sloˇzka obsahuj´ıc´ı tˇri uk´azkov´e v´ ystupy crawling session, kter´e byly pouˇzity k prezentov´an´ı v´ ysledk˚ u v kapitole 6. • Stopwords.txt: soubor se stop slovy
48