ČESKÉ VYSOKÉ UČENÍ TECHNICKÉv praze

fakulta elektrotechnická

katedra kybernetiky

Ćılené vyhledáváńıinformaćı na webu

BAKALÁŘSKÁ PRÁCE

Obor: Informatika a poč́ıtačové vědyAutor: Martin Mysĺık

Program: Otevřená informatikaVedoućı práce: Ing. Radek Mař́ık, CSc.

Praha, 2013

1

České vysoké učení technické v PrazeFaku lta elektrotech nická

Katedra kybernetiky

zADÁNí enxnlÁŘsrÉ pnÁce

Student: Martin Myslík

Studijní program: Otevřená informatika (bakalářský)

Obor: lnformatika a počítačové vědy

Název tématu: Cílené vyhledávání informací na webu

Pokyny pro vypracováni:

1. Vytvorte přehled současných technik a metod cíleného vyhledávání informací na webu,2, Naimplementujte prototyp vyhledáváníwww stránek týkajícíse problematiky a vyzkoušejte

na něm vybrané metody.3. Zhodnotte dosažené výsledky a navrhněte další postup práce,

Seznam odborné literatury:[1] Mark Levene: An lntroduction to Search Engines and Web Navigation. Second edition,

John Wiley & Sons, New Jersey,2010.[2] George Almpanidis, Constantine Kotropoulos, loannis Pitas: Combining text and link

analysis for focused crawling - An application for vertical search engines. lnf. Syst. 32(6):886-908 (2007)

[3] Zdravko Markov and Daniel T. Larose: Data Mining the Web: Uncovering Patterns in WebContent, Structure, and Usage. Wiley, New Britain , CT,2007.

[4] Raymond Kosala, Hendrik Blockeel:Web Mining Research: A Survey. ln ACM SIGKDD,July 2000.

Vedoucí bakalářské práce: lng. Radek Mařík, CSc.

Platnost zadání: do konce zimního semestru 2O13l2O14

*udimír Mařík, DrSc.

vedďucí katedry

Y Praze dne 10. 1.2013

3

Anotace

Tématem bakalářské práce je ćılené vyhledáváńı informaćı na internetu. Práceobsahuje teoretický rozbor dnešńı podoby Webu, představuje stručný přehledtechnik použ́ıvaných k jeho prohledáváńı a popisuje konkrétńı implementaciprogramu, který je zaměřen na ćılené vyhledáváńı informaćı.

Internet je v dnešńı době bezpochyby nejrozsáhleǰśı zdroj informaćı dostupnýchčlověku. V posledńıch dvou desetilet́ı došlo k jeho tak rapidńımu r̊ustu, že vy-hledáváńı relevantńıch stránek se stalo specializovanou discipĺınou. Nejpouž́ıvaněǰśıa nejpohodlněǰśı zp̊usob vyhledáváńı na Webu jsou jistě internetové vyhledávače.Ty k prohledáváńı stránek použ́ıvaj́ı crawlery, tedy poč́ıtačové programy pro au-tomatizované indexováńı stránek.

Hlavńım ćılem práce bylo vytvořit takový program, který uživateli pomůže vy-hledat konkrétńı informace na internetu bez nutnosti toho, aby byl uživatelběhem tohoto procesu fyzicky př́ıtomen, př́ıpadně alespoň poṕı̌se postup, kterýby výsledný program tomuto ćıli přibĺıžil.

Kĺıčová slova: internet, web crawling, crawler, focused crawler, vyhledáváńı,vyhledávač, hodnoceńı stránek, information retrievel

Abstract

The topic of this thesis is focused on Internet search methods. At first, a theore-tical background, including the current structure of the Internet and techniquesused for information retrieval, are presented. After that, a simple implemen-tation of a program used for focused crawling is analysed.

Internet is without doubt the biggest information source available at the mo-ment. There has been a huge growth in the size of the Web in the last two deca-des and information retrieval has become very important. Using various searchengines is probably the most convenient way of searching information onlinetoday. These search engines use crawlers, specialized computer programs, forautomatic indexing of web pages.

The main goal of this project is to create a crawler that will assist the userwith searching for high quality information sources without the need of beingphysically present to this process.

Keywords: internet, web crawling, crawler, focused crawler, information re-trieval, search engine, page ranking

4

Obsah

1 Úvod 71.1 Ćıle projektu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71.2 Dnešńı podoba internetu . . . . . . . . . . . . . . . . . . . . . . . 71.3 Webcrawling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

2 Přehled technik použ́ıvaných pro webcrawling 112.1 Základńı cyklus . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112.2 Prohledáváńı . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112.3 Beam search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142.4 Parsováńı . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142.5 Suffixová pole . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152.6 Škálovatelnost . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

3 Hodnoceńı stránek 173.1 TF-IDF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173.2 Latent semantic indexing (LSI) . . . . . . . . . . . . . . . . . . . 193.3 PageRank . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203.4 HITS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

4 Existuj́ıćı software 234.1 Google . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234.2 Yahoo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244.3 Lydia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254.4 Daľśı boti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254.5 Focused crawlery . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

5 Implementace crawleru 275.1 Popis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 275.2 Pr̊uběh session . . . . . . . . . . . . . . . . . . . . . . . . . . . . 275.3 Reprezentace dat a struktura . . . . . . . . . . . . . . . . . . . . 285.4 Výstup crawleru . . . . . . . . . . . . . . . . . . . . . . . . . . . 305.5 Stop words . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 315.6 Problémy implementace . . . . . . . . . . . . . . . . . . . . . . . 315.7 Budováńı indexu . . . . . . . . . . . . . . . . . . . . . . . . . . . 315.8 Struktury indexu . . . . . . . . . . . . . . . . . . . . . . . . . . . 325.9 Klient . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

6 Prezentace výsledk̊u 336.1 Př́ıklad 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 336.2 Př́ıklad 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 366.3 Př́ıklad 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

5

7 Navržeńı daľśıho postupu 417.1 Práce s daty a výkon . . . . . . . . . . . . . . . . . . . . . . . . . 417.2 Aktualizace indexu . . . . . . . . . . . . . . . . . . . . . . . . . . 417.3 Podpora jazyk̊u . . . . . . . . . . . . . . . . . . . . . . . . . . . . 427.4 Rozpoznáváńı struktury stránek . . . . . . . . . . . . . . . . . . 427.5 Učeńı . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

8 Závěr 44

6

1 Úvod

1.1 Ćıle projektu

Ćılem projektu je vyzkoušet, jak efektivně vyhledávat informace na internetupomoćı jeho prozkoumáváńı (webcrawling) a následnou analýzou nalezenéhotextu. Rozebereme, jak postavit crawler1 tak, aby se byl sám schopen pohybovatmezi jednotlivými stránkami a sb́ırat informace. Vysvětĺıme jeho architekturua na co si dát při psańı programu pozor.

Část práce bude zaměřena na to, jak naložit se źıskanými daty. Poṕı̌seme r̊uznézp̊usoby hodnoceńı stránek na základě analýzy jejich obsahu, a jejich výhody anevýhody v naš́ı implementaci. Mimo jiné se zaměř́ıme i na to, č́ım se lǐśı nášcrawler od jiných, široce využ́ıvaných, bot̊u.

1.2 Dnešńı podoba internetu

Internet je bezpochyby největš́ım úložǐstěm dat, které je dnes člověku př́ıstupno.Odhad počtu indexovaných stránek je v současné době cca 7,65 bilion̊u2. Skutečnéč́ıslo bude ale mnohonásobně větš́ı, nebot’ toto jsou pouze ty stránky, kterébyly označeny internetovými vyhledávači. Nav́ıc ještě značná část dat neńı vy-hledávač̊um př́ımo př́ıstupna, protože je ukryta ve vnitřńıch databáźıch, jednáse o tzv. skrytý internet (invisible web). Odhaduje se, že tato část webu bymohla být až 550krát3 větš́ı, než data př́ımo př́ıstupná na internetu.

Skutečný počet stránek na internetu by v současné době mohl přesáhnout i je-den trilion, nebot’ internetové vyhledávače pokrývaj́ı jen malou část př́ıstupnéhointernetu. Toto č́ıslo je ale velmi těžké ověřit, protože významná část webu jetvořena dynamicky vytvářenými stránkami.

Mnohem větš́ı vypov́ıdaj́ıćı hodnotu než celkový počet stránek má ale početwebsites. Ke změřeńı jejich počtu nám stač́ı identifikovat jen domovskou stránkukaždé z nich a následně seč́ıst tyto stránky. Roku 2010 bylo spočteno, že exis-tuje 113,9 milion̊u registrovaných komerčńıch websites. Toto č́ıslo nám asi přesnýpočet stránek určit nepomůže, protože r̊uzné stránky mohou vlastnit i několikdomén, ale dává nám alespoň hrubý odhad4.

Kromě”velikosti“ internetu je ještě zaj́ımavé zmı́nit jeho strukturu. Kdybychom

vzali všechny stránky na internetu, nanesli je na velkou plochu v podobě bod̊ua následně mezi nimi vyznačili odkazy, dostali bychom graf zobrazuj́ıćı celou śıt’

(obr. 1).

1Webcrawler je poč́ıtačový program, který automaticky prohledává internet2http://www.worldwidewebsize.com/3http://aip.completeplanet.com/4http://www.whois.sc/internet-statistics/

7

Obrázek 1: Př́ıklad mapy části internetu z roku 2005, zdroj:http://en.wikipedia.org/

Ačkoli by se mohl člověk z obrázku domńıvat, že internet je vlastně jedna velkáspojitá struktura, ve skutečnosti tomu tak neńı. Studie5 ukázala, že v 75%př́ıpad̊u neexistuje žádná cesta z jedné náhodně vybrané stránky na druhou, akdyž už taková cesta existuje, vzdálenost těchto stránek je cca 16 kliknut́ı. Vı́ceo struktuře webu se lze doč́ıst v knize od M. Levene[Lev06].

Daľśı, co je nutné zmı́nit v úvodu do problematiky webcrawlingu, je dynamickástruktura webu. Web je většinou považován, za soubor stránek, z čehož vyplývá,že graf Webu má konečně mnoho uzl̊u. To ale neńı tak docela pravda, Pokud za”webovou stránku”považujeme všechno, co má URL adresu použ́ıvaj́ıćı HTTPprotokol, tak ačkoli je množstv́ı informaćı na Webu konečné, počet stránek je ne-

5Studii provedli roku 1999 odborńıci z IBM, Compaq a AltaVista

8

konečný. Existuj́ı miliony dynamických webových stránek, které obsahuj́ı linkyna daľśı dynamicky generované stránky, z čehož se dá usuzovat, že Web je vpodstatě nekonečný.

Většina studíı zabývaj́ıćıch se Webem pojednává pouze o ”veřejně dostupné”částiinternetu, aniž by brala v potaz ”skrytý Web”(viz výše). Neindexovatelná částje charakterizována jako všechny stránky, ke kterým se normálńı uživatelé maj́ıšanci dostat, ale crawlery6 použ́ıvané vyhledávači ne. Některé stránky nejsouindexovatelné, protože vyžaduj́ı registraci uživatel̊u nebo jinou autorizaci. Jinémohou umožňovat př́ıstup pouze v určité śıti (např. firemńı intranet). Daľśı sku-pinu tvoř́ı dynamicky vytvářené stránky po zadáńı požadavk̊u. Crawler nemuśıznát parametry těchto požadavk̊u. Různé části Webu si můžete prohlédnout naobr. 2.

Obrázek 2: Web může být rozdělen na části chráněné heslem a veřejně př́ıstupnéčásti, a dynamické a statické stránky[BYC07]

1.3 Webcrawling

Webcrawler je program, který automaticky procháźı Web a stahuje jednotlivéstránky. Na každé stránce najde odkazy (links), které následuje. Většinou jsoutyto programy použ́ıvány vyhledávači k indexováńı webových stránek. Mezi daľśımožné aplikace patř́ı validace stránek, strukturálńı analýza a vizualizace obsahu,upozorněńı na změny na stránce, ale i řada zlomyslných uplatněńı - např. sb́ıráńımailových adres za účelem roześıláńı spamu. Webcrawlers tvoř́ı centrálńı částvyhledávač̊u. Jsou nutné k tomu, aby databáze prohledaných stránek byla co

6Při psańı české verze této práce jsem jen s obt́ıžemi hledal český ekvivalent slova ”crawler”-proto budu tento výraz skloňovat takovým zp̊usobem, jaký mi přijde nejpřirozeněǰśı

9

nejaktuálněǰśı, a jejich architektura je většinou považována za obchodńı tajem-stv́ı.

My se ted’ pod́ıváme na základńı typy takovýchto programů:

General-purpose crawlerTyto crawlery sb́ıraj́ı a zpracovávaj́ı obsah Webu kolem nějakého centralizo-vaného mı́sta tak, aby bylo možné indexovat jednotlivé stránky dopředu, cožumožńı rychlé odpovědi na mnoho uživatelských dotaz̊u. V počátćıch, když Webještě nebyl př́ılǐs rozsáhlý, náhodné prohledávaćı metody byly postačuj́ıćı proindexováńı všech stránek. Nyńı je ale Web př́ılǐs obsáhlý a my muśıme dělatřadu kompromis̊u: Crawler může mı́t dobré pokryt́ı ale ńızkou obnovovaćı frek-venci (tzn. jeho index může být zastaralý). Nebo může být obnovovaćı frekvence(refresh rate) vysoká, ale za cenu horš́ı hodnot́ıćı funkce (ranking function),či může chybět zpracováńı složitěǰśıch dotaz̊u, které potřebuj́ı vyšš́ı výpočetńıvýkon.

To je také d̊uvodem, proč s rychlou expanźı webu tyto crawlery a obecné vy-hledávaćı systémy pokrývaj́ı stále menš́ı fragment celkového počtu všech webovýchstránek a na oblibě nabývaj́ı specializované (focused) vyhledávaćı systémy7.

Focused crawlerTvorba těchto bot̊u byla motivována faktem, že Web obsahuje nepopsatelněmnoho informaćı, ale většina lid́ı se zaj́ımá pouze o jejich malinký zlomek. Ćılemtěchto programů je prohledáváńı pouze malé části Webu a nalezeńı stránek, kterése zabývaj́ı požadovaným tématem. Takový crawler může mı́t mnoho podob: kla-sický focused crawler (dostane zadané počátečńı URL, seznam hledaných výraz̊ua procháźı stránky, dokud nenalezne, co hledáme), learning crawlers (spolupra-cuje s uživatelem, který označuje stránky jako relevantńı a irelevantńı, aby zlepšilvýkon programu pro budoućı použit́ı) a mnoho daľśıch.

Chováni crawleru je charakterizováno kombinaćı několika strategíı8:

• selection policy - určuje, které stránky stahovat

• re-visit policy - určuje, kdy kontrolovat změny na stránkách

• politeness policy - určuje, jak se vyhnout přet́ıžeńı jednotlivých stránek,resp. server̊u

• parallelization policy - určuje, jak koordinovat jednotlivé crawlery, pokudjich je v́ıce než jeden

7též Vertical search engines8Některé výrazy týkaj́ıćı se tohoto tématu nemaj́ı uspokojivý český ekvivalent, proto

nechám jejich zněńı v Angličtině

10

2 Přehled technik použ́ıvaných pro webcrawling

V této kapitole se budeme zabývat t́ım, jaké techniky se daj́ı použ́ıt při im-plementaci samotného crawleru. Nebudeme dělat přehled všech problémů, sekterými se při psańı programu člověk setká, ale uděláme stručný výčet pouzetěch nejzaj́ımavěǰśıch.

2.1 Základńı cyklus

Každé prohledáváńı se skládá z několika základńıch krok̊u. Session většinouzač́ıná inicializaćı nějakých startovaćıch URL (seed URLs, často zadány uživatelem).Všechny tyto URl se ulož́ı do listu stránek, které čekaj́ı na zpracováńı (Openlist/frontier a jsou postupně stahovány a parsovány, dokud neńı list prázdnýnebo nenastala nějaká terminačńı podmı́nka. Pr̊uběh session se dá zjednodušeněznázornit takto:

Obrázek 3: Pr̊uběh crawling session[PSM04]

2.2 Prohledáváńı

Při crawlingu je d̊uležité, jakou strukturu si zvoĺıme pro list obsahuj́ıćı URLstránek, které se teprve chystáme prohledat. Těmi nejzákladněǰśımi z nich jsou

11

fronta a zásobńık.

ZásobńıkZásobńık funguje na principu LIFO (last in, first out). Jinými slovy: posledńıURL, kterou na dané stránce najdeme, navšt́ıv́ıme jako prvńı. Z ńı opět sepa-rujeme všechny odkazy a zařad́ıme je na vršek zásobńıku. Jedná se tedy o DFSprohledáváńı (depth-first search).

Obrázek 4: DFS - prohledáváńı do hloubky

Zjevnou nevýhodou tohoto postupu je, že stránky většinou obsahuj́ı obrovskýpočet odkaz̊u, a pokud začneme prohledávat nějakou neperspektivńı větev, můžemese snadno dostat mimo stránky, které souviśı s hledaným tématem.

FrontaFronta, oproti zásobńıku, funguje na principu FIFO (first in, first out). Při jej́ıaplikaci se tedy bude jednat o BFS prohledáváńı (breadth-first search).

Obrázek 5: BFS - prohledáváńı do š́ı̌rky

Tento postup je evidentně efektivněǰśı. Při správně zvoleném seed URL bu-

12

deme mı́t větš́ı šanci se dobrat použitelných výsledk̊u, protože se nám nestane,že během prohledáváńı se crawler dostane zbytečně hluboko na stránky, kteréjsou od p̊uvodńıho tématu velmi vzdálené. Použijeme tedy frontu. Mimo tov roce 2001 vyšlo shrnut́ı studie, která porovnávala prohledáváńı do š́ı̌rky ado hloubky (a daľśı) na 328 milionech unikátńıch stránek s použit́ım algoritmuPageRank jako kriteriálńı funkce[NW01]. Kvalitu daného řazeńı byla hodnocenapodle toho, jak rychle daný algoritmus vyhledá všechny ”kvalitńı”stránky (tj.stránky s nejvyšš́ı hodnotou PageRank funkce9). Výsledky tohoto testu ukázaly,že prohledáváńı do š́ı̌rky stáhne kvalitńı stránky jako prvńı a kvalita nalezenýchstránek se postupně (tedy s každou daľśı úrovńı) snižuje. Nav́ıc tato metodaméně zatěžuje servery.

Omezeńı vyhledáváńıDaľśı otázkou, kterou je nutno řešit, je jak dlouho nechat crawler prohledávat.Vzhledem k tomu, kolik je na webu stránek, by při zvoleńı určitých seed URLsmohlo prohledáváńı trvat nepř́ıjemně dlouho (př́ıpadně skončit kv̊uli nedostatkuvýpočetńıho výkonu). Muśıme proto naši session shora omezit. Nab́ıźı se hnedtři možnosti: určit čas, který má crawler k dispozici, nastavit fixńı hloubkuprohledávaćıho stromu nebo určit limit počtu navšt́ıvených stránek. Bude tedyrozumné rozhodnout se pro posledńı jmenované, protože narozd́ıl od prvńıchdvou možnost́ı nám zaruč́ı pokaždé stejný počet prohledaných stránek.

Daľśı věc, se kterou se budeme potýkat, je opakováńı stejných URL adres. Jepravděpodobné, že pokud prozkoumáváme okoĺı nějaké seed URL pomoćı BFS,jednotlivé stránky budou mezi sebou provázané, a my nechceme žádnou stránkunavšt́ıvit dvakrát. Bude proto třeba vytvořit Close list, do kterého ulož́ıme je-jich adresy. Vhodnou strukturou je d́ıky rychlému př́ıstupu a snadné manipulaciHashmap.

Některé objekty na webu nejsou HTML stránky, ale tvoř́ı je např. obrázky,PDF a jiné nestandardńı typy soubor̊u. Takové stránky můžeme bud’ úplněignorovat nebo s nimi pracovat. Naše implementace např. podporuje ukládáńıpdf soubor̊u (leč jej́ıch zpracováńı vyžaduje odlǐsný a náročněǰśı př́ıstup než uHTML stránek) a ignoruje ostatńı typy soubor̊u.

Daľśı možnostiKromě zásobńıku a fronty máme ještě daľśı možnosti, jak zvolit pořad́ı staho-vaných stránek. Jedńım z nich je např́ıklad prioritńı fronta nebo backlist or-dering, ve kterém jako prvńı stahujeme stránky s nejvyšš́ım ratingem. Je tedynutné zvolit metriku, podle které budeme určovat kvalitu stránek (HITS, Page-Rank . . . ) a následně přepoč́ıtávat rating všech nově stažených stránek.

9Vı́ce o algoritmu PageRank v daľśıch kapitolách

13

2.3 Beam search

Beam search je zvláštńı druh prohledáváńı, který buduje strom pomoćı pro-hledáváńı do š́ı̌rky, ale rozšǐruje v každém patře pouze omezený počet nejlépehodnocených uzl̊u. Pokaždé tedy ohodnot́ı všechny uzly v právě prohledanéúrovni, seřad́ı je a vybere n nejlepš́ıch, ve kterých pak pokračuje ve vyhledáváńı.Č́ıslo n označuje jako beam width. Tento algoritmus neńı úplný10, nebot’ op-timálńı stav nemuśı být nalezen, ale je pamět’ově efektivněǰśı, protože nemuśımebudovat celý strom jako při klasickém prohledáváńı do š́ı̌rky.

Existuje ale i varianta tohoto algoritmu, která je úplná. Pokud do beam searchzavedeme backtracking, pak máme možnost zajistit, že při prohledáváńı vždynalezneme optimálńı stav. To popsali roku 2005 vědci z univerzityv Mississippi[ZH05].

Tento algoritmus je často použ́ıván např́ıklad v systémech strojových překlad̊u.Každé slovo lze přeložit mnoha zp̊usoby, ale vybere se jen ten, který nejlépeodpov́ıdá struktuře věty. To je dobře popsáno např. ve studii, která byla pro-vedena roku 2003 v IBM T. J. Watson Research Center[TN03]. My použ́ıvámesvým zp̊usobem také jistou formu beam search, a to v př́ıpadě opakované craw-ling session. Prohledáváme během jednotlivých session stránky do š́ı̌rky a potévybereme n nejlepš́ıch výsledk̊u a použijeme je jako seed URLs pro daľśı session.

2.4 Parsováńı

Jakmile je stránka stažena, je načase ji rozparsovat11. Na stránce můžeme např.hledat pouze odkazy, př́ıpadně pak daľśı obsah.

Často nás na stránce zaj́ımá nějaká konkrétńı část, ke které se budeme snažit do-stat. V takovém př́ıpadě je nutné prohledat celý strom HTML tag̊u (HTML/tagtree), abychom se k hledanému obsahu dostali. V naš́ı implementaci crawleruse HTML parsováńım nezabýváme, protože stahujeme a analyzujeme veškerýtextový obsah stránky, nicméně pokládám za d̊uležité toto téma zmı́nit. Přistažeńı stránky muśıme nejdř́ıve upravit stránku do takové podoby, abychommohli vygenerovat strom, ve kterém bude každý uzel mı́t jednoho rodiče. Nastránkách např́ıklad mohou chybět některé povinné tagy (< html >,< body >apod.), které je nutné doplnit. Následně je možné rekonstruovat celou strukturuv podobě stromu a analyzovat třeba jen některé uzly, ve kterých se vyskytuj́ırelevantńı informace.

Za jistý druh parsováńı se dá považovat i rekonstrukce nalezených URL. Vmnohých př́ıkladech mohou být odkazy napsané v nestandardńım tvaru, kterýmuśı být upraven, abychom daný odkaz mohli použ́ıt. Mezi takové úpravypatř́ı: převedeńı odkazu na malá ṕısmena, odstraněńı tzv. ”anchor”část́ı (část

10complete11česky např. ”rozložit”

14

URL za # symbolem), doplněńı zpětných lomı́tek, př́ıpadně odstraněńı těchpřebývaj́ıćıch, odstraněńı ”..”z odkazu a vygenerováńı patřičné URL v úplnémtvaru a daľśı.

2.5 Suffixová pole

V této sekci krátce rozebereme metodu suffixových poĺı, která patř́ı k použ́ıvanýmtechnikám při prohledáváńı dlouhých text̊u. Suffixová pole jsou technika použ́ıvanápři online vyhledáváńı typu ”Je W substring12 A? Dı́ky této technice jsmeschopni na tuto otázku odpovědět v čase O(P + logN), kde P je délka W a Nje délka A, což je ve většině př́ıpad̊u kratš́ı čas, než u suffix tree algoritmů.

Suffixové pole je vlastně seřazený list všech suffix̊u13 nějakého textu A. Po-kud toto pole spárujeme s informaćı o nejdeľśıch běžných prefixech (lcp - leastcommon prefixes) sousedńıch slov v našem suffixovém poli, pak hledáńı řetězc̊uv textu dosáhne již zmı́něné složitosti O(P + logN) (např. pomoćı binárńıhovyhledáváńı).

Nejprve se ve zkratce pod́ıváme, jak prob́ıhá vyhledáváńı za předpokladu, žesuffixové pole již bylo sestaveno. Necht’ A = a0, . . . , aN−1 je text o délce N .Necht’ Ai = ai, . . . , aN−1 je suffix A, který zač́ıná na pozici i - konkrétně Pos[k]je počátečńı pozice k-tého nejmenš́ıho suffixu v A. Pro všechny prvky pole Posplat́ı, že APos[0] < APos[1] < · · · < APos[N−1], kde < je lexikografické řazeńı.Dále pro řetězec u definujeme up jako prefix, který se skládá z p prvńıch sym-bol̊u u. Definujeme i relace p,≤p,≥p jako lexikografické řazeńı prefix̊u o pprvćıch.

Pokud chceme vyhledat všechny instance řetězce W = w0, . . . , wp−1 v A, kdep ≤ N , pak provedeme následuj́ıćı: Necht’ LW = min(k : W ≤p APos[k] ork = N) a RW = max(k : APos[k] ≤p W or k = −1). Dı́ky tomu, že naše poleW je lexikograficky seřazené, plat́ı, že pro každé i = Pos[k] je k ∈ [LW , RW ].Takže pokud, dokážeme rychle naj́ıt LW a RW , pak počet shodných řetězc̊u,které najdeme je RW − LW + 1 a jejich levé koncové pozice jsou dány jakoPos[LW ], . . . , Pos[RW ]. Nav́ıc d́ıky řazeńı ≤p jsme schopni LW a RW naj́ıt me-todou porovnáńı řetězc̊u v časeO(logN), kde každé porovnáńı vyžadujeO(logP )operaćı. T́ım pádem jsme schopni v poli Pos vyhledat všechny výskyty řetězcev čase O(PlogN).

Nyńı se pod́ıváme, jak se takové suffixové pole sestavuje. Vylepšeńı pomoćısestavováńı lcp zde rozeb́ırat nebudeme, nebot’ to neńı předmětem této práce.Řazeńı prob́ıhá v nejhorš́ım př́ıpadě v log2(N + 1) fáźıch. V prvńı fázi seřad́ımesuffixy skupin podle jejich prvńıho symbolu. Poté stejným zp̊usobem děĺıme tytoskupiny podle dvojnásobného počtu následuj́ıćıch symbol̊u. Pro zjednodušeńı

12podřetězec13angl. připona, v textu ale nebudu překládat

15

označ́ıme tyto fáze 1, 2, 4, 8 atd. abychom t́ım vyznačili počet ovlivněných sym-bol̊u. Takže fáze H-tá fáze znač́ı, že jsme provedli řazeńı do stupně leqH . Dáleještě dopńıme všechny suffixy mezerami tak, aby jejich délka byla N + 1.

V prvńı fázi máme pole Pos seřazeno podle prvńıch symbol̊u a v daľśım poli siuchováváme logické hodnoty, které označuj́ı děleńı suffix̊u do m1 skupin. PolePos bude stále v́ıce seřazené a v H-té fázi budou suffixy rozřazeny do mH sku-pin, kde v každé budou suffixy se stejnými H prvńımi symboly, a nav́ıc jsou vrámci každé skupiny suffixy seřazeny do stupně ≤H .

Podrobněǰśıho postup při tvořeńı a použit́ı suffixových poĺı se lze doč́ıst např. v[MM90] nebo [YC01]. Hlavńı výhodou této metody je nižš́ı výpočetńı složitosti úspora mı́sta na disku, protože nemuśıme uchovávat všechny texty a řetězcev poĺıch, ale stač́ı nám pouze hlavńı text a několik poĺı č́ısel, které symbolizuj́ıukazatele do něj.

2.6 Škálovatelnost

Při masivńım crawlingu by se boti měly d́ıvat do souboru ”robots.txt”, kterýje umı́stěn v root adresáři téměř každé větš́ı stránky. Podle něho se zjist́ı, zdamůže být daná stránka v̊ubec prohledávána. Dále by se mělo předej́ıt tomu, abybyl server zahlcen dotazy ke stažeńı stránek, což se může lehce stát, pokud se kněmu snaž́ı připojit velké množstv́ı crawler̊u najednou.

Implementace jednoduché verze crawleru, který pouze stahuje a ukládá obsahstránek je poměrně triviálńı. Pokud ale chceme vybudovat systém, který byzpracovával větš́ı množstv́ı stránek (jako to dělaj́ı např. webové vyhledávače),máme před sebou nesnadný úkol. Pr̊uměrná velikost jedné stránky je cca 20KB(miliarda stránek pak může mı́t i 20 000GB), takže je nutné celý obsah ukládatna distribuované śıti poč́ıtač̊u nebo podobném obrovském úložǐsti.

Nejd̊uležitěǰśım úkolem je ale navržeńı systému pro koordinaci velkého množstv́ıcrawler̊u. Podrobně se t́ımto tématem zabývá např. studie z roku 2003[Bos03].

16

3 Hodnoceńı stránek

V této kapitole se zaměř́ıme na to, jak naložit se źıskanými daty. Existujemnoho zp̊usob̊u jak hodnotit stránky a řadit je podle obsahu od nejlepš́ı ponejhorš́ı (resp. podle relevance). Zde postupně poṕı̌seme několik z nich se všemivýhodami a nevýhodami.

V prvńı řadě je nutné zmı́nit, že je rozd́ıl mezi pojmy data retrievel a infor-mation retrievel (IR). Předpokládejme, že uživatel do vyhledávače zadá nějakýdotaz (query). V data retrievel hledáme v dokumentech přesnou shodu - toznamená, že ověřujeme, zda se daná informace v dokumentu nacháźı či ne. Vinformation retrievel hledáme ty dokumenty, které alespoň částečně vyhovuj́ızadanému dotazu a následně z nich vybereme ty s nejlepš́ı shodou.

Dř́ıve pracovaly strategie IR na principu lexikálńıho porovnáńı dotazu, kterýse skládal z malého množstv́ı kĺıčových slov (keywords), s dokumenty a jejichindexovanými slovy. Většina vyhledávač̊u nyńı ale pracuje ještě s hyperlinko-vou strukturou dokument̊u, což je dnes s velkým počtem webových stránek jižtakřka nutnost́ı. Velmi dobrým přehledem těchto technik je např́ıklad článek zeScienceDirect od autor̊u z řecké univerzity v Thessaloniki[AKP06].

3.1 TF-IDF

TF-IDF, neboli Term Frequency - Inverse Document Frequency, je zp̊usob hod-noceńı stránek na základě relevance nalezeného textu. Náš crawler tento algo-ritmus implementoval formou nećıleného i ćıleného vyhledáváńı. Pokud tedyspust́ıme crawling session bez jakékoli specifikace hledaných výraz̊u, spust́ı seprávě tato forma hodnoceńı. Idea je, že stránky, které obsahuj́ı v́ıce relevantńıch(jakkoli) informaćı se objev́ı nahoře ve výsledćıch.

TF složka vyjadřuje, jak často se výraz vyskytuje v dokumentu z databáze.Většinou se normalizuje vyděleńım délkou (počtem slov) dokumentu, aby sepředešlo nadhodnocováńı dlouhých dokument̊u, ve kterých se výraz může vysky-tovat častěji než v kratš́ıch, aniž by byl dokument relevantněǰśı. T́ım źıskávámenásleduj́ıćı definici tf:

tfi,j = Ni,j (1)

kde Ni,j je počet výskut̊u výrazu i na stránce j. Při normalizaci se většinoupouž́ıvá Euklidovská norma.

Idf složka reprezentuje ”d̊uležitost”slova (tento termı́n ale berme s rezervou,viz dále). Č́ım častěji se slovo vyskytuje v dokumentech, t́ım méně je d̊uležité(slovo, které se vyskytuje ve všech dokumentech je většinou pro vyhledáváńınepoužitelné). Idf pro slovo i spoč́ıtáme podle vzorce:

17

idfi = logN

Ni, (2)

kde N je celkový počet stránek a jmenovatel vyjadřuje počet stránek, na kterýchse vyskytuje výraz i.

Ze vzorc̊u14 vyplývá, že slovo, které se vyskytuje na všech stránkách, bude mı́tnižš́ı hodnotu IDF a tud́ıž bude hodnoceno méně, než slovo, které se vyskytujevýjmečně. Stránky s větš́ım počtem unikátńıch výraz̊u by proto mohly obsa-hovat relevantněǰśı informace, než ostatńı, které obsahuj́ı jen ńızce hodnocenáslova.

V naš́ı implementaci jsme napoč́ıtali TF-IDF hodnotu pro vektor všech slovnapř́ıč prohledanými stránkami a to samé jsme udělali pro vektory slov na jed-notlivých stránkách. Relevanci obsahu pak spoč́ıtáme jako kosinovou vzdálenost15

těchto vektor̊u (tj. kosinovou vzdálenost hodnoceńı slov na dané stránce a vek-toru všech nalezených slov). Použijeme vzorec:

cosθ =dq

‖d‖‖q‖, (3)

kde d je vektor TF-IDF hodnocené stránky, q je vektor TF-IDF všech nale-zených slov.

Tato metoda jde samozřejmě použ́ıt i pro ćılené vyhledáváńı. Rating jednot-livých stránek je dán součtem TF-IDF hodnoceńı hledaných slov, které stránkaobsahuje. TF-IDF se v praxi použ́ıvá velmi často (v r̊uzných modifikaćıch) spolus page-rank algoritmy.

Tento zp̊usob hodnoceńı stránek (pokud je použit samostatně) má ale řadunevýhod. Jak jsme již uvedli, pojem ”d̊uležitost slova”je nutno brát s rezervou.TF-IDF mı́ra pro výraz i na stránce j (ai,j = tfi,jidfi) kombinuje dva r̊uznéprostory (prostor slov v TF a prostor stránek v IDF)16. Pro danou hodnotuIDF je vztah ai,j a tfi,j lineárńı, ale slovo, které se na stránce j vyskytuje x-krát nemuśı (a pravděpodobně ani neńı) x-krát relevantněǰśı, než slovo, které sena dané stránce vyskytuje jen jednou.Když se pod́ıváme na vztah IDF a TF-IDF, tak zjist́ıme, že IDF také nemážádnou spojitost s relevanćı slov. Je to vlastně logaritmický odhad, že náhodněvybraná stránka ni z kolekce stránek N bude obsahovat slovo i.

Důležitost slova v dokumentu záviśı na spoustě faktor̊u, jako např. význam,entropie (množstv́ı informace, kterou obsahuje), ale i uživatelské dotazy na totoslovo. TF-IDF samo o sobě nezohledňuje žádný z těchto faktor̊u. Neposledńı

14Vzorečky převzaté z http://www.ardendertat.com/2011/07/17/how-to-implement-a-search-engine-part-3-ranking-tf-idf/

15Cosine distance16http://irthoughts.wordpress.com/2008/07/07/understanding-tfidf/

18

nevýhodou implementace tohoto hodnoceńı je i výpočetńı složitost, protože jenutné jednak sb́ırat informace o výskytech slov na jednotlivých stránkách, alenav́ıc ještě po skončeńı session proj́ıt všechny stránky znovu spoč́ıtat IDF. Ipřesto se ale TF-IDF hojně použ́ıvá (a výpočet kosinových podobnost́ı), protožev kombinaci s daľśımi př́ıstupy přináš́ı velmi slušné výsledky a je stále méněnáročné než jiné mı́ry, které zohledňuj́ı i modely s entropíı slov.

Na celé TF-IDF by se dalo nahĺıžet jako na entropii. Lze lehce ověřit, že př́ılǐsvelký počet slov ve vektoru (který určuje dimenzi prohledávaného prostoru)spolu s menš́ım počtem dokument̊u v kolekci zp̊usob́ı, že spoč́ıtané hodnoceńıstránek formou kosinových vzdálenost́ı v sobě neponese žádnou informaci. Stejnětak př́ılǐs hustě zaplněný prostor zp̊usob́ı tento problém.

3.2 Latent semantic indexing (LSI)

LSI je daľśım z př́ıklad̊u text-based IR technik, která použ́ıvá matematickoutechniku SVD (Singular value decomposition). Ve vyhledáváńı se často použ́ıvátzv. term-document matice A o velikosti m× n, kde řádky reprezentuj́ı výskytdaného slova ve všech dokumentech a sloupce reprezentuj́ı jednotlivé dokumenty.Prvek matice A na pozici ai,j je tedy vztah mezi i-tým slovem a j-tým doku-mentem. V binárńım modelu jsou na jednotlivých pozićıch jedničky tam, kde seslovo vyskytuje v př́ıslušném dokumentu a nuly jinde. Ve vektorovém modelujsou většinou na pozićıch matice relativńı četnosti slov v dokumentech.

Problém s použit́ım jednoduché formy této term-document matice je, že d́ıkyvelkému množstv́ı slov ve slovńıku a počtu dokument̊u může být tato repre-zentace velmi výpočetně náročná. Je tedy výhodné pro účely vyhledáváńı tentoprostor co nejv́ıce zredukovat. LSI nab́ıźı možnost, jak identifikovat vztahy mezijednotlivými slovy v textu a zbavit se zbytečných slov, která tvoř́ı dokument.Vycháźıme z předpokladu, že slova, která jsou použita ve stejných kontextechmaj́ı většinou podobný význam.

Zmenšeńı dimenze prostoru slov je dosaženo použit́ım SVD rozkladu. Základńıtvar SVD je dán vzorcem[AKP06]:

A = USV T , (4)

kde U, V jsou matice velikosti m× k0 a n× k0 s ortonormálńımi sloupci, kteréreprezentuj́ı ortonormálńı vlastńı vektory př́ıslušné nenulovým vlastńım č́ısl̊ummatic ATA a AAT , rank(A) = k0. S je diagonálńı matice (velikosti k0 × k0),která na diagonále obsahuje vlastńı č́ısla seřazená od největš́ıho po nejmenš́ı. Myse budeme snažit zredukovat náš prostor t́ım, že vybereme pouze k nejvyšš́ıchvlastńıch č́ısel (k < k0) a k nim př́ıslušných vlastńıch vektor̊u, č́ımž vznikneodhad matice A:

Ak = UkSkVTk . (5)

19

V SVD reprezentuj́ı vlastńı vektory př́ıslušné nejvyšš́ım vlastńım č́ısl̊um směrynejvětš́ıho rozptylu dat. Pokud tedy zanedbáme vlastńı č́ısla nejnižš́ıch hodnot,přijdeme jen o minimum sémantických aspekt̊u textu a zároveň sńıž́ıme nutnývýpočetńı výkon.

Pro nalezeńı podobnosti dotazu a jednotlivých dokument̊u je použita opět kosi-nová vzdálenost, a to mezi vektorem dotazu a jednotlivými sloupci matice Ak.

Takováto jednoduchá implementace má jednu nevýhodu. Pro obrovské množstv́ıprohledaných dat neńı třeba reorganizovat stažená data ani struktury, ve kterýchmáme uložené výsledky (jako např. naš́ı term-document matici). Pro menš́ıpočet dat si ale nemůžeme dovolit ignorovat slova, která nemáme zahrnuta veslovńıku a nově nalezené dokumenty nelze považovat za ned̊uležité. Je protonutné při budováńı indexu do našeho algoritmu zahrnout i možnost aktualizo-vat naše struktury - tzn. přidávat nové dokumenty a slova a aktualizovat tystávaj́ıćı. Mezi takové metody patř́ı např. fold-in nebo SVD updating.

3.3 PageRank

Algoritmus PageRank byl navržený Larry Pagem a Sergeyem Brinem a tvoř́ızáklad vyhledávače Google. Jedna se o typický př́ıklad hyperlink-based algo-ritmu, který využ́ıvá strukturu odkaz̊u mezi webovými stránkami pro jejichhodnoceńı. Důležitost stránky je určena podle počtu daľśıch stránek, které nańı ukazuj́ı. Zároveň je ale bráno v úvahu i hodnoceńı odkazuj́ıćıch stránek. Celývzorec vypadá takto17:

PR(A) = (1− d) + d(PR(T1)C(T1)

+ · · ·+ PR(Tn)C(Tn)

), (6)

kde PR(A) je PageRank stránky A, PR(Ti) je PageRank stránky Ti, která od-kazuje na A, C(Ti) je množstv́ı odkaz̊u vedoućı ze stránky Ti a d je tzv. dampingfactor - č́ıslo mezi 0 a 1.

Ze vzorce vid́ıme, že hodnoceńı stránek Ti neovlivňuje PageRank stránky A rov-noměrně, ale záviśı i na počtu odkaz̊u vedoućı z Ti. Pokud tedy z nějaké stránkyvede velké množstv́ı odkaz̊u, budou se tyto odkazy na PageRanku promı́tatpouze minimálně. Vzorec je rekurzivńı, ale při jakýchkoli vstupńıch dat po-stupně konverguje k výsledku.

Existuje ještě druhá verze algoritmu, jej́ıž vzorec vypadá takto:

PR(A) =(1− d)N

+ d(PR(T1)C(T1)

+ · · ·+ PR(Tn)C(Tn)

), (7)

kde N je počat stránek na webu. Od prvńı verze se tento vzorec př́ılǐs nelǐśı,ale d́ıky vyděleńı N udává opravdovou pravděpodobnost, že se uživatel při

17http://pr.efactory.de/e-pagerank-algorithm.shtml

20

náhodném surfováńı dostane na danou stránku. Algoritmus pak reprezentujepravděpodobnostńı rozděleńı nad všemi stránkami na webu, takže suma Page-Ranku všech stránek se sč́ıtá do jedničky.

Původně byl algoritmus PageRank popsán jako model chováńı uživatele při sur-fováńı webu, kde daný uživatel náhodně kliká na odkazy, aniž by mu záleželo naobsahu stránek18. Uživatel s pravděpodobnost́ı d bude pokračovat v surfováńı as pravděpodobnost́ı 1−d skonč́ı svou session. Kromě toho slouž́ı damping factord k normalizaci hodnoceńı - součet jednotlivých PageRank všech prohledanýchstránek je konstantńı. Sergey Brin navrhl d = 0.85, což je hodnota, která senejčastěji použ́ıvá a byla spoč́ıtána statistickými metodami. Podrobnou studiio hodnotě faktoru d a jeho možných alternativách udělali v roce 2006 vědci zuniverzity Shu-Te na Taiwanu[FLT06].

Jedno ze zaj́ımavých vylepšeńı popsal např́ıklad Taher H. Haveliwala ve svéstudii TopicSensitive PageRank [Hav02], ve které navrhuje napoč́ıtáváńı v́ıcenež pouze jednoho PageRank vektoru pro větš́ı přesnost v závislosti na hle-daném dotazu. Nejprve se muśı určit jednotlivá témata (okruhy), pro kterése bude PageRank vektor poč́ıtat. Následně se při zpracováńı dotazu vyhod-not́ı, do kterého tématu tento dotaz spadá, a použije se odpov́ıdaj́ıćı vektor.Vytvořeńım topic-sensitive19 verze PageRank algoritmu předejdeme vysokémuhodnoceńı stránek, na které vede hodně odkaz̊u a které obsahuj́ı některé z hle-daných slov, ale ve skutečnosti nemaj́ı žádnou spojitost s hledaným tématem.Tento postup se dá uplatnit např. při vyhledáváńı slov v nějakém kontextu.Ve zmı́něné studii je uveden hezký př́ıklad, kdy uživatel procháźı nějaký doku-ment zabývaj́ıćı se slavnými architekty na stránce pomoćı vyhledáváńı zvýrazńıslovo ”architektura”, ke kterému chce naj́ıt daľśı informace. V tomto kontextuby bylo vhodné, aby výsledek takového vyhledáváńı byl odlǐsný od toho, kdyžsi takový uživatel vyhledá termı́n ”architektura”použitý v článku o procesorech.

Ve zkratce se topic-sensitive PageRank dá popsat takto: Během offline zpra-cováńı našeho prohledáváńı (web crawl) vygenerujeme určitý počet topic-sensitivePageRank vektor̊u. Během zpracováńı dotazu spoč́ıtáme podobnost dotazu (querysimilarity, možné zahrnout i kontext, ve kterém hledáme) s každým tématem amı́sto použit́ı jednoho globálńıho PageRank vektoru použijeme lineárńı kombi-naci naš́ı množiny vektor̊u váženou spočtenými podobnostmi. Důležitým faktemje to, že naše množiny pro zvolená témata musej́ı být vychýlená (biased). Tohodosáhneme následuj́ıćım postupem:

vi,j =

{1|Tj | , i ∈ Tj0, i /∈ Tj ,

(8)

kde Tj je množina URLs v nějakém top-level directory v kategorii cj (mámej kategoríı). Dále vj je vektor, který použijeme během výpočtu PageRanku

18random surfer19citlivé na téma, tento výraz se obt́ıžně překládá do českého jazyka

21

namı́sto jednoho obecného vektoru.

3.4 HITS

HITS patř́ı mezi daľśı ze tř́ıdy hyperlink-based algoritmů pro identifikaci skupinstránek zabývaj́ıćıch se stejným tématem na webu. Algoritmus děĺı jednotlivéstránky na ”authorities”a ”hubs”20. Authorities jsou stránky s bohatým obsa-hem, které mezi sebou většinou nemaj́ı odkazy. Oproti tomu hubs jsou stránkyslouž́ıćı jako adresář odkazuj́ıćı na mnoho autoritativńıch stránek. Dobrý hub jeproto taková stránka, která má co nejv́ıce odkaz̊u na dobré authorities, a dobráauthority je stránka, na kterou je odkazováno z mnoha hubs. Tyto dva typydokument̊u jsou separovány dvěmi následuj́ıćımi operacemi[NOHI04]:

xp =∑

q,q→pyq (9)

yp =∑

q,p→qxq (10)

Pro stránku p je váha xp upravena podle počtu yq např́ıč všemi stránkamiq, které na p odkazuj́ı. Stejným zp̊usobem jsou poč́ıtány i váhy yp. T́ım jsouspoč́ıtány váhy jednotlivých hubs i authorities.

Algoritmus HITS byl navržen Jonem Kleinbergem za doby jeho p̊usobeńı vIBM a byl v podstatě předch̊udcem algoritmu PageRank.

20Tyto termı́ny nebudu překládat do Češtiny

22

4 Existuj́ıćı software

Zde se pod́ıváme, jaký software v kategorii webcrawlingu a vyhledáváńı jižexistuje, a uděláme stručný přehled. Nejprve uvedeme př́ıklad na velkých vy-hledávaćıch systémech a poté zmı́ńıme několik odkaz̊u na existuj́ıćı crawlery aboty.

4.1 Google

Google běž́ı na distribuované śıti milion̊u levných poč́ıtač̊u, takže dokáže zpra-covávat velké množstv́ı proces̊u současně21. Google se skládá ze tř́ı hlavńıchčást́ı:

• Google-bot - web crawler

• Indexer - analyzuje slova na stránkách a stará se o index

• Query processor - porovnává dotazy od uživatele i indexem a vraćı rele-vantńı dokumenty

Google-botGoogle-bot se skládá z mnoha poč́ıtač̊u, kteř́ı bez přestávky stahuj́ı tiśıce r̊uznýchstránek současně. Aby se zabránilo přehlceńı server̊u, tak Google-bot pośılána jednotlivé servery požadavky pomaleji, než je jeho opravdový výkon. Exis-tuj́ı dva zp̊usoby, jak tento bot nalézá nové stránky: skrze formulář na adresewww.google.com/addurl.html a skrze URL, které se nacházej́ı na prohledanýchstránkách.

Tento formulář obsahuje test, který má za úkol rozpoznat, zda se jedná ouživatele či jiného bota, aby se zabránilo zneuž́ıváńı pro spam a komerčńı účely.Hodně spammer̊u totiž začalo vymýšlet taktiky, jak zvýšit viditelnost svýchstránek v Google indexu.

Google-bot provozuje tzv. deep crawling, takže následuje jednotlivé linky dovelké hloubky, což mu umožňuje prozkoumat velkou část webu. Jelikož je alestránek obrovské množstv́ı, prob́ıhá crawling dané stránky pouze jednou za čas- např. jednou za měśıc.

Stránky, které má Google-bot v plánu navšt́ıvit muśı být permanentně po-rovnávány s již navšt́ıvenými, aby se zabránilo duplicitě. Stránky, které jsounavštěvovaněǰśı a měńı se dynamicky jsou navštěvovány a analyzovány častějinež ty statické a méně populárńı, aby byl idnex stále aktuálńı. Tomu se ř́ıkátzv. fresh crawl. Např́ıklad r̊uzné stránky zabývaj́ıćı se zprávami a jiným častose měńıćı obsahem jsou stahovány každý den. Fresh crawls samozřejmě stáhnoumnohem méně stránek než deep crawls, takže pro optimálńı strategii je použitakombinace obou technik.

21parallel processing

23

IndexerIndexer dostává od crawleru kompletńı obsah stažené stránky. Tyto stránkyjsou uloženy v indexu. Index je seřazen abecedně podle hledaných výraz̊u, kdeke každému slovu existuje list stránek, jež toto slovo obsahuj́ı.

Google také použ́ıvá stop words, aby se vyhnul zbytečné analýze výraz̊u, kterénesou jen minimálńı informaci a jsou pro relevanci výsledného hodnoceńı stránekned̊uležité.

Query ProcessorQuery processor se skládá z v́ıce část́ı. Prvńı z nich je uživatelské rozhrańı(tedy formulář), do kterého uživatel zadává sv̊uj dotaz. Daľśı části se pak jižvěnuj́ı vyhodnoceńı zadaného dotazu pomoćı algoritmu PageRank, kterým jsmese zabávali v dř́ıvěǰśı kapitole. Google také použ́ıvá r̊uzné algoritmy, kterými seuč́ı rozpoznat vztahy mezi r̊uznými slovy, a mimo jiné také implementuje auto-matické opravy pravopisných chyb.

Seznam bot̊u, které Google použ́ıvá může být nalezenem na stránkách Goo-gle support22. Bližš́ı shrnut́ı toho, jak celý vyhledávač funguje, se lze doč́ıstnapř́ıklad zde23. Dobrým zdrojem může být také článek od samotných zaklada-tel̊u Google[BP98].

4.2 Yahoo

Yahoo p̊uvodně začalo jako velký webový adresář s webovými stránkami, kterébyly hierarchicky organizované do jednotlivých skupin. Koncem devadesátýchlet se z Yahoo stal plnohodnotný vyhledávač.

Podobně jako Google se i Yahoo architektura skládá z v́ıce část́ı. Těminejd̊uležitěǰśımi jsou tyto dvě:

• Spider - web crawler, u Yahoo se mu ř́ıká Slurp

• Indexer -vyhodnocuje obsah stránek a buduje index

Funkce jednotlivých část́ı je velmi podobná jako u Google, takže ji zde již ne-budu podrobně rozepisovat.

Pro podrobněǰśı informace ohledně vyhledávač̊u a jejich historie doporučujinapř́ıklad přehled, který udělali vědci z Minot State University v USA roku2011[SFK11].

22http://support.google.com/webmasters/bin/answer.py?hl=en&answer=106194323http://www.googleguide.com/google works.html

24

4.3 Lydia

Lydia[LKS05] je projekt, který buduje relačńı model lid́ı, mı́st a publikaćı po-moćı natural language processing stránek zabývaj́ıćıch se zprávami. Projekt dělástatistickou analýzu četnost́ı slov a ko-lokaćı. Momentálně je v systému cca500 stránek zabývaj́ıćıch se online zpravodajstv́ım. Lydia zjǐst’uje, o kom se vezprávách ṕı̌se, kým, kde a kdy.

Celý systém je optimalizován tak, aby byl schopen analyzovat obrovské množstv́ıtextu ve velmi krátkém čase, jelikož je nutné zpracovat celý obsah online zpravo-dajského portálu každý den (a těchto portál̊u je také velké množstv́ı). Aktuálńıinformace jsou na adrese http://www.textmap.com/.

Nejprve crawler źıská text stránky, poté se identifikuje, kde se dané objekty(lidi, mı́sta, společnosti apod.) nacházej́ı v textu. Pro každý takový objekt sezjǐst’uje, jaké daľśı objekty se vyskytuj́ı pobĺıž. Každý objekt může být použitv́ıce r̊uznými zp̊usoby, a proto se ještě muśı identifikovat synonyma. Nakonecnásleduj́ı r̊uzné analýzy, kterými se vypoč́ıtá, jak často se objekty objevuj́ı najednotlivých stránkách.

Přehled všech aktivit ohledně systému Lydia je na stránkáchhttp://www.cs.sunysb.edu/∼skiena/lydia/.

4.4 Daľśı boti

Každý vyhledávač má své boty, ale vzhledem k tomu, že všichni funguj́ı velmipodobně, nemá smysl je zde podrobně rozeb́ırat, nebot’ to neńı ćılem této práce.Kromě bot̊u, kteř́ı pracuj́ı pro velké vyhledávače existuje ale i mnoho daľśıch,kteř́ı mohou být vyvinuty pro specielńı druh práce.

Vzhledem k velkému počtu a r̊uznorodosti zde uvedu několik odkaz̊u na seznamexistuj́ıćıch bot̊u.

• http://www.robotstxt.org/db.html

• http://www.user-agents.org/

4.5 Focused crawlery

V této sekci se pod́ıváme na př́ıklady crawler̊u, které jsou naš́ı implementaci svoufunkcionalitou nejbližš́ı (mohou se ale výrazně lǐsit př́ıstupem k prohledáváńı).

Prvńım př́ıkladem takového crawleru je např́ıklad Bingo!24. Tato implemen-tace použ́ıvá klasifikátor, který pomoćı trénovaćıch dat odhaluje archetypy vanalyzovaných stránkách a ty následně porovnává s nově nalezenými stránkami.Jakmile byla stránka klasifikována, jsou z ńı extrahovány všechny linky, které

24http://www.mpi-inf.mpg.de/departments/d5/software/bingo/idx.htm

25

Obrázek 6: Diagram Lydia pipeline[LKS05]

jsou umı́stěny do fronty. Bingo! použ́ıvá kombinaci strategíı pro priorizaci stránekve frontě, jako např́ıklad prohledáváńı do hloubky s fixńı hloubkou.

K vyhledáváńı jsou použity i takové stránky, které neprošly testem klasifikátoru,nicméně je na ně aplikováno prohledáváńı do menš́ı hloubky. To se dělá zd̊uvodu, že někdy se k relevantńımu obsahu dá dostat pouze skrz r̊uzné uv́ıtaćıstránky a rozcestńıky, které samy o sobě nenesou žádné informace. Pro analýzudokument̊u Bingo! použ́ıvá kombinaci r̊uzných strategíı, mimo jiné i TF-IDFmı́ru.

Daľśım př́ıkladem je Win Web Crawler 225, což je nástroj pro webmasterypro vytvářeńı webových adresář̊u a podporu webových portál̊u. Tento crawlerextrahuje URL, meta tagy, text a daľśı cenné informace z prohledaných stráneka ulož́ı je na disk. Program nav́ıc podporuje široký výběr filtr̊u a omezeńı propodrobněǰśı specifikaci crawling session.

25http://www.fileguru.com/Win-Web-Crawler/info

26

5 Implementace crawleru

V této sekci se pod́ıváme na implementaci konkrétńıho crawleru a rozeberemesi jednotlivé struktury programu.

5.1 Popis

Nejprve si muśıme uvědomit, co náš crawler vlastně bude umět, a č́ım se budeodlǐsovat od ostatńıch crawlers. Mým ćılem je navrhnout tzv. focused crawler,který bude vyhledávat zadaná slova, př́ıpadně stránky zabývaj́ıćı se nějakýmbĺıže nespecifikovaným tématem. Kromě ćıleného vyhledáváńı bude možno ivyhledáváńı bez specifikace hledaných výraz̊u - stránky pak budou hodnocenyna základě množstv́ı informaćı, které obsahuj́ı. Nebudeme mı́t k dispozici do-statečný výpočetńı výkon ani množstv́ı dat, abychom si mohli vybudovat rozsáhlýindex, ve kterém bychom prováděli vyhledáváńı - budeme tedy vyhledávat zachodu. Vybudováńı indexu ale také do naš́ı implementace zahrneme, abychommohli výsledky vyhledáváńı použ́ıt i offline.

Narozd́ıl od vyhledávač̊u, které použ́ıvaj́ı velký počet bot̊u k pravidelnému pro-hledáváńı Webu a tvorbě rozsáhlého (a aktuálńıho) indexu, nemáme k dispozicitakový výpočetńı výkon, aby naše výsledky byly srovnatelné např. s Google.Proto zvoĺıme jiný př́ıstup - budeme prohledávat omezený počet stránek, kterépostupně analyzujeme, a na konci session26 zobraźıme výsleky. Dı́ky ńızkémupočtu prohledaných stránek (tiśıce až deśıtky tiśıc) budeme stránky hodnotitjen na základě výskyt̊u hledaných slov a zanedbáme odkazy mezi nimi.

Posledńı věc, kterou je nutné zmı́nit, je, že výsledek dané session je dán hlavnět́ım, jaké zdrojové stránky (seed URLs) použijeme. Dı́ky nižš́ımu počtu prohle-daných stránek nemůžeme zač́ıt s prohledáváńım př́ılǐs daleko od zvolenéhotématu (tzn. pokud hledáme informace o webovém vyhledáváńı, nemůžemeočekávat velký úspěch, začneme-li vyhledávat na stránkách, které se zabývaj́ıvařeńım).

Crawler bude psán v jazyce Java. K parsováńı HTML použijeme vestavěnéknihovny. Jejich dokumentace je dostupná na stránkách Oracle27. Součást́ı budei grafické uživatelské rozhrańı a podpora v́ıce vlákem pro spuštěńı několikanezávislých crawler̊u současně.

5.2 Pr̊uběh session

Crawler bude vykonávat jednoduchý cyklus: stáhne zdrojový kód stránky, zpra-cuje všechen text na ńı, ulož́ı si odkazy, které ze stránky vedou a pokračujetakto dál.

26jeden cyklus prohledáváńı27http://docs.oracle.com/javase/6/docs/api/javax/swing/text/html/parser/package-

summary.html

27

Obrázek 7: Základńı cyklus webcrawling session

Prvńı věc, kterou je třeba rozhodnout, je jakou strukturu použ́ıt pro ukládáńınově źıskaných URLs. Zde implementujeme frontu. Důvody byly již rozebrányv předchoźıch kapitolách.

Na konci prohledáváńı crawler vyhodnot́ı všechny navšt́ıvené stránky a na základěTF-IDF metriky každé z nich přǐrad́ı hodnoceńı, které odpov́ıdá relevanci danéstránky. Tato hodnoceńı budou uložena spolu s daľśımi cennými statistikami,jako např. četnostmi slov na jednotlivých stránkách a graf̊u pr̊uběhu celé session.Nakonec program vyprodukuje výstup, kde budou zobrazeny nejlépe hodnocenéstránky a umožńı uživateli daľśı interakci.

Mimo to crawler vyprodukuje index, ve kterém bude možné vyhledávat i poskončeńı session.

5.3 Reprezentace dat a struktura

Vzhledem k tomu, že celý program je psán v jazyce Java, př́ımo se nab́ıźı práces daty jakožto s objekty. Za objekt budeme považovat úplně vše - od jednot-livých slov, přes stránky až po samotný crawler. Výhodou je, že od většinystuktur bude existovat mnoho instanćı a my si o nich budeme schopni velmijednoduše pamatovat řadu informaćı (např. u stránek seznamy slov, r̊uzná hod-noceńı, u slov počty výskyt̊u apod.). Nevýhodou je pak v některých př́ıpadechmenš́ı efektivita a pamět’ová náročnost. Na to se ale pod́ıváme až na konci tétokapitoly, př́ıpadně se pod́ıváme na statistiky v kapitole shrnuj́ıćı výsledky práce.

Hlavńı entitou je Master Manager, která má pod sebou všechny crawlery (těchmůže být v́ıce a každý běž́ı v separátńım vlákně). Tř́ıda Crawler je pak ř́ıd́ıćımobjektem pro jednotlivé crawling sessions, která má pod sebou všechny daľśı

28

komponenty programu. Celou základńı strukturu si můžete prohlédnout naobrázku.

Obrázek 8: Základńı struktura programu

Následuje stručný popis nejd̊uležitěǰśıch entit:

ManagerToto je hlavńı tř́ıda, která spravuje globálńı informace a argumenty pro spuštěńıjednotlivých crawler̊u. Můžeme pustit v́ıce prohledáváńı najednou, které poběž́ınezávisle na sobě v oddělených vláknech.

CrawlerHlavńı struktura, ve které prob́ıhaj́ı všechny procesy spjaté s prohledáváńım aanalýzou dat.

URL processorTř́ıda, která se stará o nalezené URL adresy. V př́ıpadě invalidńı nebo ignoro-vané adresy (některé stránky můžeme při určitém nastaveńı crawleru ignorovat)se postará o výjimku.

Text processorSpravuje informace o nalezených stránkách a slovech (př́ıpadně dvojićıch atd.),

29

které se na nich nacházej́ı.

Pages detectorAnalyzuje obsah stránek a přǐrazuje jim rating podle zvolené metody. Určuje,jaké stránky se na konci session objev́ı na vrcholu.

Index generatorPo skončeńı posledńı crawling session vytvoř́ı index pro budoućı vyhledáváńı v”offline”režimu, resp. pomoćı druhého klienta.

Zbylé tř́ıdy jsou určeny pro grafickou reprezentaci nalezených dat a jiné funkce.

5.4 Výstup crawleru

Kromě popsaných možnost́ı crawlingu má program ještě pár daľśıch funkćı.Pod́ıváme se tedy ted’, co vše je výstupem jednotlivých crawling sessions:

Hodnoceńı stránek: Sám crawler i bez použit́ı indexu (ač oproti vyhledáváńı vindexu poměrně neefektivně) umı́ vytvořit hodnoceńı jednotlivých stránek, a topoužit́ım TF-IDF mı́ry pro jednotlivá slova a dvojice slov. Tato hodnoceńı jsoupoužita i v př́ıpadě, že se session několikrát opakuje pro nalezeńı optimálńıchzdrojových URL.

Statistiky ignorovaných a chybových URL: Soubory, ve kterých jsou uve-deny všechny URL, které byly v pr̊uběhu crawling session ignorovány nebo se knim nepodařilo připojit.

Graf pohybu po stránkách: Graf ve formátu XML28 a k němu př́ısluš́ıćısoubor se statistikami o stupńıch uzl̊u v tomto grafu.

Obrázek podobnosti jednotlivých stránek: Na obrázku jsou ve stupńıchšedi znázorněny podobnosti (kosinové vzdálenosti TF-IDF) každých dvou stránek,které jsme navšt́ıvili. Celý obrázek je symetrický nebot’ na diagonále se vysky-tuj́ı vždy stejné stránky.

Statistiky výskyt̊u slov: Crawler sleduje statistiky četnost́ı jednotlivých slova dvojic slov. Kromě toho rozlǐsuje tyto četnosti v rámci všech prozkoumanýchstránek i jednotlivě na každé stránce zvlášt’.

Index: Crawler na konci posledńı session vytvoř́ı matici a k ńı př́ıslušné soubory(viz daľśı kapitola).

28optimalizovaný pro prohĺıžeńı v programu yED - http://www.yworks.com/en/products yed about.html

30

5.5 Stop words

Stop words jsou slova, která se v daném jazyce vyskytuj́ı často, ale nenesoužádnou významovou informaci. Většinou se jedná o r̊uzné předložky, spojkyapod. Seznam těchto slov se označuje jako stopwords a tato slova jsou zpravidlapři budováńı indexu a vyhledáváńı zcela ignorována.

My máme možnost na začátku session specifikovat cestu k souboru, kde mámenáš seznam stopwords uložen, a t́ım tyto výrazy při zpracováńı dat zanedbat.Kromě toho, pokud jsme nějaký takový seznam vybrali, crawler nám na koncisession sám nab́ıdne několik deśıtek nejčastěǰśıch výraz̊u (v tomto př́ıpadě slovs nejvyšš́ım ratingem), ze kterých můžeme vybrat libovolné množstv́ı. Tato vy-braná slova pak budou automaticky přidána do našeho seznamu pro budoućıpoužit́ı.

5.6 Problémy implementace

Asi největš́ım zádrhelem mé implementace ja výpočetńı složitost a ukládáńı dat.Jelikož ani práce se soubory ani r̊uzné metody zabývaj́ıćı se efektivitou využit́ıvýpočetńıho výkonu nebyly předmětem této práce, zvolil jsem poměrně jed-noduché struktury. Tomu samozřejmě odpov́ıdá i výsledný výkon a pamět’ovánáročnost.

Kromě toho během každé session zpracovávám ještě daľśı data - předevš́ımr̊uzné statistiky četnost́ı skupin slov, generováńı graf̊u a obrázku apod., kterépro samotné vyhledáváńı nejsou př́ımo potřebné. Práce by tedy šla zefektiv-nit použit́ım jednodušš́ıho crawleru, který by měl pouze ty funkce, které jsoubezprostředně nutné pro vytvořeńı indexu.

5.7 Budováńı indexu

Náš crawler umı́ na konci dané crawling session zobrazit výsledky, takže nějakouzpětnou vazbu již máme. Pro dlouhodobé už́ıváńı by ale bylo poněkud nešikovné,kdybychom při každém vyhledáváńı nějakého dotazu museli čekat, než proběhnecelá session a my konečně uvid́ıme relevantńı výsledky. Proto bychom si mělivybudovat index, ve kterém budeme moci vyhledávat i po skončeńı všech craw-ling session.

Obrázek 9: Základńı cyklus

31

5.8 Struktury indexu

Crawler si uchovává řadu zaj́ımavých informaćı a statistik, které nasb́ıral běhemprozkoumáváńı webu. K vybudováńı indexu nám ale stač́ı jen některé z nich. Vprvńı řadě budeme potřebovat sestavit tzv. term-document matrix A = [ai,j ],kde ai,j znač́ı term frequency slova i na stránce j. Tato matice zat́ım nebylastandardńım výstupem crawleru, a d́ıky uchováváńı velkého množstv́ı informaćıběhem prohledáváńı, ji budeme tvořit až na konci posledńı session (která byměla být ze všech nejv́ıce relevantńı).

Matice je uložena jako textový soubor, což je sice poměrně neefektivńı, alejednoduché (a my zat́ım pracujeme sṕı̌se s menš́ım počtem dat29). Muśıme sitedy uvědomit, jaké struktury budeme k reprezentaci dat potřebovat. Kroměsamotného souboru s matićı A to bude ještě soubor s jednotlivými stránkami aslovy, ke kterým si muśıme pamatovat indexy (tzn. pozice v naš́ı matici) a IDFmı́ry jednotlivých slov, abychom je mohli použ́ıt pro vyhledáváńı.

Jakmile budeme mı́t tyto výsledky uložené, vytvoř́ıme si klienta, který budev indexu vyhledávat. Při jeho spuštěńı specifikujeme cestu k uloženým dat̊um(tzn. můžeme mı́t v́ıce speciálńıch index̊u) a následně můžeme zadávat dotazy,jejichž výsledkem budou jednotlivé prozkoumané stránky seřazené podle rele-vance. Jako mı́ru budeme opět použ́ıvat TF-IDF.

5.9 Klient

Uživatel nejprve specifikuje cestu k soubor̊um, které jsme pro účely našeho in-dexu vytvořili. Následně si klient do paměti načte soubory s jednotlivými slovya url prozkoumaných stránek spolu s jejich indexy do term-document matrix.

Samotnou matici si již do paměti nač́ıtat nemuśıme, nebot’ nám stač́ı pouzenač́ıst ty jej́ı řádky, které budou odpov́ıdat slov̊um obsažených v dotazu30 oduživatele. Následně jsme schopni téměř okamžitě napoč́ıtat všem stránkám ra-ting podle tf hledaných slov, seřadit stránky sestupně podle ratingu a zobrazitvýsledky.

29 řádově tiśıce až desetitiśıce stránek30query

32

6 Prezentace výsledk̊u

Jako prvńı uvedu několik praktických př́ıklad̊u z crawling sessions a následnémvyhledáváńı r̊uzných dotaz̊u v indexech, které jsem z nasb́ıraných dat vytvořil.Hned na začátku muśım podotknout, že mé hodnoceńı výsledk̊u bude velmi sub-jektivńı, nebot’ je obt́ıžné tyto výsledky s něč́ım porovnat. Vzhledem k ńızkémurozsahu indexu (v řádu tiśıc̊u stránek a statiśıc̊u unikátńıch slov) nelze tytovýsledky porovnávat např. s velkými internetovými vyhledávači. V př́ıpaděmenš́ıch stránek lze pro porovnáńı použ́ıt lokálńı vyhledáváńı (podporuje-liho prohledávaná doména). Z hlediska pamět’opvé náročnosti, která je z částizp̊usobená t́ım, že můj crawler během session sb́ırá spoustu daľśıch informaćı,které nejsou pro budováńı indexu př́ımo potřebné, se omeźım na prohledáváńıpouze několika tiśıc stránek.

6.1 Př́ıklad 1

Jako prvńı př́ıklad jsem se rozhodl použ́ıt stránky zabývaj́ıćı se vařeńım -spousta r̊uzných stránek s recepty nám poslouž́ı jako vhodné prostřed́ı prosběr dat a následným vyhledáváńım v indexu budeme schopni alespoň odhad-nout, do jaké mı́ry bylo naše vyhledáváńı přesné. Výhodou je i to, že jsem jakotestovaćı stránku vybral takovou, která má vlastńı lokálńı vyhledávač, takžemám možnost své výsledky i v menš́ı mı́̌re porovnávat s ńım. Pro demonstracivýsledk̊u použiji dva r̊uzné dvouslovné dotazy.

Doména: http://www.thekitchn.com/Limit: 4000 stránekLokálńı vyhledáváńı: ANOStopwords: ANOĆılené vyhledáváńı: NEVı́cenásobné session: NE

Čas: cca 45 min (včetně zápisu a zpracováńı dat)Pamět’ová náročnost na konci session: cca 1 GB

Dotaz 1: Fried chicken31

Ačkoli námi prohledaných 4000 stránek nezahrnuje celou testovanou doménu,pro tento dotaz jsme dostali překvapivě dobré výsledky. Tři z našich pěti nejlépehodnocených stránek dokonce patř́ı mezi pětici nejlépe hodnocených stránek ve-stavěného vyhledávače. Z našich nalezených URL je jistě na prvńı pohled patrné,že se všechny týkaj́ı (př́ıpadně je v receptu zahrnuto) smaženého kuřete. Pojd’mese tedy pod́ıvat, jak dopadl náš druhý dotaz:

31testováno dne 21. 2. 2013

33

Rank My index1 http://www.thekitchn.com/dinner-recipe-baked-fried-chic-

1526202 http://www.thekitchn.com/thomas-kellers-fried-chicken-r-801973 http://www.thekitchn.com/recipe-easy-chicken-marsala-1165814 http://www.thekitchn.com/recipe-korean-f-1597485 http://www.thekitchn.com/lighter-zucchini-fritti-olive-89272

Obrázek 10: Výstup klienta

Rank Built-in search1 http://www.thekitchn.com/healthy-recipe-fake-fried-chicken-

1653742 http://www.thekitchn.com/dinner-recipe-baked-fried-chic-

1526203 http://www.thekitchn.com/thomas-kellers-fried-chicken-r-801974 http://www.thekitchn.com/recipe-korean-f-1597485 http://www.thekitchn.com/recipe-fingerlicking-fried-chi-79965

Dotaz 2: Vegetarian mealZde se naše výsledky od jejich lokálńıho vyhledávače již poněkud lǐśı, nicméněna prvńı pohled je očividné, že výsledek našeho vyhledáváńı pro tento dotaz bylpoměrně úspěšný a všechny nalezené stránky jsou naproto relevantńı.

34

Obrázek 11: Výstup lokálńıho vyhledáváńı

Rank My index1 http://www.thekitchn.com/recipes/vegetarian2 http://www.thekitchn.com/how-to-make-a-quick-vegetarian-

1267123 http://www.thekitchn.com/vegetarian-recipes-728654 http://www.thekitchn.com/ideas-for-vegetarian-winter-recipes-

that-can-be-served-cold-good-questions-1844225 http://www.thekitchn.com/healthy-vegetarian-recipes-that-

satisfy-even-die-hard-meat-eaters-182827

35

Rank Built-in search1 http://www.thekitchn.com/25-vegetarian-and-vegan-recipe-

1048412 http://www.thekitchn.com/categories/vegetarian3 http://www.thekitchn.com/ideas-for-vegetarian-meals-with-no-

fruits-or-vegetables-good-questions-1766474 http://www.thekitchn.com/meatless-recipe-1634265 http://www.thekitchn.com/vegetarian-meals-to-satisfy-ron-

swanson-171323

6.2 Př́ıklad 2

Ve druhém př́ıkladu bych chtěl ukázat, jak funguje naše ćılové vyhledáváńı.Budeme opět vyhledávat lokálně, tentokrát na anglické Wikipedii. Náš crawlerdostane několik kĺıčových slov, podle kterých na konci session ohodnot́ı prohle-dané stránky a začne daľśı session od těch nejslibněǰśıch. Je to tedy něco nazp̊usob beam search32. Wikipedii jsem vybral proto, že je to obrovská website,kde standardńı vyhledáváńı v jedné session omezené shora limitem max pro-hledaných stránek by pravděpodobně nepřineslo uspokojivé výsledky. Nav́ıc zdeopět můžeme porovnat naše výsledky s lokálńım vyhledáváńım, které je na Wi-kipedii k dispozici.

Doména: http://en.wikipedia.org/Limit: 1500 stránekLokálńı vyhledáváńı: ANOStopwords: ANOĆılené vyhledáváńı: ANOVı́cenásobné session: 3x

Čas: cca 50 min (včetně zápisu a zpracováńı dat)Pamět’ová náročnost na konci session: cca 1 GB

Dotaz: Ancient Greek33

Výsledky pro tento dotaz si můžeme opět prohlédnout v tabulce a srovnat jes výsledky lokálńıho vyhledávače. Všechny nalezené nejlepš́ı výsledky se týkaj́ıhledaného dotazu. Stránka, kterou Wikipedie (a já osobně také) hodnot́ım jakonejv́ıce relevantńı skončila na třet́ım mı́stě. To je zp̊usobeno vysokými frek-vencemi slov ”ancient”a ”greek”na ostatńıch stránkách a faktem, že v našemindexu nezohledňujeme pořad́ı slov (tzn. zda hledané výrazy jsou obsaženy vtextu stránky př́ımo vedle sebe).

32viz kapitola 233testováno dne 28. 2. 2013

36

Rank My index1 http://en.wikipedia.org/wiki/Outline of ancient Greece2 http://en.wikipedia.org/wiki/Military of ancient Greece3 http://en.wikipedia.org/wiki/Ancient Greek4 http://en.wikipedia.org/wiki/Greek Evangelical Church5 http://en.wikipedia.org/wiki/List of ancient Greek theatres

Obrázek 12: Nejlépe hodnocená stránka dle našeho indexu

Těchto výsledk̊u bylo dosaženo až na konci třet́ı session. Pokud se pod́ıvámenapř́ıklad na výsledky nejlépe hodnocených stránek po prvńı session, kterázač́ınala na titulńı stránce Wikipedie, uvid́ıme, že pouze některé z nich jsourelevantńı:

37

Rank My index1 http://en.wikipedia.org/wiki/Greek Wikipedia2 http://en.wikipedia.org/wiki/Cyprus3 http://en.wikipedia.org/wiki/Portal:Arts4 http://en.wikipedia.org/wiki/Andrew Dalby5 http://en.wikipedia.org/wiki/Engineering

6.3 Př́ıklad 3

Jako sv̊uj posledńı př́ıklad jsem si vybral stránku žertovného zpravodajstv́ı apolitické satiry The Onion News Network, na které provedu lokálńı vyhledáváńıa sestav́ım index. Výsledek pak ověř́ım na dvou dotazech. Je zde opět možnostporovnat výsledky s lokálńım vestavěným vyhledávačem.

Doména: http://www.theonion.com/Limit: 6000 stránekLokálńı vyhledáváńı: ANOStopwords: ANOĆılené vyhledáváńı: NEVı́cenásobné session: NE

Čas: cca 120 min (včetně zápisu a zpracováńı dat)Pamět’ová náročnost na konci session: cca 500 MB

Dotaz: President Obama34

Tento dotaz přinesl velmi věrohodné a přesné výsledky, což je dáno hlavně fak-tem, že query ”president Obama”je poměrně aktuálńı a tud́ıž se ve zpráváchvyskytuje často. Naše pokryt́ı 6000 stránek tedy bylo dostatečné. Nav́ıc slova”president”a ”Obama”se v textu často vyskytuj́ı vedle sebe. Srovnáńı s lokálńımvyhledávačem zde ani neńı třeba.

Rank My index1 http://www.theonion.com/articles/biden-implores-obama-to-

rub-one-out-before-debate,29785/2 http://www.theonion.com/articles/obama-paranoid-government-

coming-for-his-guns,30638/3 http://www.theonion.com/articles/obama-reelected-

president,30285/4 http://www.theonion.com/articles/president-obama-mentions-

hed-like-to-see-lebron-ja,17512/5 http://www.theonion.com/articles/president-obama-wondering-

why-he-always-has-to-ini,27026/g

Dotaz: Peter JacksonNa tomto dotazu bych chtěl poukázat na určité nedostatky našeho vyhledáváńı.

34testováno dne 9. 3. 2013

38

Obrázek 13: Nejlépe hodnocená stránka dle našeho indexu

Vybral jsem query ”Peter Jackson”, nebot’ je toto téma (d́ıky nedávné premiéřefilmu Hobbit) poměrně aktuálńı a náš crawler v této tématice našel několikstránek. ”Jackson”je ale poměrně frekventované př́ıjmeńı, a když se pod́ıvámena výsledky našeho crawleru, tak z pěti nejlépe hodnocených stránek se spojeńı”Peter Jackson”objevuje pouze v jedné.

Je to zp̊usobeno t́ım, že na nejlépe hodnocené stránce se poměrně frekvento-vaně vyskytuje slovo ”Jackson”, které má nav́ıc o něco vyšš́ı hodnoceńı IDF než”Peter”(IDFjackson = 2.6321, IDFpeter = 2.3802).

Rank My index1 http://www.theonion.com/articles/reggie-jackson,18311/2 http://www.theonion.com/articles/peter-jackson-opens-up-

about-his-personal-hobbit-f,28487/3 http://www.theonion.com/articles/phil-jackson-enjoying-

retirement-on-montana-ranch,28021/4 http://www.theonion.com/articles/lauren-jackson,28948/5 http://www.theonion.com/articles/pet-dog-almost-like-

disgusting-family-member,30794/

39

Obrázek 14: Pohyb crawleru během crawling session

40

7 Navržeńı daľśıho postupu

Během práce jsme implementovali funkčńı verzi crawleru, který je schopen vybu-dovat index, a klienta, který v něm umı́ vyhledávat. Výsledky této implementacejsou shrnuty v předchoźıch kapitolách.

Nyńı je čas naznačit, na co již v této práci nezbyl prostor. Zde tedy shrneme,jaké úpravy je třeba udělat, aby se z našeho crawleru stal použitelný nástroj,př́ıpadně i základ malého specializovaného vyhledávače.

7.1 Práce s daty a výkon

Jedńım z největš́ıch problémů současné implementace je práce s daty. Jelikožtato oblast nebyla těžǐstěm práce, řešili jsme ukládáńı a nač́ıtáńı dat poměrnětriviálńım zp̊usobem, což se podepisuje i na současném výkonu crawleru. Do bu-doućı verze softwaru (bude-li nějaká) bude třeba změnit zp̊usob, jakým ukládámedata, aby se s nimi dalo rychle a efektivně pracovat. Mı́sto textových soubor̊ubude použita databáze.

Kromě toho by výkon crawleru velmi vylepšilo, kdyby byla možnost si datav pr̊uběhu session pravidelně ukládat, jelikož většina z nich bude potřeba až naúplném konci. Mimo jiné by taky pomohlo, kdyby se celý crawler v́ıce speciali-zoval na vybudováńı indexu, nebot’ v současné době je trochu omezen faktem,že během session zpracovává data, která s indexem př́ımo nesouviśı (analýzyr̊uzných skupin slov, grafy, obrázky apod.).

Zaj́ımavé by též bylo udělat takovou implementaci, která by byla schopná efek-tivněji využ́ıvat v́ıce vláken a mohla být spustitelná na v́ıce poč́ıtač́ıch současně.Pak by se počet zpracovaných stránek mohl pohybovat v řádově vyšš́ıch č́ıslech,č́ımž by se zvýšila i relevance vrácených výsledk̊u při vyhledáváńı.

7.2 Aktualizace indexu

V současné době je index vybudován na základě jedné rozsáhlé crawling session.Pro lepš́ı výsledky vyhledáváńı by ale bylo třeba implementovat možnost, jaktento index dynamicky rozšǐrovat během jiných session.

Daľśı možnost́ı by bylo vybrat určitou skupinu stránek (ideálně takovou, kdese stránky často měńı) a na ńı provádět s časovým odstupem opakované pro-hledáváńı a aktualizovat obsah indexu jednotlivých stránek. V kombinaci srozšǐrováńım indexu bychom tak měli prvńı krok k vybudováńı rozsáhleǰśıhovyhledávače.

41

7.3 Podpora jazyk̊u

Momentálně náš software funguje hlavně na stránkách v Angličtině, nebot’ ang-lická podstatná jména se neskloňuj́ı, což naši práci značně usnadňuje. Nicméně izde by se dala udělat řada vylepšeńı, které se týkaj́ı gramatiky (v současné doběnáš crawler např. bere ”dog”a ”dogs”jako dvě naprosto odlǐsná slova). V př́ıpaděněmeckého nebo českého jazyka by náš software již ale narazil na řadu problémů(když pomineme problematiku zpracováńı české diakritiky) kv̊uli rozlǐsováńıpád̊u a r̊uzných tvar̊u slov. Tato tématika je značně rozsáhlá a v př́ıpadě bu-dováńı vyhledávače by bylo nutné se j́ı podrobně zabývat.

V tomto ohledu se nab́ıźı hned daľśı možné rozš́ı̌reńı, a to analýza textu zaúčelem identifikace synonym. Pak by bylo možné mnohem efektivněji identifiko-vat stránky, které se zabývaj́ı podobnou tématikou. Identifikace synonym v textuse většinou dělá pomoćı hledáńı slov, které se vyskytuj́ı ve stejném kontextu (tzn.ve stejných větách na určitém mı́stě). Touto tématikou se zabývá např́ıklad tatostudie[Cap03]. Jedńım z problémů takové identifikace je ale např́ıklad obt́ıžnérozlǐsováńı synonym a antonym. T́ım se zabývá např́ıklad krátké shrnut́ı Iden-tifying Synonyms among Distributionally SimilarWords z roku 2003[LZQZ03].Jednou z metod takového rozlǐseńı je např́ıklad zasazeńı potenciálńıch synonymdo nějakého kontextu (např. dosazeńım do slovńıho spojeńı ”from X to Y”nebo”either X or Y”). Pokud se slova X a Y vyskytuj́ı v takovém významu, zřejměnep̊ujde o synonyma (např. ”from ally to foe”se bude vyskytovat sṕı̌se než ”fromfoe to opponent”). Jinými slovy existence takového spojeńı může identifikovatantonyma.

7.4 Rozpoznáváńı struktury stránek

Kĺıčově informace se na stránkách často vyskytuj́ı pouze v určitých sekćıch. Vel-kou část textového obsahu mnoha stránek tvoř́ı pro nás naprosto nerelevantńıinformace jako např. reklamy, zpětné odkazy nebo r̊uzné komentáře apod. Iden-tifikováńım těch kĺıčových sekćı bychom dosáhli mnohem efektivněǰśıho využit́ıčasu i paměti během crawling session, nebot’ bychom se vyhnuli zbytečnémuzpracováńı nadbytečných dat.

Kromě toho náš crawler momentálně ignoruje hmtl syntax stránky a všemslov̊um přǐrazuje stejnou d̊uležitost. Přitom např́ıklad se zvýrazněněnými slovya nadpisy by se mělo zacházet jinak než s výrazy, které se vyskytuj́ı v běžnémtextu.

7.5 Učeńı

Je jasné, že programovat crawler tak, aby se z něj stal plnohodnotný vyhledávač,jako je např. Google, asi nemá smysl. My bychom se tedy potřebovali vydattakovým směrem, abychom vytvořili software, jež bude budovat index speciali-zovaný na určité téma. Crawler by se tedy měl umět učit (za podpory uživatele)

42

indentifikovat takové stránky, které jsou v daném tématu relevantńı. Již jsmezmı́nili tzv. beam search, což je jedna z možnost́ı, jak při vyhledáváńı postupo-vat. Kromě toho je ale potřeba implementovat nějakou heuristiku, která by vkombinaci s použitou metrikou hodnoceńı relevance stránek crawleru směrovalak relevantńımu obsahu.

Již jsme implementovali učeńı se novým stop words. Ted’ by měla přij́ıt nařadu daľśı učeńı - označeńı relevantńıch stránek, dynamické hodnoceńı stránekv pr̊uběhu prohledáváńı za použit́ı existuj́ıćıho indexu společně s implementaćıprioritńı fronty, aby stránky, u kterých je vyšš́ı pravděpodobnost obsahu re-levantńıch informaćı, byly staženy přednostně. Současně s t́ım by bylo třebazměnit metriku z čistého TF-IDF např. na kombinaci TF-IDF a PageRanku,aby byla zohledněna i hyper-link struktura stránek.

43

8 Závěr

Ćılem této bakalářské práce bylo navrhnout crawler, který bude schopen samo-statně vyhledávat informace na Webu a své vyhledáváńı zpřesňovat na základěinterakce s uživatelem.

V prvńı kapitole je rozebrána dnešńı podoba internetu a stručný úvod do pro-blematiky webcrawlingu. Následuje přehled technik použ́ıvaných pro ćılené vy-hledáváńı informaćı na Webu. Ve třet́ı kapitole následuje přehled zp̊usob̊u výpočtuhodnoceńı stránek na základě jejich relevance. Čtvrtá kapitola se věnuje několikapř́ıklad̊um existuj́ıćıho softwaru včetně velkých vyhledávač̊u.

Zbytek práce je věnován popisu konkrétńı implementace crawleru a prezentacidosažených výsledk̊u na třech vyhledávaćıch scénář́ıch. Posledńı, sedmá, kapi-tola je věnována nast́ıněńı daľśıho postupu, aby se z výsledného crawlera stalužitečný nástroj.

Nyńı je čas na shrnut́ı celé práce. Podařilo se vytvořit funguj́ıćı implemen-taci, která samostatně vyhledává informace na Webu podle zadaných specifikaćı.Aplikace má ale několik nedostatk̊u, které již byly zmı́něny v předchoźıch kapi-tolách. Tou nejzávažněǰśı je asi nutnost započ́ıt vyhledáváńı poměrně bĺızko hle-daného tématu, aby byl výstup relevantńı. To je dáno hlavně malým výkonem,který je limitován použit́ım crawlera na jediném poč́ıtači. Vyhledáváńı je paktedy př́ılǐs pomalé a neefektivńı. V sedmé kapitole je ale popsáno několik zp̊usob̊u,jak tohoto crawlera vylepšit a tyto nedostatky překonat.

V současné době je tato aplikace vhodná pro podrobněǰśı analýzu středně velkýchkolekćı stránek (3 - 8 tiśıc stránek), předevš́ım na lexikografickém základu.Kromě toho tento crawler produkuje řadu statistik týkaj́ıćıch se výskyt̊u slova podobnosti prohledaných stránek, což z něj může dělat nástroj vhodný prozkoumáńı struktury dnešńıho Webu. Tyto výsledky si lze prohlédnout na přiloženémCD.

Jsem si vědom, že některé témata nejsou rozebrána př́ılǐs do hloubky. Ćılempráce bylo vytvořit přehled použ́ıvaných technik, kde podrobný popis mnohýchz nich by překročil rámec této práce.

Práce na tomto tématu mě velmi zaujala, bavila a byla pro mne velkým př́ınosem.Dozvěděl jsem se o hlubš́ı podstatě ćıleného vyhledáváńı a