Documentverwerking P10 Zoekrobotten
Prof.Dr.ir. Patrick P. Bergmans Prof.Dr.ir. Faculteit IngenieursWetenschappen Universiteit Gent
Zoekrobotten (1) Doelstelling van Zoekrobotten: het vinden van documenten,, in grote g documentverzamelingen, g , die beantwoorden aan bepaalde eigenschappen Documenttypes: html, pdf, andere Eigenschappen: meestal het bevatten van een aantal trefwoorden, opgegeven a.d.h. een vraag (query) Eigenschappen kunnen ook anders zijn (metadata) Zoekrobotten voor de WWW Eigenlijk een gigantisch “hyperlinked” document Zoekrobotten voor DMS (Document Management Systems) Belangrijk conceptueel verschil: Documenten worden op de WWW totaal ongecontroleerd geplaatst Het opslaan van documenten in DMS gebeurt volledig gecontroleerd 2
Zoekrobotten (2) Zoekrobotten voor de WWW Hoe groot is de WWW (aantal bladzijden)? Enkele duizendtallen in het begin (1990+) 20 miljard vandaag Tot een paar jaar geleden geleden, >50% Engelstalig De meeste zoekrobotten zijn zelf bereikbaar via het Internet, als zgn. “web “web-toepassingen” op een bepaald adres www.google.com of IPIP-adres 64.233.183.99 Hoe werkt zo’n zoekrobot? Gebruik van (soms zeer uitgebreide) indextafels, waarvan de opbouw een totaal afzonderlijk proces is Indextafels bevatten de trefwoorden waarop kan gezocht worden Zoektijd k d is dus d allen ll d de zoektijd k d in die d indextafels d f l 3
Zoekrobotten (3) Korte geschiedenis: Archie,, 1990, Archie 1990 McGill University University;; eigenlijk geen WWW zoekrobot, maar een FMS zoekrobot, voorganger van DMS zoekrobotten Lycos,, 1994, Carnegie Mellon University; Lycos University; ongeveer 1 000 000 documenten geïndexeerd 1.000.000 Altavista,, 1995, Digital Equipment Corp; Altavista Corp; eerste meertalig zoekrobot (ENG, FRA, ESP, GER, POR, ITA, RUS) Google, 1998 1998-2001, Google Corp; Corp; ontworpen voor massieve opschaling (duizendtallen computers onderhouden de index) Baidu,, 1999, Baidu 1999 China; eerste Chinees zoekrobot; gecensureerd door Chinese regering Quaero,, 2006, Europa; multimedia zoekrobot (beelden, Quaero klanken, enz enz)) Zie www.searchengines.com 4
Zoekrobotten (4)
Uit Wikipedia ©
5
Zoekrobotten (5) Prestatieparameters van zoekrobotten, op een gestelde vraag: Recall: het aantal gevonden documenten Recall: Relevance:: een maat van hoe sterk de gevonden Relevance g documenten aan de vraag beantwoorden Return time: de tijd nodig om de documenten te vinden ((of liever,, referenties naar die documenten)
Typische verhouding tussen “recall “recall”” en relevance”: ”: “relevance Relevance
Recall
6
Zoekrobotten (6) Zoekvragen zijn Boolese uitdrukkingen met En AND + & Of OR | Niet NOT - ! Nabij NEAR ~ Vorming van zinnen “ … “ Gebruik van haakjes ( ) is meestal toegelaten B k Bijkomende d opties op b bepaalde ld zoekrobotten k b Datum Formaat van de bestanden Filters Benadrukken van gezochte trefwoorden Taalfuncties f Beperkte zoekgebieden 7
Zoekrobotten (7) Opbouwen van de index: door “(Web) Crawlers Crawlers”” (kruipprogramma’s) (kruipprogramma s) Maken de ronde van de WWW; starten met een lijst van vooropgestelde URL’s Halen bladzijden in; deze fase wordt soms “spider” genoemd; opgehaalde bladzijden worden opgeslagen in een “cache” Extraheren van trefwoorden uit de bladzijden en stoppen die in de index (“indexer (“indexer”) ”) Identificeren hyperlinks yp in de bladzijde, j , en ze doorgeven aan de “spider”
Details over de werking van web crawlers worden dikwijls geheim gehouden door de firma firma’ss die ze uitbaten 8
Zoekrobotten (8) (Web) crawlers worden ook anders genoemd: bots, wanderers,, agents, wanderers agents, enz Web crawlers kunnen ook andere taken vervullen Geautomatiseerd onderhoud van web sites Verzamelen V rzam n van an sp specifieke cf informatie nformat (e(e ( -mail ma adressen, telefoonnummers) Bewaking en detectie van nieuwigheden Verzameling g van statistische gegevens g g Architectuur van web crawlers Gecentraliseerd: bestaat praktisch niet meer Parallel: om vanuit verschillende processen, bladzijden in parallel op te laden Gedistribueerd: parallel maar ook fysisch verdeeld Getypeerd: yp zoekproces p beperkt p zich tot bepaalde p types 9
Zoekrobotten (9) Strategie van web crawlers Selectiestrategie bepaalt welke bladzijden opgeladen worden • Ontdekkingsmechanisme (exploratie) • Filtering bepaalt welke bladzijden weerhouden worden
Prioriteitstrategie bepaalt de volgorde Herneemstrategie bepaalt wanneer reeds bezochte bladzijden bl d ijd n opnieuw pni b bekeken k k n worden d n ((cache h refresh) f h)
Parameters van een bladzijde in de cache van een zoekrobot/crawler Versheid (freshness): {0, 1} functie van de tijd die aanduidt dat de cache een exacte kopie bevat Ouderdom (age): functie van de tijd die de tijd sedert d t d de llaatste t t nietniet i t-gedetecteerde d t t d wijziging ij i i aangeeft 10
Zoekrobotten (10)
Gemiddelde versheid moet zo hoog mogelijk zijn Gemiddeld ouderdom moet zo laag g mogelijk g j zijn j 11
Zoekrobotten (11) Herneemstrategie (revisiting) kan Uniform zijn tt.o.v. o v wijzigingsfrequentie van bladzijden Snelveranderende bladzijden frequenter hernemen E Een mengsell van beide b id aanpakken kk
“Beleefdheid” van web crawlers
Crawlers moeten opletten om web servers met beperkte prestatie niet nodeloos zwaar te belasten Slecht ontworpen crawlers kunnen web servers “platleggen”; vergelijkbaar met D.O.S. virussen
Verdedigingsmechanisme tegen agressieve crawlers Robot.txt protocol (conventioneel gedefinieerd) in http://www.robotstxt.org/wc/norobots.html http://www robotstxt org/wc/norobots html 12
Zoekrobotten (12) Uitdagingen voor zoekrobotten en crawlers crawlers:: Groei van de WWW: 100 100.000 000 bladzijden per dag!!! Bestaande bladzijden worden ook heel dikwijls aangepast; moeten eveneens opnieuw geïndexeerd worden, uitgenomen als de aanpassing triviaal is (klok) Google g index wordt “in parallel” p onderhouden door meer dan d 5.000 5 000 computers
De “deep “deep web”
Informatie op de WWW die schuilt in databanken (SQL, Access, enz enz)) Bladzijden worden met deze informatie dynamisch pg n.a.v. ondervragingen g g opgebouwd Web sites met toegangscontrole 13
Zoekrobotten (13) DMS-gerichte zoekrobotten DMSH opslaan/wijzigen Het l / ij i van een document d in i een DMS geeft een signaal door aan de indexmanager, dat een document (opnieuw) moet geïndexeerd ï d d worden d Omdat het gebeurt met speciale functies van het DMS Kan ook met eenvoudige FMS
Het vernietigen van een document eveneens Zodanig dat referenties naar dit document kunnen ongeldig gemaakt worden • In andere documenten • In de index 14
Zoekrobotten (14) Index kan veel meer dan trefwoorden bevatten Elk document wordt voorzien van metadata metadata, al dan niet automatisch gegenereerd Auteur, oorsprong, enz. Inhoudstafel I h d t f l Historiek van wijzigingen Samenvatting (summarization), automatisch of niet • Eventueel vertaald, automatisch of niet
Semantische trefwoorden Die metadata worden ook geïndexeerd Met vrij complexe operaties, bvb. semantische links Zoekvragen (queries) kunnen ook op specifieke metadata slaan Zoekrobot wordt dan integraal component van DMS 15
Zoekrobotten (15) Ander type zoekrobotten: meta meta-zoekrobotten Hebben zelf geen index Vormen de vraag om naar de vraagvorm van een of meerdere andere robotten Sturen Stur n de vraag raag door, oor, soms naar tientallen t nta n zoekrobotten, die wel over indextafels beschikken Verzamelen de resultaten Passen bepaalde p criteria toe, en tonen geconsolideerde g resultaten lt t aan de d gebruiker b ik Bijkomende eigenschappen van meta meta-zoekrobotten Beheren van toegangsrechten Groeperen van resultaten (“clusteren”) Andere functies, zoals vertaling van de vraag, expansie van de vraag, enz. Gemengd d WWW en DMS meta meta-zoekrobotten k 16
De Google Story (1) Waarom is Google zo bijzonder? De creatie van het product/systeem en van het bedrijf De technologie De bedrijfscultuur Het business model • van Google • rond Google
De evolutie van het product/systeem en de strategie van het bedrijf
17
De Google Story (2) Het artikel dat alles begon kwam van twee doctoraatstudenten van Stanford University “The Anatomy of a LargeLarge-Scale Hypertextual Web Search Engine”, g , van Sergey g y Brin and L Lawrence P Page http://infolab.stanford.edu/~backrub/google.html Uit de samenvatting: “To To engineer a search engine is a challenging task task”” Honderdtallen miljoenen Web bladzijden Tientallen of honderdtallen miljoenen verschillende termen Tientallen miljoenen queries per dag • Honderdtallen of duizendtallen per seconde
18
De Google Story (3) Basisconcept: p Grootschalig g Naam: Google is een andere schrijfwijze voor “Googol “Googol”, ”, of 10100 Yahoo! Was er vóór Google, Google maar: Het bijhouden van de “index” van Yahoo! Gebeurt manueel OK voor populaire onderwerpen Ingewikkeld en duur Werkt niet voor gespecialiseerde onderwerpen Zoekrobotten met automatische index, en vergelijking van trefwoorden Leveren te veel resultaten op Kunnen door agressieve adverteerders gestoord worden
19
De Google Story (4) Het artikel verscheen in 1998; het vermeldt World Wide Web Worm (94) 110,000 web bladzijden WebCrawler (97) 2 to 100 million bladzijden Voorziet in 2000 meer dan 1 miljard bladzijden
Het artikel focusseert op “improved “improved search quality” quality” V ll di h id van d Volledigheid de iindex d iis geen garantie ti voor k kwaliteit lit it “Recall” Recall” steeg, maar relevantie werd een probleem Gebruikers kijken j niet verder dan de eerste ((tientallen (tientallen)) resultaten
20
De Google Story (5) In de eerst dagen van Google was Internet snel een belangrijke plaats aan het innemen in de “business “business”” wereld 1993: 1,5% , van alle web sites waren van het .com type yp 1997: 60% van alle web sites Maar ook … de “Internet “Internet bubble bubble”” die barstte in de vroege jaren 2000
Einddoelstelling:
Bouw een architectuur om nieuwe onderzoeksactiviteiten te ondersteunen op (zeer) grote schaal Ondersteun bijkomend onderzoek op een echt draaiend systeem; verschillende onderzoeksprojecten hebben gebruik gemaakt van gegevens ingezameld door Google
21
De Google Story (6) Systeemeigenschappen Gebruik de linkstructuur van de Web om een quality ranking voor elke bladzijde te berekenen; deze ranking heet PageRank (is het “page” page van “web web page page””, of “page” page van “Larry Page Page”” ☺?) De ““citation citation”” of “link graph graph”” van de web is een belangrijk begrip g p dat reeds door andere zoekrobotten werd gebruikt g
De Citation number van een bladzijde is het aantal andere bladzijden die naar die bladzijde wijzen (met html hyperlinks) Niet het Ni h aantall links li k op de d bladzijde, bl d ijd maar Het aantal “backlinks “backlinks””
22
De Google Story (7) PageRank gebruikt dit begrip, begrip maar beschouwt niet alle backlinks als gelijkwaardig; en normaliseert het aantal links op een bladzijde [citaat uit het artikel] We assume page A has T1, T , T2, T , … Tn which point to it. The parameter d is a damping factor, between 0 and 1 (usually d=0,85). C(A) is the number of links out of A. The PageRank of A is PR(A) = (1(1 -d) + d * [ PR(T1)/C(T1) + … + (PR(Tn)/C(Tn) ] [citaat uit het artikel] PageRank for 26 millions web pages can be computed in a few hours on a medium size PC
23
De Google Story (8) Men kan aantonen dat PR(A) de waarschijnlijkheid is dat een “random “random”” surfer op bladzijde A terecht komt, als hij van tijd tot tijd, gedurende het random surfen, van een random bladzijde herbegint Een E Bladzijden Bl d ijd A h heeft ft een hoge h PageRank P R k PR(A) Als er veel bladzijden naar A wijzen Als er enkele bladzijden, j die zelf een hoge PR hebben, naar A wijzen ij
PageRank is een maat van …
De populariteit van een bladzijde Het belang van een bladzijde De relevantie van een bladzijde, als de categorie juist is
24
De Google Story (9) [from Wikipedia]
25
De Google Story (10) “Anchor Anchor text text”” voor links is het gedeelte van de tekst tussen de hyperlink tags: tags:
> anchor text > De meeste systemen beschouwen enkel “anchor text” text” als
belangrijk in de bladzijde die de tekst bevat Google associeert ook de “anchor anchor text text”” met de bladzijde waarneer de link verwijst Het concept werd reeds gebruikt in de World Wide Web Worm Werd W d van in i het h t begin b i ook k door d Google G l gebruikt b ikt
Google steekt ook alle bladzijden opgehaald door de spider in een cache Gedurende het opbouwen van de index, index maakt Google gebruik van formattering informatie in de tekst (bvb. grootte van de tekst)
26
De Google Story (11) De bedrijfscultuur van Google is uiterst open Oprichten van “space “space-age” Googleplex gebouwen waarin werken leuk is
27
De Google Story (12) [ van http://www.google.com/corporate/tenthings.html ]
De ““tien tien g geboden”” van Google geboden g 1. 2. 3 3. 4. 5. 6 6. 7. 8. 9. 10.
Focus on the user and all else will follow. It's best to do one thing really, really well. Fast is better than slow Democracy on the web works You don't need to be at your desk to need an answer You can make money without doing evil There's always more information out there The need for information crosses all borders Y can be You b serious i without i h a suit i Great just isn't good enough
28
De Google Story (13) Het Google businessmodel Het businessmodel voor commerciële zoekrobotten is reclame; de prioritaire resultaten bevatten dikwijls reclame Er zijn twee soorten reclameresultaten op Google bladzijden
29
De Google Story (14) Search Engine Optimization (SEO) Het verkeer naar een web site doen stijgen als het gevolg van natuurlijke zoekactiviteiten, … … door de algoritmen te begrijpen die gebruikt worden door de crawler, de spider en de indexgenerator … … en de structuur van bladzijden aan te passen om een hoge ranking te verwerven Maar de algoritmen zijn dikwijls “geheim “geheim””
Bug business voor consultanten in het ontwerpen van web site Talrijke boeken werden hierover gepubliceerd 736 referenties op Google Books over SEO 462 referenties op Amazon.com over SEO
30
De Google Story (15) Andere p projecten j projects/products/systems: p j p y Searches ((opzoekingen opzoekingen)) op The web (classic Google) Images Video News Maps p Blogs Books Finance Labs Patents Photos Products Scholar 31
Lijst zoekrobotten (1) Algemene Zoekrobotten (soms gebruik makend van andere) www.altavista.com www. . m www.askjeeves.com www.excite.com www.go.com g www.go2.com www.google.com www.hotbot.com www.lycos.com www.northernlight.com www.opentext.com p www.rocketnews.com www.teoma.com www.webcrawler.com www.vivisimo.com 32
Lijst zoekrobotten (2) Gespecialiseerde Zoekrobotten www lexibot com www.lexibot.com deep Web www.quigo.com deep Web www.about.com directory www.looksmart.com www looksmart com directory www.netcenter.com directory www.suite101.com directory www.a9.com 9 metasearch h www.dogpile.com metasearch www.go2net.com metasearch www.mamma.com metasearch www.profusion.com metasearch www.search.com metasearch www.webinfosearch.com metasearch 33
Lijst zoekrobotten (3) Web Crawlers 1 JumpStation p RBSE Spider WebCrawler The NorthStar Robot W4 (the World W rld Wide Web Wanderer) W nderer) Fish search The Python Robot html analyzer html_analyzer MOMspider HTMLgobble WWWW - the WORLD WIDE WEB WORM W3M2 Websnarf The Webfoot Robot Lycos 34
Lijst zoekrobotten (4) Web Crawlers 2 ASpider p (Associative ( Spider) p ) SGSG -Scout EIT Link Verifier Robot NHSE Web Forager g WebLinker EmacsEmacs -w3 Search Engine Arachnophilia Mac WWWWorm churl tarspider The Peregrinator Checkbot webwalk Harvest Katipo 35
Lijst zoekrobotten (5) Web Crawlers 3 InfoSeek f Robot 1.0 . Open Text Corporation Robot The TkWWW Robot Tcl W3 Robot CSCS -HKUST WWW Index Server Spry Wizard Robot weblayers WebCopy Scooter Aretha WebWatch ArchitextSpider HI (HTML Index) Search Hämähäkki h kk explorer 36
Lijst zoekrobotten (6) Web Crawlers 4 Senrigan g FunnelWeb The Jubii Indexing Robot Jobot DeWeb(c) Katalog/Index Web Core / Roots Robot Francoroute Duppies IncyWincy IBM_Planetwide Nomad UCSD Crawl webfetcher libertechl libertech h-rover HTDig 37
Lijst zoekrobotten (7) Web Crawlers 5 BlackWidow Pioneer NetCarta WebMap Engine Wild Ferret Web Hopper #1, #2, #3 BackRub B ckRub Templeton Wombat Inktomi HKU WWW Octopus Vision Search Resume Robot w3mir SafetyNet Robot GetBot CACTVS Chemistry Spider 38
Lijst zoekrobotten (8)
. . . . . . . .
Web Crawlers 6 TravelTravel -F Finder Spider p pka ILSE Personal Times IsraeliIsraeli -search Infoseek Sidewinder WebMirror
39
