Søkerobot

Frå Wikipedia – det frie oppslagsverket
Gå til: navigering, søk

Ein søkerobot (Også kjent som ein 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 kopierer 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[endre | endre wikiteksten]

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. URLane frå denne lista blir vitja rekursivt i henhald til eit sett med reglar. Dersom søkeroboten driv mer 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.[1]

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

Talet på mulige URLar som genererast 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[2], 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."[3] Ei søkjerobot må difor overveie nøye på kvart et steg kva sider han skal vitja.

Haldningsreglar for tråling[endre | endre wikiteksten]

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

  • 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 arbeide mellom fleire søkerobotar som arbeidar parallellt.

Utvalshaldning[endre | endre wikiteksten]

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.[5] Ei tidlegare studie av Steve Lawrence og Lee Giles viste at ikkje nokon søkjemotor indekserde meir enn 16% av veven i 1999.[6] Sidan ei søkerobot berre lastar ned ein brøkdel av vevsidane, er det høgst ønskelig at den nedlasta brøkdelen inneheld dei mest relevante sidane, og ikkje berre eit tilfeldig utval av verdveven.

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 holdningsreglar for tidsplanlegging av trålarar. Datasettet deira var ei 180 000 sider lang tråling frå standord.edu domenet, der trålingssimularinga var utprøvd med forskjellige strategiar.[7]

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 kun var for eit enkelt domene. Cho skreiv også doktorgraden si på Stanford om søkerobotar.[8]

Najork og Wiener utførte også ei faktisk tråling på 328 millionar sider, og nytta bredde-fyrst sortering.[9] 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).[10] 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ørd 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å kor 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.[11][12]

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.[13] 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ø.[14] 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[endre | endre wikiteksten]

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 URLen 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 URLane sine.

URL normalisering[endre | endre wikiteksten]

Søkerobotar utførar vanlegvis ei eller anna form for normalisering over URLane 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.[15]

Stiklatrande søkerobotar[endre | endre wikiteksten]

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.[16] 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[endre | endre wikiteksten]

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 ei kostnad knytta til å ikkje oppdaga ei hending, dermed å ha ein utdatert versjon av ressursen. Dei mest nytta kostnadsfunksjonane er ferskheit og alder.[17]

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[endre | endre wikiteksten]

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.[18] Kostnadene inkluderar:

  • 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.[19] Denne standarden inkluderar 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.[20] Desverre, 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[endre | endre wikiteksten]

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[endre | endre wikiteksten]

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.

Referansar[endre | endre wikiteksten]

  1. MasaTalet på mulige URLar som genererast 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[2], 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.nès, Julien (February 15, 2007). Web Archiving. Springer. s. 1. ISBN 978-3-54046332-0. 
  2. name=HTTP/1.1 standardenDoe, John (30 April 2005). «My Favorite Things, Part II». Open Publishing. http://www.example.org/. Henta 6 July 2005. 
  3. Edwards, J., McCurley, K. S., and Tomlin, J. A. (2001). «An adaptive model for optimizing performance of an incremental web crawler». In Proceedings of the Tenth Conference on World Wide Web (Hong Kong: Elsevier Science): 106–113. doi:10.1145/371920.371960. 
  4. Mal:Cite thesis
  5. A. Gulli; A. Signorini (2005). «The indexable web is more than 11.5 billion pages». Special interest tracks and posters of the 14th international conference on World Wide Web. ACM Press.. pp. 902–903. doi:10.1145/1062745.1062789. http://doi.acm.org/10.1145/1062745.1062789. 
  6. Steve Lawrence; C. Lee Giles (1999-07-08). «Accessibility of information on the web». Nature 400 (6740): 107. Bibcode 1999Natur.400..107L. doi:10.1038/21987. PMID 10428673. 
  7. Cho, J.; Garcia-Molina, H.; Page, L. (April 1998). «Efficient Crawling Through URL Ordering». Seventh International World-Wide Web Conference. Brisbane, Australia. http://ilpubs.stanford.edu:8090/347/. Henta 2009-03-23. 
  8. Cho, Junghoo, "Crawling the Web: Discovery and Maintenance of a Large-Scale Web Data", Ph.D. dissertation, Department of Computer Science, Stanford University, November 2001
  9. Marc Najork and Janet L. Wiener. Breadth-first crawling yields high-quality pages. In Proceedings of the Tenth Conference on World Wide Web, pages 114–118, Hong Kong, May 2001. Elsevier Science.
  10. Serge Abiteboul; Mihai Preda; Gregory Cobena (2003). «Adaptive on-line page importance computation». Proceedings of the 12th international conference on World Wide Web. Budapest, Hungary: ACM. pp. 280–290. doi:10.1145/775152.775192. ISBN 1-58113-680-3. http://www2003.org/cdrom/papers/refereed/p007/p7-abiteboul.html. Henta 2009-03-22. 
  11. Paolo Boldi; Bruno Codenotti; Massimo Santini; Sebastiano Vigna (2004). «UbiCrawler: a scalable fully distributed Web crawler». Software: Practice and Experience 34 (8): 711–726. doi:10.1002/spe.587. 
  12. Paolo Boldi; Massimo Santini; Sebastiano Vigna (2004). «Do Your Worst to Make the Best: Paradoxical Effects in PageRank Incremental Computations». Algorithms and Models for the Web-Graph. ss. 168–180. http://vigna.dsi.unimi.it/ftp/papers/ParadoxicalPageRank.pdf. Henta 2009-03-23. 
  13. Baeza-Yates, R., Castillo, C., Marin, M. and Rodriguez, A. (2005). Crawling a Country: Better Strategies than Breadth-First for Web Page Ordering. In Proceedings of the Industrial and Practical Experience track of the 14th conference on World Wide Web, pages 864–872, Chiba, Japan. ACM Press.
  14. Shervin Daneshpajouh, Mojtaba Mohammadi Nasiri, Mohammad Ghodsi, A Fast Community Based Algorithm for Generating Crawler Seeds Set, In proceeding of 4th International Conference on Web Information Systems and Technologies (WEBIST-2008), Funchal, Portugal, May 2008.
  15. Pant, Gautam; Srinivasan, Padmini; Menczer, Filippo (2004). «Crawling the Web». I Levene, Mark; Poulovassilis, Alexandra. Web Dynamics: Adapting to Change in Content, Size, Topology and Use. Springer. ss. 153–178. ISBN 978-3-540-40676-1. http://dollar.biz.uiowa.edu/~pant/Papers/crawling.pdf. Henta 2009-03-22. 
  16. Cothey, Viv (2004). «Web-crawling reliability». Journal of the American Society for Information Science and Technology 55 (14): 1228–1238. doi:10.1002/asi.20078. 
  17. Junghoo Cho; Hector Garcia-Molina (2000). «Synchronizing a database to improve freshness». Proceedings of the 2000 ACM SIGMOD international conference on Management of data. Dallas, Texas, United States: ACM. pp. 117–128. doi:10.1145/342009.335391. ISBN 1-58113-217-4. Arkivert frå originalen den 2003-08-18. http://web.archive.org/web/20030818093005/http://www.cs.brown.edu/courses/cs227/2002/cache/Cho.pdf. Henta 2009-03-23. 
  18. Koster, M. (1995). Robots in the web: threat or treat? ConneXions, 9(4).
  19. Koster, M. (1996). A standard for robot exclusion.
  20. Koster, M. (1993). Guidelines for robots writers.

Vidare lesing[endre | endre wikiteksten]

Broom icon.png Denne artikkelen kan ha godt av ein språkvask, som reinskar opp målføringa og/eller innfører same språkstilen overalt.