Søkerobot

Ein søkerobot (også kjent som crawler eller spider) er ein Internet-bot som systematisk gjennomgår Verdsveven, typisk for å indeksere nettsidene.

Søkjemotorar og nokre andre nettstader nyttar søkerobotar for å oppdatera innhaldet på vevsidene sine, eller indeksar av nettinnhaldet i andre sider. Søkerobotar kan kopiere alle sidene dei besøkjer for seinare behandling av ein søkjemotor som indekserar nettsidane slik at brukarane kan søke i dei meir effektivt.

Søkerobotar kan validera hyperkoplingar og HTML-kode. Dei kan også nyttast for automatisk nedlasting av vevsinnhald (Web-scraping).

Oversikt

Ein søkerobot starter med ei liste av URL-ar som skal vitjast, kalla frøa. Etter kvart som søkeroboten vitjar desse URLane kan han identifisera alle hyperkoplingane og putta dei i lista over vevsider som skal vitjast. URL-ane frå denne lista blir vitja rekursivt i høve til eit sett med reglar. Dersom søkeroboten driv meir arkivering vil han lagra informasjonen etter kvart som han mottek ho. Slike arkiv er som regel lagra slik at dei kan nyttast som om dei var vanlige nettstader på verdsveven, sjølv om dei er lagra som augneblinksbilete av sida.

Det store volumet av nettsider impliserar at søkeroboten berre kan laste ned eit avgrensa antal av vevsidene på tida han har til råde, så han treng å prioritera nedlastingane sine. Den høge endringstakta på verdsveven tilseiar at vevsider allereie kan ha blitt oppdaterte eller til og med sletta innan roboten er ferdig med arbeidet sitt.

Talet på mulige URL-ar som blir genererte dynamisk fra serverprogram gjer det vanskelig for roboten å unngå å lasta ned duplikatar av sider han allereie har vitja. Sjølv om W3C åtvarar mot å nytta meir enn 255 byte i ein HTTP GET førespurnad, tilsvarar det $256^{256}\approx 3,2\times 10^{616}$ sider som kan genererast, og ein kan derfor ikkje gjetta seg til gyldige GET-førespurnadar. I tillegg kan same innehald lenkjast til på fleire forskjellige måtar. Til dømes kan ei vevsapplikasjon som serverer nyheitsmeldingar frå forskjellige årstal tilby eit felt for årstal, og eit felt for svartype. Om du då spesifiserar example.com/?årstal=2000&datatype=XML er dette nøyaktig det same som å spesifisera example.com/?datatype=XML&årstal=2000. Då får du eit problem når same informasjon kan lenkjast på forskjellige måtar, og hyperkoplingane dermed ikkje lengre peikar til unikt innhald.

Som Edwards m.fl. nemnar, "Gitt at båndbredda for å tråla korkje er uendelig eller gratis, blir det essensielt å tråla veven på ei ikkje berre skalerbar, men også effektiv måte, om eit fornuftig krav på kvalitet eller fersknad skal oppretthaldast." Ei søkjerobot må difor overveie nøye på kvart et steg kva sider han skal vitja.

Haldningsreglar for tråling

Oppførselen til ei søkerobot er gjeven av ein kombinasjon av haldningsreglar:

• ei Utvalshaldning som gjer kva sider som skal lastast ned,
• ei Omvitjingshaldning som seiar når ein skal vitje sida på ny,
• ei Høfligheitshaldning som seiar korleis ein unngår å overlasta vevsider, og
• ei Paralelliseringshaldning som seiar korleis ein skal samhandle arbeidet mellom fleire søkerobotar som arbeider parallellt.

Utvalshaldning

Gitt den noverande storleiken på Verdveven, vil til og med store søkemotorar dekkje berre ein brøkdel av den offentlege veven. Ei studie frå 2005 viste at storskalasøkjemotorar ikkje indekserte meir en berre 40-70 % av den indekserbare verdsveven. Ei tidlegare studie av Steve Lawrence og Lee Giles viste at ikkje nokon søkjemotor indekserde meir enn 16% av veven i 1999. Sidan ein søkerobot berre lastar ned ein brøkdel av vevsidene, er det høgst ønskelig at den nedlasta brøkdelen inneheld dei mest relevante sidane, og ikkje berre eit tilfeldig utval av verdsveven.

Dette krev eit mål viktigheita for å kunne prioritera vevsider. Viktigheita av ei side er ei funksjon av sidas egenkvalitet, popularitet i termar av besøkande eller lenkjar, eller til og med i termar av sidas URL om trålinga omhandlar eit og berre eit toppnivådomene. Formgiving av ei god utvalshaldning har ei ekstra vanskefaktor, med at ho må verka med ukomplett informasjon, sida den totale mengda vevsider ikkje er kjent mens ein trålar.

Cho m.fl. skapte den første studia om haldningsreglar for tidsplanlegging av trålarar. Datasettet deira var ei 180 000 sider lang tråling frå standord.edu domenet, der trålingssimuleringa var utprøvd med forskjellige strategiar.

Sorteringsreglane som ble testa var bredde fyrst, oppteljing av tilbakekoplingar (backlink), og delvis berekningar av Pagerank. Ei av konklusjonane var at om ein ynskte å lasta ned sider med høg Pagerank tidlig i trålingsprosessen, så var delvis Pagerank betre, følgd av Bredde-fyrst og teljing av tilbakekoplingar. Ein må hugse på at desse resultata berre var for eit enkelt domene. Cho skreiv også doktorgraden si på Stanford om søkerobotar.

Najork og Wiener utførte også ei faktisk tråling på 328 millionar sider, og nytta bredde-fyrst sortering. Deira funn var at bredde-fyrst tråling lasta tidleg ned sider med høg Pagerank, men dei samanlikna ikkje denne stragien med mot andre strategiar. Forklaringa forfattarane gav var at "dei viktigste sidane har mange lenkjer i seg frå mange sider, og desse linkane vil bli funne tidleg, uavhengig frå kor trålinga starta."

Abiteboul formgav ei trålingsstrategi basert på ei algoritme kalle OPIC (On-line Page Importance Computation). Under OPIC, er kvar side gitt ei startmengde med "pengar" som er jevnt fordelt over sidane ho pekar til. Ho liknar på Pagerank-berekningar, men er raskare og blir berre gjort i eit steg. Ei OPIC-søkerobot lastar fyrst ned sidane i toppen av lista si som har mest kontantar. Forskjellige eksperiment ble utført på ei 100 000 siders syntetisk graf med ei distribusjon av koplingar som per potenslova. Men det var ingen samanlikning med andre strategiar eller eksperimentar på den faktiske verdveven.

Boldi m.fl nytta ei simulasjon av eit subsett av veven på 40 millionar sider frå .it toppnivådomenet, og 100 millionar sider frå WebBase trålinga, og testa bredd mot dybde først sortering, tilfeldig orden og ei allvitane strategi. Samanlikninga baserte se på der bra PageRank berekna på ei delvis tråling approksimerte den sanne Pagerank verdia. Overraskande nok, ville noke nitjinga som akkumulerte Pagerank veldig raskt gje veldig dårleg progressive approksimasjonar.

Baeza-Yates m.fl. nytta ei simulasjon på to subsett av verdsveva på 3 millionar sider frå .gr og .cl domena, og testa fleire trålingsstrategiar. Dei vista at både OPIC og ei strategi som nytte lengda på per-sida køane er betre enn bredde-fyrst tråling, og at det også er særs effektivt å nytte ei tidlegare tråling, når ho er tilgjengelig, til å guida den noverande.

Daneshpajouh m.fl. formga ei samfunnsbasert algoritme for å oppdage gode frø. Metoden deira tråla vevsider med høg Pagerank frå forskjellige samfunn i færre iterasjonar samanlikna med trålingar som starta frå tilfeldige frø. Ein kan utvinna gode frø frå ei tidlegare tråling om ein nyttar denne metoden. Om ein nyttar desse frøa kan ei ny tråling bli veldig effektiv.

Begrense koplingar som følgast

Ei søkerobot kan ønskje å berre lasta ned HTML-sider og unnga alle andre MIME-typar. For å berre nytte HTML-ressursar kan ei søkerobot nytte ei HTTP HEAD førespurnad for å avgjere vevsressursen's MIME-type før han ber om heile ressursen med ein GET førespurnad. For å unngå å nytte for mange HEAD førespurnadar kan ein søkerobot undersøke URL en og berre spørre om ressursen om URL-en enda på eit gitt suffiks som .html, .htm, .asp, .php, .jsp eller liknande. Denne strategien kan medføra at mange HTML-ressursar blir hoppa over.

Nokre trålarar kan unngå å be om ressursar som har eit spørjeteikn ('?') i seg, for å unngå uendelege rekursjonar og ende opp med å lasta ned eit uendeleg antal URLar frå ei vevside. Denne strategien er ustabil om sida nyttar ei somskrivingsmotor (rewrite engine) for å forenkla URL-ane sine.

URL normalisering

Søkerobotar utførar vanlegvis ei eller anna form for normalisering over URL-ane sine for å unngåå å tråla samme ressursen meir enn ein gang. Termen URL normalisering refererar til prosessen med å modifisera og standardisera ei URL på eit konsistent vis. Det er flere typer normalisering som kan utførast, som til dømes konvertering av URL til små bokstavar, fjerning av "." og ".." segmentar og suffiksing av ei skråstrek '/' på slutten av ei URL.

Stiklatrande søkerobotar

Nokre søkerobotar ynskjer å lasta ned så mange ressursar som mogleg frå ei gitt vevside.Stiklatrande søkerobotar ble intdodusert for å klatra opp alle stiane i ei gitt URL som den ynskjer å tråla. Tili dømes, gitt ei frø-URL som example.com/apekatt/kråke/index.html, vil ho forsøke å tråla /apekatt/kråke/, /apekatt/, og /. Cothey fann at ei stiklatrande søkerobot var særs effektiv til å finna isolerte ressursar, eller ressursar utan nokon link som peikte til henne.

Omvitjingshaldning

Verdsveven har ei veldig dynamisk natur, og tråling ei brøkdel av veven kan ta ukar eller månader. Innan ei søkerobot har blitt ferdig med trålinga si, kan mykje ha skjedd, inkludert oppdateringar og slettingar av innhold. Frå ei søkjemotors perspektiv er det ein kostnad knytt til å ikkje oppdaga ei hending, dermed å ha ein utdatert versjon av ressursen. Dei mest nytta kostnadsfunksjonane er ferskheit og alder.

Ferskheit Dette er eit binært mål som indikerar om den lokale utgåva av ein ressurs er nøyaktig eller ikkje. Ferskheten av sida p i repositoriet ved tid t er definert som:

$F_{p}(t)={\begin{cases}1&{\rm {hvis}}~p~{\rm {~er~lik~lokal~versjon~ved~tid}}~t\\0&{\rm {ellers}}\end{cases}}$

Alder: Eit mål som indikerar kor utdatert den lokale utgåva er. Alderen av ei side p i repositoriet ved tid t er definert som:

$A_{p}(t)={\begin{cases}0&{\rm {hvis}}~p~{\rm {~er~ikkje~endra~ved~tid}}~t\\t-{\rm {tdispunkt~for~endringa}}~p&{\rm {ellers}}\end{cases}}$

Høfligheitshaldning

Søkerobotar kan be om data mykje raskare og i større dybde enn menneskelege brukarar, så dei kan ha ei paralyserande effekt på sidas ytelse. Derfor er det viktig å ikkje ta for stort beslag på nettjenaranes ressursar ved å til dømes be om mange ressursar per sekund, lasta ned store filar, eller liknande.

Som påpekt av Koster, er bruken av søkerobotar nyttig for mange oppgåver, men kommer med ei prislapp for det generelle samfunnet. Kostnadene inkluderer:

• nettverksressursar, sidan søkerobotane treng betydelige mengdar bandbredde og opererar med ei høg grad av paralellisering over ei lengre tidsperiode.
• Overlasting av tjenarar, spesielt om frekvensen på førespurnader er for høg.
• Dårlig skrevne søkerobotar som kan krasje tjenarar og rutarar, eller som lastar ned sider dei ikkje kan ta hand om.
• Personlege søkerobotar som om dei blir nytta av for mange brukarar, kan forstyrre nettverk og tjenarar.

Ei delvis løysing til desse problema er Robots Exclusion Standard, ein protokoll som er ei standard for administratorar for å indikera kva for delar av nettjenarane deira som ikkje skal trålast av søkerobotar. Denne standarden inkluderer ikkje eit forslag for intervallet på førespurnadar til sida, sjølv om dette intervallet er den mest effektive måten å unngå overlasting av tjenare på. Nyleg har kommersielle søkemotoraktørar som Google, Ask Jeeves, Yahoo! og Bing implementert ei moglegheit for å nytta eit "Crawl-delay:" parameter i robots.txt fila for å indikera antall sekundar dei bør vente mellom førespurnader.

Det første foreslåtte intervaller mellom nedlastingar var 60 sekundar. Dessverre, viss sider blei lasta ned på denne hastigheita frå ei nettstad med meir enn 100 000 sider over ei perfekt tilkopling, med null ventetid og uendeleg bandbredde ville det tatt over 2 månader å laste ned berre den nettstaden. I tillegg ville berre ei liten brøkdel av ressursane frå den nettjenaren bli nytta.

Paralelliseringshaldningar

Ei paralell parallell søkerobot er ein robot som køyrer fleire prosessar parallelt. Målet er å maksimera nedlastingsraten samtidig som ein minimerar ekstrakostnadene som følgjer med å køyre parallellt, og unngå å lasta ned same side meir enn ein gong.

For å unngå å laste ned same side meir enn ei gong, krev trålingssystemet ei haldningsregel for å tilordne nye URLar som blir oppdaga under trålinga, sidan den same URLen kan oppdagast av to forskjellige trålingsprosessar.

Søkerobotsidentifikasjon

Søkerobotar identifiserar seg vanlegvis via å nytte User-agent feltet i ein HTTP-førespurnad. Vevsideadministratorar kan dermed sjekke loggane sine for å sjå kva for søkerobotar som har besøkt sida og kor ofte. User-agent feltet kan innehalde ein URL som peikar til informasjon om agenten og kva han er til for. Det finnest og verkty som kan automatisk sjekka for søkerobotar.

Det er viktig for søkerobotar å identifisera seg sjølv, slik at administratorar kan kontakte eigarane om det trengs. Nokre gongar kan ein søkerobot sette seg fast, og lasta ned same side om att og om att, og eigaren må slå han av. Identifikasjon er også nyttig for administaratorar, slik at dei kan vite omtrent når dei kan forvente at sida deira blir indeksert på forskjellige søkemotorar.

Vidare lesing

• Cho, Junghoo, "Web Crawling Project", UCLA Computer Science Department.
• A History of Search Engines, from Wiley
• A tutorial Arkivert 2014-05-09 ved Wayback Machine. for creating basic crawlers.
• WIVET is a benchmarking project by OWASP, which aims to measure if a web crawler can identify all the hyperlinks in a target website.
• Shestakov, Denis, "Current Challenges in Web Crawling", slides for a tutorial presented at ICWE'13.