Hlavní navigace

Na stopě internetovým agentům

25. 5. 2006
Doba čtení: 6 minut

Sdílet

Autor: 29
Searchboti. Softwaroví agenti bez přestání prolézají miliardy internetových stránek a vytvářejí si jejich kopie pro potřeby vyhledávačů. Jejich životním prostředím je hypertext. Všechny odkazy na stránce si zaznamenávají, a pokud je nenavštíví hned, po čase se k nim vrací. Vyhledávače si jejich tajemství střeží jako oko v hlavě a o jejich práci se toho mnoho neví.

Searchboti rozhodují o tom, jestli se vaše stránky objeví mezi vyvolenými. Rychlosti datových spojení nerostou tak rychle jako množství internetových stránek. Searchboti tak musí dobře vybírat, jaké stránky vyhledávači uloží. Na všechny se nedostane. Na Wikipedii lze najít zmínku o studii z roku 2000, podle které vyhledávače zaindexují jen asi 16 procent z veřejně přístupných stránek.

V polovině dubna byl po roce ukončen velmi zajímavý experiment, který monitoroval chování tří nejslavnějších internetových agentů: Googlebot, Yahoo Slurp a msnbot. Pro potřeby tohoto experimentu bylo vygenerováno a uspořádáno 2.147.483.647 in­ternetových stránek do struktury binárního vyhledávacího stromu. Z každého uzlu takovéto datové struktury vedou vždy dva odkazy – větve. Následující uzly z každého uzlu směrem doleva mají u takového stromu pořadové číslo (hodnotu) menší, než je hodnota rodičovského uzlu a větve směrem doprava mají pořadová čísla vyšší.

Poslední uzel vlevo tak měl hodnotu jedna a uzlu zcela napravo byla přiřazena hodnota 2.147.483.647­. Výška stromu vyjadřuje počet uzlů, které musíte projít od kořene – výchozího uzlu – k nejvzdálenějšímu uzlu celého stromu. Experimentální strom měl výšku 30 a celkový počet uzlů je tak dán vzorcem 2exp(N+1) – 1 = 2.147.483.647.

U každé stránky (uzlu stromu) byla v období od 13. dubna 2005 až 13. dubna 2006 monitorována aktivita všech tří nejznámějších agentů. Pro obohacení atraktivnosti stránek byla na každou umístěna diskuse a záznamy o návštěvách jednotlivých agentů. Vzorový uzel číslo dvě si můžete prohlédnout na stránkách studie.

Aktivita searchbotů je zachycena do podoby stromu. Zakresleny jsou navštívené uzly a délka větví symbolizuje počet návštěv agenta na jednotlivých stránkách. Od počátku se ukázal jako nejaktivnější Yahoo Slurp. Během roku si vyžádal více než milión stránek a prolezl přes sto tisíc uzlů. Pořád však jde jen o 0,0049 procent z celkového počtu uzlů.

Statistika aktivity sledovaných searchbotů
Yahoo Slurp Googlebot msnbot
Vyžádaných stránek 1.030.396 20.633 4699
Navštívených uzlů 105.961 7556 1390
Z celkového počtu uzlů 0,0049 procent 0,00035 procent 0,000065 procent
Zaindexovaných uzlů 120.000 554 1
Procento zaindexování 113,23 procent 7,33 procent 0,07 procent

Binární strom objevil na stránkách drunkmenworkhe­re.org jako první Yahoo Slurp. Během prvních hodin začal prohledávat strom zuřivou rychlostí 2,3 uzly za vteřinu a ještě během prvního dne jich stihl navštívit přes 30.000. Doporu­čujeme zhlédnout krátkou animaci, která jeho rychlost zachycuje.

Searchboti - slurp
Hustý vyhledávací strom Yahoo Slurp svědčí o vysoké aktivitě

Během následujícího měsíce jeho aktivita ustala, ale po jeho uplynutí navštívil Yahoo Slurp znovu všechny stránky, na kterých už byl před tím. Nepodíval se ovšem na žádnou další. Stejný jev se opakoval téměř na den přesně každý měsíc: 14. května 2005 a 13. června 2005. Počet pageviews dosáhl přesně 90.000, ale žádný nový uzel už agent nezkoumal. Šlo tedy o návštěvy, které měly za cíl pouze aktualizovat cache. Zde je to znázorněno v animaci na stromu, kterému se pouze prodlužují větve.

Teprve po čtyřech měsících začal Yahoo Slurp poprvé od první návštěvy prolézat také nové uzly, jejich počet rychle zdvojnásobil, a pak začal navštěvovat strom pravidelně. Trochu překvapivě neindexoval Yahoo více stránek, než kolik uzlů ve skutečnosti navštívil. Každý uzel byl ovšem přístupný na doméně www.drunkmenwor­khere.org i drunkmenwor­khere.org.

Searchboti - google
Strom Googlu vypadá jako živý, uzly blízko kořenu navštěvoval agent častěji

Binární strom Googlu vypadá trochu více jako skutečný strom, protože Googlebot navštěvoval hlubší uzly s menší frekvencí než ty blíže ke kořenu, a větve se tak postupně zkracují. Yahoo navštěvoval s vyšší intenzitou pouze uzly na prvních třech úrovních, zatímco Google aplikoval různou frekvenci návštěv na uzly ve dvanácti úrovních.

Struktura Google stromu by měla odpovídat PageRanku jednotlivých stránek. Vzhledem k tomu, že drtivá většina uzlů nebyla linkována z jiných stránek a vynecháme-li linky zanechané spamboty v komentářích, lze PageRank každé stránky určit takto:

PR(node) = (1-d) + d (PR(rodič) + PR(levý potomek) + PR(pravý potomek))/3

Parametr d se pohybuje mezi hodnotami 0 a 1, přičemž ve většině případů je jeho hodnota nastavena na 0,85. Na následujícím grafu si můžete prohlédnout, jak autor studie vygeneroval na základě tohoto vzorce ideální Google strom s hloubkou 17. PageRank každého uzlu symbolizují délky větví. Neznámý PageRank kořenu stromu nastavil autor na hodnotu 100.

Searchboti - google2
Takto by měl vypadat vyhledávací strom Googlu, kdyby agent postupoval pouze podle PageRanku

Na animaci postupu Googlebota lze ovšem vysledovat prvky nevyzpytatelného chování. Hned z počátku agent preferoval uzly na pravé straně stromu a 4. července 2005 dokonce dosáhl uzel s nejvyšším pořadovým číslem. To se na jeho stromu projevilo zakroucenou větvičkou na pravé straně. Na konci června dosáhl Googlebot na protější krajní uzel s pořadovým číslem 1, ale přišel zcela neznámou cestou, nikoliv přes jeho otce. Po několika hodinách navštívil agent uzel s pořadovým číslem 2, který byl nad ním.

Za několik dnů se Googlebot vrátil a během 20 vteřin dokázal nalézt cestu od kořene stromu až k dříve objevenému uzlu 2. Musel přitom projít přes 24 neznámých uzlů, na jistotu bez jediné chybné odbočky vpravo dorazil až k uzlu 2. Je zajímavé, že po celý zbytek pokusu – devět měsíců už Googlebot ani jednou tuto cestu nenavštívil.

Posledních šest měsíců Google navštěvoval průměrně 260 stránek za měsíc a stejně jako v případě Yahoo se zdá, že agent střídá období, ve kterých objevuje nové stránky, s těmi, kdy obnovuje cache. Google zaindexoval celkem jen 554 stránek, největší PageRank mají stránky 1 a 2, které jsou velmi hluboko ve stromu na úrovni 30 a 29. Ostatní odkazy na první stránce Googlu pochází ze čtvrté úrovně stromu. První tři byly zřejmě penalizovány kvůli spamem zahlceným komentářům.

Searchboti - msn
MSN se příliš nečinil, jeho strom proto vypadá chudě

Strom MSN vypadá vedle dvou prvních velmi chudě. Je to způsobeno malým počtem navštívených uzlů. Za pozornost stojí větev oddělená od zbytku stromu, která vznikla záměrně umístěným odkazem na uzel z jiné adresy. Uzel na úrovni 24 postupně navštívili všichni agenti a ani jednomu se jej nepodařilo připojit ke kořenu stromu. Stejná situace se opakovala i u druhé utržené větve v horní části.

Na následujícím grafu je zobrazen pozvolný nárůst navštívených uzlů v čase.

Searchboti - graf1
Počet navštívených uzlů v čase

Další graf zobrazuje množství uzlů každé úrovně, které agenti navštívili. Kořen stromu se nachází na úrovni 0, nejvzdálenější uzel na úrovni 30. Kdyby searchboti prolezli všechny uzly stromu, byly by na grafu zachyceny překrývající se přímky.

Searchboti - graf2
Počet prohledaných uzlů na jednotlivých úrovních stromu

Do dvanácté úrovně stromu se takové přímce nejvíce blíží Googlebot. V okamžiku, kdy prolezl 5524 z 8191 možných uzlů, to ovšem vzdal a počet navštívených uzlů se prudce propadl. Podobně postupoval i msnbot, ale trpělivost mu došla už v deváté úrovni (656 z 1023 m­ožných).

Searchboti - graf3
Průměrný počet návštěv na jednotlivých úrovních

Tento graf zobrazuje průměrný počet návštěv agentů na uzlech jednotlivých úrovní. Yahoo Slurp navštěvoval uzly v hlubších částech stromu mnohem častěji než zbylí dva.

Nezaháleli ani spamboti. Do 103 uzlů bylo vloženo celkem 5265 příspěvků, přičemž 32 z těchto uzlů nebylo nikdy navštíveno žádným z vyhledávacích agentů. Drtivá většina komentářů (3652) byla umístěna pouze na root. Nejspamovanější slova se nijak neliší od těch, která končí denně v našich e-mailových schránkách.

CS24 tip temata

Searchboti - graf4
Zastoupení nejčastěji spamovaných slov

Pokus přináší velmi zajímavý pohled do kuchyně nejslavnějších světových vyhledávačů. Máme před sebou data, která odkrývají zvyky tajemných softwarových agentů. Bylo by však chybou vyhledávače na základě těchto dat jakkoliv hodnotit. Pokusné stránky neobsahovaly prakticky žádná data relevantní pro uživatele Internetu, a nelze tak rozhodnout, jestli je chybou, nebo výhodou, že searchbot ztrácel prolézáním binárního stromu drahocenný čas.

Kompletní studii včetně dalších grafů a informací najdete na stránkách drunkmenworkhe­re.org.

Který searchbot si podle vás v pokusu vedl nejlépe?

Autor článku

Autor je redaktorem serveru Mobil.cz....
Upozorníme vás na články, které by vám neměly uniknout (maximálně 2x týdně).