Et standard web-søgesystem kan beskrives som bestående af 2 hoveddele/-aktiviteter:

1. Input, dvs. indsamling af data (web-sider) fra WWW og indeksering af disse ind i selve databasen over indekserede ord og URL-adresser.
2. Output fra samme database, dvs. besvarelse af bruger-forespørgsler (request), samt en relevansvurdering (ranking/prioritering) af de fremfundne resultater. Dette indebærer også en præsentation af resultatet for brugeren.

Dette kan videre under-inddeles i flere kategorier og delfunktioner. I denne rapport er valgt en opdeling, der er brugt af professor T. Koch, Lunds Universitet i forbindelse med en undersøgelse fra 1996 omkring den daværende status omkring søgemaskiner[5].

Ved denne undersøgelse er valgt følgende delelementer:

• Size
• Coverage
• Actualisation
• Haresting
• Indexing
• Result display
• Retrieval
• User interface

Da dette vurderes som værende en hensigtsmæssig opdeling, vil denne opdeling også blive fulgt i denne rapport til den teoretiske beskrivelse.

3.1: Eksempel på søgemaskine
Da alle de store søgemaskiner i dag er kommercielt drevne forretninger, er selve opbygningen af disse maskiner ikke offentlig tilgængelig. Som illustrativt udgangspunkt for beskrivelsen af søgemaskiner er derfor valgt en søgemaskine, der er opbygget på Hong Kong Universitet og som er offentlig beskrevet mht. opbygning og funktionalitet[18][21]. Systemet beskrives her som et udgangspunkt for den efterfølgende nærmere analyse af de forskellige aspekter ved søgemaskiner generelt, da systemet i funktionalitet minder om de kendte store søgemaskiner.

Opbygningen af systemet er skitseret i fig. 3:

Figur 3 - Skematisk opbygning af søgemaskine

På figuren er illustreret de forskellige WWW-sites, der enten kan tilgås direkte af de enkelte brugere, eller som kan tilgås af brugerne gennem et bruger-interface (user-interface) til søgemaskinen. Søgemaskinen er opbygget af en indexer robot, der kommunikerer med de forskellige WWW-sites ved hjælp af http-protokollen ganske som en almindelig browser. Robotten arbejder autonomt, og når den indlæser en side, udtrækker den nøgleord og hyperlink data, som den indsætter ind i en index-database. Derefter fortsætter den til de URL-adresser, som den har udtrukket af den netop besøgte side.
Index-databasen er i systemet opbygget som en almindelig relationel database med følgende tabeller:

Page-ID tabel:

herved mappes URL-adresserne over i et unikt Page-ID hvilket er nemmere at arbejde med, ligesom det muliggøre at skifte adresse uden at skulle ændre alle forekomster i databasen. Dette er ret ofte forekommende, f.eks. hvis der skiftes udbyder.

Keyword-ID tabel:

herved mappes de keyword/ord, som der indekseres efter, over i et unikt Keyword-ID, hvilket er nemmere at arbejde med i de forskellige tabeller. De keywords, der indekseres i dette system, er alle ord i dokumenterne, der er omsluttet af HTML-tags såsom fed tekst, italic tekst, ord i første sætning i hvert liste-element mv., dvs. ord, der kan betragtes som værende fremhævet på en eller anden måde i forhold til den øvrige tekst. Undtaget er endvidere high-frequency ord, dvs. ord, der forekommer så ofte i sproget, at det er meningsløst at indeksere dem (typiske eksempler på dansk er: "og", i" osv.), samt tal, filnavne, email-adresser og HTML-tags. Grunden til denne udvælges angives til at være et ønske om at reducere den nødvendige lager-plads.

Page-Title tabel:

dokumentets titel, som angivet med TML-tag'et , mappes herved særskilt over Page-ID, hvorved der muliggøres en direkte søgning efter kendte titler.

Page-Modification-date tabel:

de enkelte URL-adresser mappes op mod sidste indekseringsdato, hvilket dels bruges i forhold til vedligeholdelsen af databasen (hvornår skal adressen besøges igen) og dels til en oplysning til brugeren om, hvor gammel oplysningen er.

Hyperlink tabel:

herved mappes hver Page-ID mod en liste bestående af links, der peger hen på/refererer til den pgl. side (incoming links), samt af links der findes på den pgl. side (outgoing links). Dette bruges i forhold til relevans-beregninger i forhold til brugerens request.

Inverted index:

herved mappes hvert enkelt keyword-ID mod lister bestående af Page-ID og det pgl. ords position i det pgl. dokument, dvs. for hvert enkelt ord er der en henvisning til en liste bestående af records indeholdende dels page-ID på dokumenter, hvori ordet optræder, og dels hvilket position det har (anført som numerisk værdi talt med første ord som position 1). Dette bruges dels til søgninger efter eksakte sætninger; dels til søgninger, hvor der angives nærhedsoperatorer og endelig til beregning af relevans i forbindelse med prioritering af søgeresultaterne.

Forward index:

hermed mappes hvert Page-ID mod en liste indeholdende alle de keywords, der er indeholdt i det pgl. dokument. Dette bruges dels til beregne af frekvensen, hvormed et ord optræder i det pgl. dokument, samt til beregning af relevans.

For at optimere tilgangshastigheden til de 2 sidste tabeller opbygges der HASH-tabeller på disse, dog uden af selve HASH-funktionen er nærmere beskrevet.

Databasen vedligeholdes ved, at index-robotten hver anden uge validerer alle URL-adresser i databasen. Dette sker ved, at robotten sender en http-request header med metoden HEAD til de pgl. servere. Herved vil serverne kun returnere header-data, der bl.a. indeholder den sidste modificeringsdato for det pgl. dokument (hentes fra det pgl. filsystem) men ikke selve dokumentet. Denne dato vil robotten sammenligne med et opslag i tabellen Page-Modification-date tabel. Hvis de 2 datoer er forskellige, sættes den pgl. URL i kø med henblik på at blive re-indekseret.
Derudover er der i systemet mulighed for eksplicit at lægge en URL-adresse i køen af dokumenter, der skal indekseres.

Bruger-forespørgsler sendes til systemet som HTML-forms. The search-engine i systemet modtager bruger-forespørgslen (user-request) og oversætter denne til en query (SQL-statment), der forstås af databasen. Databasen eksekverer den pgl. query på de indsamlede data og returnerer derefter en liste over URL's, der matcher det pgl. request. The search-engine modtager denne liste og foretager en ranking af de udfundne URL's på baggrund af forskellige algoritmer, der sigter på at udfinde og prioriterer de mest relevante dokumenter. På baggrund heraf genereres en HTML-side, der indeholder de prioriterede URL-adresser, der sendes tilbage til brugeren som en HTML-side. Brugeren kan så direkte fra den modtagne side benytte de angivne adresser som hyperlinks.

Yderligere oplyses, at WWW robotten var skrevet i C og at selve databasen var implementeret i GDBM - GNU Database Manager.

Der findes ikke megen information omkring, hvorledes de kendte søgemaskiner er implementeret rent hardwaremæssigt, hvilket også er forhold, der af konkurrencemæssige hensyn holdes tæt til kroppen. Søgemaskinen HotBot oplyser da i en artikel i bladet Internet World fra d. 29/6-98[22] følgende omkring deres system-opsætning: Selve HotBot's site opereres på 15 Windows NT 4.0 servere og 5 Sun Ultra 2300 servere. Disse servere er direkte forbundet op mod søgemaskinen Inktomi's database, der også fungerer som database for HotBot, dvs. hvis man forespørger via HotBot, vil HotBot videresende søgningen til Inktomi's database, der vil foretage opslag og ranking i forhold til sin database, hvorefter søgeresulatet vil blive sendt tilbage til HotBot. HotBot præsenterer derefter resultatet for brugeren. Inktomis database, der angives til at indeholde 110 mill. individuelle dokumenter køres på to 166 Sun Ultra 2 servere. Inktomi's indexing-robot køres på en cluster af tyve intel-baserede maskiner.

I den anden ende af skala'en oplyser det danske internet firma CyberCity, at de opererer deres danske søgemaskine CyberCity Agent på en Dell pentium 133 MHz maskine med 64 Mb ram, hvorpå der køres Microsoft Internet Information Server 2.0 og MS SQL-server 6,5 på Windows NT 4[12].

3.2: Input
Under punktet Input beskrives således de aspekter, der omhandler selve indsamlingen af den data, der bliver indekseret i søgemaskinens database. Dette er opdelt i følgende underpunkter: Size, Coverage, Actualisation, Harvesting og Indexing, der vil blive beskrevet hver for sig.

3.2.1: Size og Coverage
Størrelsen af en søgemaskine målt som antallet af side (WWW-dokumenter), der er indekseret, opfattes intuitivt som værende en vigtig størrelse. Det umiddelbare argument er, jo flere web-sites og web-sider, som søge-maskinen kender, jo bedre er den og jo større er chancen for at få et godt søge-resultat, forstået som et relevant søge-resultat, der dækker det aktuelle informationsbehov.

Søgemaskiner og andre information retrivieval-systemer er traditionelt blevet målt på 3 parametre: præcision, recall og respons tid, der alle er størrelser, der har direkte sammenhæng med begrebet størrelse[1][2][14].

Den samlede mængde af web-sider på WWW kan rubriceres, jfr. nedenstående skema, som værende relevante eller ikke-relevante og som værende fundne eller ikke-fundne ved en given søgning:

Recall kan defineres som et mål for, hvor godt systemet er til at fremfinde relevante dokumenter, dvs.

Ligning 2:

Hvis en given database antages at indeholde i alt 50 dokumenter, der kan karakteriseres som værende relevante i forhold til en forespørgsel, og samme forespørgsel fremfinde alle 50 dokumenter, så har den en recall på 1. Hvis der kun fremfindes 10 af de 50 relevante dokumenter, så er recall på 10/50=0,2, hvilket omvendt betyder 0,8 (80%) af de relevante dokumenter ikke blev fundet, og som derfor stadigvæk er ukendte for brugeren.

Præcision kan tilsvarende defineres som mål for, hvor præcist systemet er til kun at fremfinde relevante dokumenter, dvs. til at undgå støj (irrelevant information), dvs.

Ligning 3:

Det betyder, at man i foregående situation, hvor recall var på 1 (dvs. alle relevante dokumenter blev fundet) kan antage, at der i alt blev fundet 200 dokumenter, hvoraf altså de 50 var relevante. Her vil recall altså være 1 (100%), hvorimod præcisionen kun vil være 50/200=0,25. De restende 0,75 (75%) vil være støj, der kan defineres som et mål for, hvor stor en del af de fundne dokumenter, der var ikke-relevante, dvs.

Ligning 4:

Støj vil kunne betyde, at de relevante sider praktisk talt "drukner", da det i praksis ikke er muligt selv at gennemse og vurdere mere end ganske få dokumenter. Et søgeresultat på bare 100 hits (dvs. 100 potentielle web-sider) vil det som oftest ikke være mulig at gennemgå. For at imødekomme dette forsøger søgemaskinerne som oftest at prioritere de fundne sider således, at de mest relevante præsenteres først. Disse algoritmer behandles senere under afsnit 3.3.2.


Fallout kan defineres som et mål for, hvor stor chancen er for, at systemet medtager ikke-relevante dokumenter, dvs.

Ligning 5:

Endelig kan generalitet defineres som et mål for, hvor dækkende selve databasens indhold er i forhold til den aktuelle forespørgsel, dvs.

Ligning 6:


Ideal situationen i forhold til en forespørgsel er situationen, hvor :

Ligning 7:

dvs. en situation, hvor systemet fremfinder alle de relevante dokumenter og ingen ikke-relevante dokumenter. Denne situation vil logisk indebærer, at der ikke er nogen støj i forespørgslen, dvs. støj = 0.

I virkelighedens verden forekommer dette dog yderst sjældent i relation til forespørgsler til søgemaskinerne. Sammenhængen med størrelsen af søgemaskinernes databaser er, at jo større databasen er i forhold til antal indekserede sider, jo mindre vil databasens generalitet også være, dvs. antallet af relevante dokumenter i forhold til den samlede størrelse vil blive mindre. Undtaget er dog specialiserede søgemaskiner, der kun indekserer fastlagte underdele af WWW. En mulighed for at forbedre/øge databasens generalitet er at specialisere databasen til kun at omfatte sider, der f.eks. omhandler et bestemt emne, et bestemt sprog, et bestemt domæne ell.lign., dvs. at begrænse databasens "Coverage".

Der findes i dag en lang række søgemaskiner/web-sites, der på forskellige måder har specialiseret sig. Ved søgninger inden for disse søgemaskiners speciale, vil man opnå en større grad af generalitet, set i forhold databasens indhold. Som eksempel på sådanne specialiserede søgemaskiner kan nævnes den danske søgemaskine på adressen http://agent.cybercity.dk/, der kun indekserer sider under domænet .dk, eller søgemaskinen på adressen http://www.wwwomen.com/, der kun omhandler kvinderelaterede sider; de forskellige job-databaser, film-databaser mv. I appendiks E er der listet forskellige kendte søgemaskiner med en kort angivelse af deres subjekt område. Det skal bemærkes, at listen på ingen måde er udtømmende i forhold til mængden af eksisterende søgemaskiner, der tæller langt over 1000.

Afgørende for størrelsen af recall og præcision er dog typisk ikke størrelsen af databasen, men mere hvilke algoritmer som søge-maskinen bruge for at fremfinde aktuelle sider. I relation til WWW er der især 2 forhold omkring disse betragtninger, der kræver nærmere overvejelse. For det første skelnes der mellem relevante og ikke-relevante dokumenter, hvilket umiddelbart forudsætter at begrebet relevans er en diskret størrelse, der kan beregnes og fastsættes i forhold til en given forespørgsel. En sådan betragtning er helt klart en simplificering af de faktiske forhold, hvor det typisk opleves, at et dokument kan være mere relevant end et andet, uden at man kan karakterisere nogen af dem som ikke-relevante. Man kunne derfor prøve med forskellige inddelinger, så som ikke-relevant, lidt-relevant, relevant, meget-relevant mv. Problemet er dog, at det ikke umiddelbart er muligt at foretage egentlige beregninger på disse forhold, da et og samme dokument af 2 forskellige personer kan opleves som både f.eks. relevant og meget-relevant i forhold en enslydende forespørgsel fra de 2 personer. Antag f.eks. en almindelig natur-interesseret og en biolog begge søger materiale om en bestemt fugl. De laver derfor begge samme forespørgsel, der er bygget op omkring artsbetegnelse på fuglen. De fremfundne sider antages herefter at kunne deles op i nogle mere populær-videnskabelige og egentlig videnskabe artikler. Heraf vil de mere populær-videnskabelige formentlig være meget-relevante for den almindeligt natur-interesseret, medens de nok vil være mindre-relevante eller kun relevante for biologen. Og omvendt i forhold til de mere videnskabelige artikler. Dette illustrerer, at oplevelsen af relevans forudsætter en viden om den person, der foretager søgningen. Tilbage bliver derfor en mere si mpel skelnen mellem relevant og ikke-relevant, der tager sit udgangspunkt i selve forespørgslen og ikke i brugerens situation. Med udgangspunkt i selve forespørgslen er det muligt at foretage beregninger på, hvorvidt et dokument er relevant eller ikke-relevant, hvilket behandles nærmere i afsnit. 3.3.2.

Det andet forhold der skal nærmere behandles i forhold til ovenfor anførte betragtninger, er antal dokumenter. Man kan her skelne mellem det totale antal dokumenter på WWW eller det totale antal dokumenter i den pgl. database.

Den faktiske størrelse af WWW og af de forskellige søgemaskiners databaser er et meget omdiskuteret emne. De forskellige søgemaskiner offentliggører med jævne mellemrum statistikker over dels, hvor mange sider de selv har indekseret og dels hvor mange sider de øvrige søgemaskiner (konkurrenterne) har indekseret. Da der er stor kommerciel opmærksomhed omkring disse tal, skal de tages med et stort forbehold, men da det omvendt er meget kompliceret at måle størrelse på databaserne uden at have privilegeret adgang til databaserne, så er det svært at fremskaffe andre og bedre tal. Endvidere er der forskel på, hvordan de forskellige søgemaskiner regner deres størrelse. Nogle medregner kun sider, som de rent faktisk har indekseret; nogle medregner alle kendte adresser, dvs. også links, der er udtrukket fra siden, men som rent faktisk ikke er indekseret; nogle tager højde for at samme side kan være indekseret flere gange og at samme side evt. kan optræde under flere forskellige adresser; nogle medregner "gamle" links, der ikke er valideret gennem længere tid. Web-siten SearchEngineWatch[6] samler og udgiver materiale omkring søgemaskiner og har også samlet de forskellige søgemaskiners størrelse, som den er opgivet af søgemaskinerne selv. Størrelsen af de 7 største og mest kendte søgemaskiner fremgår af figur 4[6]:

Figur 4 - Antal web-sider indekseret, jfr. The Search Engine Watch

Tilsvarende har Digital Research Lab i marts 1998 lavet et estimat over dels størrelsen af WWW og dels over de 4 største søgemaskiner[20], hvilket fremgår af fig. 5:

Figur 5 - Størrelse og udvikling af de store søgemaskiner:

Disse tal ændrer sig dog hele tiden og især den samlede størrelse af WWW udvikler sig konstant. Endelig skal man være opmærksom på, at der kun er opgivet størrelse for så vidt angår de statiske sider, hvorved der ikke er medregnet alle de sider, der on-the-fly genereres i forbindelse med database-opslag, af diverse scrips osv.

Endelig har størrelsen af databasen indflydelse på hastigheden i forbindelse med database-opslag, dvs. også på respons-tid. Tilgangstiden til databaserne er en kompleks størrelse, der er afhængig af størrelser som fil-størrelse, antal records, block-størrelse, fysisk organisering af filerne (ligger de i sammenhængende blokke mv), opbygningen af indices, tabeller mv. Derudover er respons-tiden meget afhængig af, hvorledes de forskellige forespørgsler er implementeret og optimeret.

Selv om der er tale om meget store databaser, ligger de faktiske respons-tider på et forholdsvist lavt niveau. The MICA Report[23] udarbejder løbende statistik, hvor der bl.a. måles på de store søgemaskiners respons-tider. I sidst udgivne analyse - pr. d. 14/6-98 - er der analyseret på søgemaskinerne AltaVista og HotBot, der jfr. ovenstående skulle have indekseret henholdsvis 110 og 100 mill. sider. Selv med disse størrelser er der målt gennemsnitlige respons-tider på henholdsvis 40.7 sek. og 16,3 sek, idet denne tid er målt fra, at forespørgslen er afsendt fra klient-maskinen og til de 3 første sider med svar er modtaget retur. Ved søgningen er der søgt specifikt inden for bestemte web-sites, der alle består af over 1000 enkelte web-sider. Den målte tid inkluderer således også transmissionstiderne frem og tilbage, ligesom det inkluderer evt. beregning af relevans, ranking, generering af output mv. Min egen erfaring (og formentlig også andres) er , at jeg på de store søgemaskiner som oftest har et svar retur i løbet af 5-10 sek. (med en alm. dial-up forbindelse over 28.8 modem) stort set uafhængigt af, hvilken søgning der er tale om. Disse indlæsningstider er således ikke væsentlig større end indlæsningstiderne af andre "almindelige" web-sider, hvorfor man nok kan konkludere, at tidsforbruget i forbindelse med selve databaseopslagene og beregningen af relevans mv. er underordnet i sammenligning med den generelle transmissionshastighed på internettet i almindelighed.

3.2.2 Actualisation
WWW er en dynamisk og konstant foranderlig størrelse, hvorfor indholdet af søgemaskinernes databaser konstant skal vedligeholdes for at være aktuelt. Ifølge Jacob Nielsens artikel Fighting Linkrot[24] er 6% af alle hyperlinks på WWW konstant ikke aktuelle, dvs. opslag til dem vil give en fejlmeddelelse. Ifølge flere undersøgelser opleves dette af brugerne som et af de største problemer og irritationsmomenter med WWW[25][26].

Denne vedligeholdelse af søgemaskinerne foregår på 2 hovedpunkter:

1. Indeksering af nye sider
2. Re-indeksering af allerede kendte/indekserede sider, der ændrer indhold (herunder sletning af ikke-længere eksisterende sider).

Indeksering af nye sider foregår på 2 hovedmåder:

1. Søge-maskinen's indekseringsrobot henter en side og udtrækker alle på siden værende hyperlinks, der så efterfølgende indlæses og indekseres osv. Det betyder, at for så vidt der findes et hyperlink pegende hen til en side (dvs. et incoming link) og denne side indeholdende henvisningen bliver indekseret, så er der en rimelig chance for at den pgl. side også vil blive indekseret.
2. Udgiverne af de enkelte web-sider/-sites anmelder (submitter) selv eksplicit deres sider til de forskellige søgemaskiner, der så efterfølgende indlæser siderne og indekserer dem. Ved anmeldelse af en side vil udgiveren typisk skulle angive URL-adresse på siden, evt. skrive en kort beskrivelse af sidens indhold og evt. kategorisere den i forhold til et indeks-system (af samme art som f.eks. det kendte biblioteks system). Adressen på siden vil så eksplicit blive lagt ind i den liste over URL-adresser, som indekseringsrobotten skal besøge. Derefter vil siden blive besøgt og indekseret på samme vis som de øvrige sider.

Re-indeksering af allerede kendte/indekserede sider foregår ved, at søgemaskinerne med regelmæssige tidsintervaller checker om de kendte sider dels stadigvæk eksisterer og dels om de er blevet ændret, siden de sidst blev indekseret.
Dette kan algoritmisk beskrives med følgende:

1. Gennemgå databasen og udtræk en liste med URL-adresser, der sidst en indlæst siden en given dato, jfr. f.eks. eksempel søge-maskinens Page-Modification-date tabel.
2. Forespørg de pgl. URL-adresser med en http-header indeholdende metoden HEAD.
3. Udtræk feltet: modification time fra svar serverens response-header.
4. Sammenlign de 2 dato'er:
   • hvis der returneres en fejl-kode 404 eller andre, der indikerer, at dokumentet ikke længere eksisterer, så slet det fra databasen.
   • hvis de 2 dato'er er ens, så er dokumentet ikke ændret og der er ikke behov for re-indeksering. Så skal dato'en blot ajourføres.
   • hvis der returneres en nyere dato, så genindlæs hele dokumentet og re-indekser det.
5. Fortsæt til pkt. 1 med næste URL-adresse.

Et alternativ er en brute force strategi, hvorefter alle dokumentet genindlæses og re-indekseres uanset hvad. Dette vil dog under hensyntagen til størrelsen dels af WWW og dels af de enkelte søgemaskiner betyde et betydeligt overhead og en betydelig belastning af nettet som helhed.

Den anførte algoritme kan herefter udvides på forskellige måder, idet der f.eks. kan sættes forskellige tidsgrænser på forskellige dele af nettet, således at web-sider med en høj frekvens af tilgang re-indekseres oftere end steder med en lav frekvens. Tilsvarende kan man slette sider, der ikke bliver tilgået via søge-maskinen gennem en angiven periode. Endelig er der muligheden for, at web-sites udgiverne kan betale sig fra at få deres sider re-indekseret med oftere intervaller.

The Search Engine Watch angiver følgende oversigt ang. de store søgemaskiners aktualitet:

3.2.3: Harvesting
Som beskrevet i foregående afsnit er der 2 principielt forskellige metoder, hvorved søgemaskinerne kan komme i kontakt med web-sider, nemlig ved udgivernes anmeldelse af deres web-sider, samt via automatisk udtræk af URL-adresser indlejret som hyperlinks. I begge tilfælde vil selve indlæsningen af siderne dog ske ved hjælp af en såkaldt web-robot.

I appendiks C: Eksempel på web-robot er vist source-kode til en web-robot, der kan søge efter URL-adresser indeholdende et nærmere angivet ord. Web-robotten skrevet i sproget Perl.

En web-robot kan defineres som et program, der automatisk gennemløber WWW ved at indlæse en side og derefter rekursivt at fortsætte med at indlæse de sider, der er refereret til via de i teksten værende hyperlinks.
Web-robotter bliver ofte endvidere angivet som: Bots, Spiders, (Web) Crawlers, Worms og lignende, der alle er betegnelse for samme ting. Man støder endvidere på betegnelsen "agent", der dog som oftest bruges som betegnelse for et program, der opfylder en af følgende betingelse:

1. Autonome agenter, der er programmer, der autonomt kan fortsætte deres kørsel på en anden maskine, hvilket kun kan ske mellem specielle servere.
2. Intelligente agenter, der er programmer, der kan hjælpe brugeren med forskellige ting. Disse behøves ikke at køre i netværk.
3. Bruger-agenter (User-agent), der er en teknisk betegnelse for programmer, der udøver netværks-opgaver for en bruger, f.eks. en browser.

I sin virkemåde er web-robotten opbygget fuldstændig som en "almindelig" browser, dog med den store forskel, at web-robotten ikke giver sig af med at præsentere de indhentede sider grafisk (eller på anden måde) for en bruger, der sidder ved skærmen. Endvidere vil web-robotten normalt kun indlæse de data, der er relevant for den, dvs. at den kun indlæser selve web-siden men ikke de i siden indlejrede hyperlinks til grafik, lyd-/video-filer, java-appletter mv. Dette kan ganske simpelt gøres ved i web-robottens http klient-header til serveren at angive, at den kun accepterer "text/html". Herved opnås en væsentlig hastighedsfordel i forbindelse med selve transmissionen af data fra server til klient, ligesom det i væsentlig opfang vil aflaste serverne.

For at gøre det muligt for administratorerne af de forskellige web-sites i et vist omfang at styre, hvorledes de bliver besøgt af web-robotter, er der udarbejdet en standard for udelukkelse af web-robotter[27]. Standarden er bygget omkring en struktureret tekst-fil, som web-site administratoren kan lægge i root-biblioteket på serveren. Filen skal have navnet robots.txt og i den kan man angive i hvilket omfang og hvilke robotter, der skal have adgang til den pgl. web-site. Et eksempel på en sådan fil er følgende:

1. #/robots.txt file for (navn på web-siten)
2. User-agent: Scooter/1.0
3. Disallow:
4. User-agent: Slurp/2.0
5. Disallow: /logs
6. User-agent: *
7. Disallow: /

Filen skal forstås på følgende måde:
Linie 1 er en ren kommentar linie. I linie 2 og 3 er angivet, at der ikke er noget, der er udelukket (disallow) for web-robotten ved navn Scooter/1.0 (hvilket er navnet på en af søge-maskinen AltaVista's web-robotter). Det er det samme som, at den pgl. web-robot kan indlæse alle de på web-siten værende sider. I linie 4 og 5 er tilsvarende angivet, at intet udover alle relative URL-adresser startende med "/logs" er udelukket for web-robotten ved navn Slurp/2.0 (navnet på Inktomi's web-robot). I linie 6 og 7 er angivet, at alle relative URL-adresser startende med "/" (dvs. alle adresser på pgl. server) er udelukket for alle andre web-robotter, dvs. alle andre end Scooter/1.0 og Slurp/2.0.

Standarden bygger endvidere på, at programmøren af web-robotten af sig selv respekterer standarden og sørger for at undersøge, om der er en robots.txt fil og i givet fald at respekterer, hvis ens robot er udelukket eller begrænset i sin adgang. Såfremt programmøren ikke ønsker at respektere dette kan man ikke umiddelbart forhindre web-robotten i at få samme adgang til web-siten som en almindelig bruger har.

Ud over denne standard findes et META TAG med navnet "ROBOTS", hvor man kan angive følgende content:

• NOINDEX - betydende, at siden ikke skal indekseres.
• NOFOLLOW - betydende, at robotten ikke skal følge de hyperlinks, der måtte være på siden.

Også disse META TAGS er afhængig af, at programmøren af web-robotten vil respekterer dem.

Visse web-sider er web-robotterne dog umiddelbart udelukket fra at tilgå - nemlig password-beskyttede sider og dynamisk genererede sider.

Password-beskyttede sider kræver, at klienten, der ønsker at tilgå siden, i sin header angiver brugernavn og password i formatet: Authorization: username:password. Alle de store søgemaskiners web-robotter er dog i stand til at håndtere dette, såfremt de udstyres med et username og password til pgl. web-site. Da det som oftest er i de enkelte web-sites interesse, at indholdet af deres web-site blive indekseret, er søgemaskinernes web-robotter som oftest udstyret med adgang til disse web-sites.
Dynamisk genererede sider kan web-robotterne derimod ikke tilgå, at de forudsætter indtastning af data, hvilket ikke er relevant for robotterne.

Tilsvarende frembyder web-sider, der er opbygget med frames, ofte problemer for søgemaskinernes web-robotter, der ikke alle har evnen til at følge og indlæse de forskellige frames.

Når web-robotten tilgår en URL-adresse fra dens liste over URL-adresser, der skal besøges og indekseres, kan den følge forskellige strategier for, hvordan den skal følge de forskellige hyperlink, der udtrækkes fra den pgl. side. Strategierne kan benævnes som:

• Depth-first
• Breadth-first
• Limited depth-first / breadth-first

Ved en depth-first strategi vil web-robotten følge hyperlinks startende fra en "start-side" eller et angivet "entry-point" til en større web-site. Herefter vil web-robotten følge hyperlinks rekursivt gående fra start-siden og mod mere specialiserede sider i forhold til foregående side. Dette sker typisk ved, at web-robotten først tilgår alle individuelle sider i samme bibliotek og derefter samtlige web-sider i samtlige under-biblioteker i forhold til "start-siden" osv.

Ved en breadth-first strategi vil web-robotten ligeledes følge hyperlinks startende fra den angivne start-side, men vil her forsøge at dække så mange forskellige områder som muligt. Dette søges opnået ved at tilgå alle sider i samme bibliotek på serveren først og derefter i stedet for at fortsætte i under-biblioteker hertil, så fortsætte i evt. side-ordnede eller højere liggende biblioteker på samme server eller andre servere.

Ved en limited depth-first eller breadth-first strategi er strategien den samme, men med den forskel, at det ekspicit er fastlagt, hvor dybt web-robotten skal brede eller fordybe sig i en web-site.

En breadth-first strategi vil resultere i en bred dækning af mange forskellige emner og vil hurtigt inkludere mange forskellige "top-sider/entry-points" til forskellige web-sites. Omvendt vil en depth-first strategi resultere i en meget detaljeret og uddybende dækning af de enkelte emner, men vil til gengæld brede sig langsomt ud over de enkelte emner. Ved at sætte forskellige begrænsninger som f.eks. at angive, at der kun kan indekseres 200 individuelle sider tilhørende samme web-site, er det muligt at regulere på balancen mellem hurtig dækning af mange forskellige web-sites/mange forskelle emner, samt mellem en stor grad af detajlviden og specialisering.

3.2.4: Indexing
Et centralt element i selve søge-maskinen er de data, der bliver indekseret, samt de tabeller og indices, der bliver opbygget af disse data. I de store søgemaskiner er disse indices og tabeller af meget betragtelig større, søgemaskinen Excite oplyser således, at selve deres søge-indeks fylder 50Gbyte[28].

Der er 2 forhold, der er af særlig interesse i forbindelse med disse indekser, nemlig

1. Hvilke data bliver rent faktisk indekseret og
2. Hvorledes organiseres disse data.

Vurderingen af hvad der skal indekseres, er en afvejning af flere forskellige og delvist modstridende forhold:

• Jo flere data, jo flere søgemuligheder
• Jo flere data, jo bedre dækning af de indekserede sider
• Jo flere data, jo større indekser og dermed også større krav til lagerplads (både med hensyn til sekundær lagerplads (diskplads) og med hensyn til primært lager (RAM)).
• Jo flere data og dermed større indekser, jo større vil den gennemsnitlige tilgangstid (access-tid) også være

Kort sagt er det en afvejning mellem præcision og omkostninger (i form af tid, lagerplads og CPU-tid).

3.2.4.1: Hvad indekseres
Der kan beskrives flere forskellige indekseringsformer, der kan illustreres med oversigten i fig. 6:

Figur 6 - Indekseringsformer:

Der skelnes primært mellem indeksering af naturlig sprog, dvs. alle de i teksten forekomne ord, og mellem et kontrolleret sprog. Ved et kontrolleret sprog forstås indeksering efter en på forhånd og eksplicit udarbejdet liste - en emneordsliste - over ord, der vurderes som værende interessante og relevante. Disse ord bruges så dels til indekseringen og dels som en liste over mulige søgetermer, dvs. der kan ikke søges på ord, der ikke optræder på emneordslisten. Ved en thesauri forstås dernæst en emneordsliste, der er ordnet i indbyrdes relationer og i semantiske strukturer. I thesauri henvises til over- og undertermer, samt til relaterede begreber.

Ved at indeksere efter emneordslister opnår man en meget høj præcision både i indekseringen og i søgningen for så vidt angår ord, der optræder på emneordslisten, idet man er sikker på, at alle indekserede ord er relevante. Til gengæld er systemet stort set kun brugbart i begrænsede fagområder, hvor sprogbrug og ordvalg er nøje fastlagt og almindeligt accepteret. Som eksempler på sådanne områder kan nævnes forskellige videnskabe områder som f.eks. medicin, fysisk osv. Til gengæld kræver det betydeligt arbejde at vedligeholde og opdatere disse emneordslister med nye begreber og ord, hvorfor systemet ikke er brugbart indenfor områder, hvor der er en kraftig og hurtig udvikling, eller hvor sprogbrug ikke er fastlagt og kontrolleret.

Indeksering efter kontrollerede ordlister bruges stort set ikke i EDB-baserede søge-systemer, hvor der næsten udelukkende indekseres efter naturligt sprog. Ved indeksering efter naturligt sprog er det meget almindeligt, at der udarbejdes ordlister - stopordslister - over ord, der er så ofte forekommende i sproget, at de dels ikke i sig selv er informationsbærende og dels optræder så ofte, at en indeksering af dem vil betyde en voldsom forøgelse af den samlede database. Der er tale om ord (på dansk) som "og", "i", "på" osv., samt f.eks. tal. Stopordslister kan man enten udarbejde eksplicit og på forhånd, eller de kan genereres dynamisk af systemet. I det sidste tilfælde vil algoritmen være, at en givent ord vil blive opført på stopordslisten og dermed ikke længere blive indekseret, når det optræder med en given frekvens i en hvis procent del af de indekserede dokumenter.

Ved indekseringen af naturligt sprog er man nødt til at tage højde for, at de enkelte ord optræder i forskellige bøjningsformer, ental/flertal, nutid/datid mv., men stadigvæk med samme mening, f.eks. et hus - husene, at træne - trænede osv.. Der kan vælges 2 forskellige løsninger, nemlig enten at indeksere alle ordene som de forekommer i teksterne eller man kan forsøge at "af-runde" ("to stem") ordene til en "normal-form". Denne af-runding er som oftest baseret på suffiks-lister (dvs. lister over de forskellige endelser - på danske f.eks. datids-endelsen -ede, flertals-endelsen -er mv) samt på grammatiske regler for, hvorledes disse suffikser tilføjes og fjernes. Der findes flere forskellige algoritmer omkring dette, hvoraf den mest kendte og brugte er kendt som Porters Stemmings Algorithm. Af-rundingen kan foretages i forbindelse med indekseringen, således at det kun er de af-rundede ord, der placeres i databasen. Modsætningsvist kan af-rundingen foretages på de af brugeren indtastede søge-ord, hvorefter de af-rundede søge-ord kan matches mod de i data-basen værende "originale ord".

Et alternativ eller en udvidelse til en sådan af-runding af de indekserede ord består i muligheden for, at brugeren i sin forespørgsel har mulighed for at trunkere, dvs. at erstatte et eller flere tegn i søge-ordene med wildcards (jokertegn), hvorved brugeren selv eksplicit har mulighed for at søge at tage højde for den nævnte problematik.

Ved en vurdering af de 3 forskellige teknikker kan man lægge vægt på, at ved en af-rundning af alle indekserede ord opnås et mindre indeks og hurtigere opslag, idet den på forhånd er taget højde for de forskellige forekomster af det samme ord. Omvendt kan der ikke længere søges på specifikke udgaver af de enkelte ord. Ved en indeksering af de originale ord og en efterfølgende af-runding eller trunkeringsmulig af søge-ordene opnås en mulighed for at søge på specifikke udgaver af de enkelte ord, men der fås samtidig væsentlig større indekser samt flere opslag i databaserne.

I praksis tillader stort set alle de kendte søgemaskiner, at man trunkerer sin forespørgsel medens det er forskelligt om søgemaskinerne selv tager højde for "af-rundingsproblemet". Søgemaskiner som InfoSeek og Lycos tager således højde for det, medens AltaVista, Excite og HotBot ikke gør det[6].

Nært forbundet med den nævnte problematik er, hvorvidt søgemaskinerne er case-sensitive, dvs. hvorvidt de skelner mellem store og små bogstaver. Den almindelige standard i dag er, at de ikke skelner mellem store og små bogstaver (dvs. ikke er case-sensitive), men der er stadigvæk søgemaskiner, hvor det er op til brugeren selv at tage højde for dette.

Endelig skal nævnes, at da alle de store søgemaskiner er amerikanske eller vesteuropæiske, er alle disse forskellige faciliteter inkorporeret i forhold til det engelske/amerikanske sprog, samt i forhold til vest-europæiske bogstaver/karaktersæt, dvs. Latin-Language karaktersættet defineret i ISO-859-1. Så snart der er tale om andre sprog samt om ikke vesteuropæiske bogstaver/tegnsæt (f.eks. russisk sprog og kyrilliske bogstaver, eller arabisk sprog og arabiske bogstaver) er det stort set kun de specialiserede søgemaskiner, der er i stand til at indeksere disse sider.

Hvis der tages udgangspunkt i eksempel søgemaskinen beskrevet i afsnit 3.1.1. , er der i denne database indekseret følgende data for de enkelte web-sider: URL-adresse; Sidens titel (hentet fra HTML-tag ); datoen, hvor siden sidst er indekseret; alle nøgle-ordene på siden og deres placering angivet som position; alle hyperlinks, der findes på siden, hvilket også er de data, der bliver indekseret i stort set alle de kendte søgemaskiner.

Nøgleord (Keywords) er i denne søge-maskine defineret som værende de ord, der i teksten er søgt fremhævet af forfatteren og som derfor kan antages at være centrale i forhold til betydningen/meningsindholdet af hele dokumentet. Herved tænkes på ord, der er markeret som værende skrevet med fed eller med kursiv, de første ord i hvert element i en liste opremsning osv. Udgangspunktet er en forudsætning om, at forfatteren af dokumentet via dokumentets præsentation (lay-out) også har taget stilling til de væsentligste ord i dokumentet. Dette er en meget benyttet teknik i udvælgelse af nøgleord fra hypertekst dokumenter, hvis der ikke alle ord indekseres.

Andre kendte muligheder i hypertekst er indeksering af indholdet af de forskellige META TAGS; indeksering af den alternative tekst, der kan opgives ved indsættelse af hypelinks til grafik/lyd/video-filer; indeksering af kommentarer i hyperteksten; indeksering af selve HTML-tags'ene; osv.

Der kan endelig være forskel på, hvorvidt hele web-siden indekseres eller om der kun indekseres dele af teksten som f.eks. de første 200 ord.

3.2.4.2: Hvorledes opbygges indeksene
Der er i database-litteraturen fremhævet 2 hovedmetoder, hvorefter man kan opbygge og organisere indices af den type, som der findes i søgemaskinerne, nemlig metoderne hashing og B-tree.

Hashing-teknik består af konstruktion af en funktion, der kan bruges til at beregne den pgl. records placering på baggrund af de indeholdte data. B-tree består af opbygningen af et binært træ på baggrund af de enkelte records.

En vurdering af de 2 forskellige metoder viser, at B-tree metoden garanterer en logaritmisk performance for alle operationer på indekset (dvs. indsættelse, sletning, søgning), hvorimod hashing giver en konstant søgehastighed. Hash-indekser er derimod svære at udvide og vil ofte kræve en genopbygning af hele indekset ved en udvidelse, hvorfor hash-indekser altid konstrueres med en vist overhead. B-tree indekser kan til gengæld udvides og indskrænkes dynamisk.

For at sikre en høj tilgangshastighed på de forskellige indekser, skal de ligge permanent i RAM-lageret.

Den konkrete opbygning og organisering af de kendte søgemaskiners indekser betragtes dog som værende forretningshemmeligheder, der holdes tæt ind til kroppen og som derfor ikke er offentliggjorte.

3.3: Output
Under punktet Output beskrives således de aspekter, der omhandler brugens interaktion med søgemaskinen og søgemaskinens generering af svar på brugerforespørgsler. Dette er opdelt i følgende underpunkter: Result display, Retrieval/ranking og User interface, der vil blive beskrevet hver for sig.

3.3.1: Result display
Resultatet af en søgning skulle gerne give brugeren en mulighed for at få tilfredsstillet sit informationsbehov. Det, der repræsenteres som søge-resultatet, er dog ikke selve den information, der findes i de pgl. web-dokumenter, men er som oftest henvisninger - hyperlinks - til de pgl. web-dokumenter.

Der er en vis forskel i hvilke data, der præsenteres for brugeren som værende søge-resultatet::

• URL-adressen på de web-dokumenter, der er fundet ved søgningen, bliver altid præsenteret og som regel som et hyperlink.


• Titlen på web-dokumentet bliver primært præsenteret som den med HTML-tag'ene markerede dokumenttitel. Alternativt hertil, hvis der ikke er markeret en sådan titel i web-dokumentet, vises enten teksten "No title" eller den første linie i web-dokumentet præsenteres som en titel. Der angives ikke hvorvidt der er tale om en markeret titel eller der er tale om den første linie.
• Beskrivelse af dokumenterne vises ofte i forbindelse med de fremfundne dokumenter. De er dog stor forskel på, hvorledes denne beskrivelse genereres. Følgende metoder er kendte:
  • Som beskrivelse bruges som den tekst, der er indsat i META TAG'et "description"
  • Som beskrivelse bruges de første linie i dokumentet, typisk fra dokumentets "krop", dvs. efter -tag'et.
  • Der genereres en beskrivelse på baggrund af dokumentets indhold, dvs. typisk af forskellige nøgleord i teksten. Der bruges her samme type algoritme, som der bruges til at beregne relevans mv (se næste afsnit).
  • Der vises ingen beskrivelse.
• Dato for web-dokumentets oprettelse, dvs. dato-stemplet på den pgl. fil, eller dato for, hvornår siden sidst er indekseret viser i nogle systemer, men ikke i alle. Dato'erne giver et udgangspunkt for en vurdering af om de pgl. informationer stadigvæk er relevante og ajourførte.


• Fil-størrelsen af de enkelte dokumenter og evt. størrelse af indlejret grafik mv. vises i nogle systemer.


• Relevans og prioritering af de fremfundne sider. De enkelte søge-resultater prioriteres som regel, således at siderne med størst (beregnet) relevans vises først (se næste afsnit vedr. selve beregningen), dvs. selve prioriteringen fremgår implicit af, hvor på siden det enkelte dokument er anført. Enkelte systemer angiver også et numerisk mål for relevans-scoren, typisk opgivet som en procent angivelse. Derimod er der ingen systemer, der angiver direkte efter hvilke regler, at prioriteringen er foretaget.


• Antal søgeresultater angives som regel som antal dokumenter, der matcher forespørgslen. Der vises typisk mellem 10 til 50 henvisninger per side og typisk med en mulighed for at gå videre til efterfølgende sider med flere søgeresultater. Det fremgår ikke, hvor mange sider, at systemerne rent faktisk finder frem, men de har alle en begrænsning, de er væsentlig lavere end det antal, der angives som værende det antal dokumenter, der matcher forespørgslen.

3.3.2: Retrieval / ranking
Ved en søgning i de store søgemaskiners databaser returneres der som oftest et betragteligt antal - ofte flere tusinde - henvisninger til dokumenter, der matcher forespørgslen. De fleste brugere vil - afhængig af hvor energiske de er - prøve de første 5-10 henvisninger og vil derefter enten være tilfredse, vil prøve med en anden søgning eller vil opgive. Dette viser, at den prioritering i forhold til forventet relevans, som søgemaskinerne foretager, er meget vigtig af 2 forskellige grunde:

• for brugeren er det vigtigt, at de mest relevante dokumenter, der bedst antages at kunne dække hans informationsbehov, kommer først, da han formentlig aldrig vil gennemse alle henvisningerne;
• for informationsudbyderne er det omvendt vigtigt, at deres web-dokumenter kommer først, da det er de dokumenter, der bliver læst af brugeren. Dette er især for kommercielle web-sites meget vigtigt og har ført til en stor interesse for det spørgsmål.

Ved beregningen af en søgemaskines præcision og recall er det ligeledes vigtigt, at søgemaskinen er i stand til at præsentere de mest relevante dokumenter først.

Der findes en lang række forskellige algoritmer og metoder, der tager sigte på at beregne ligheden mellem to dokumenter eller mellem et dokument og et søge-udtryk. Disse metoder kan også bruges til at udtrykke en grad af relevans i forhold til en forespørgsel, idet det antages, at en stor lighed mellem et søge-udtryk og et dokument også betyder, at dokumentet har en tilsvarende stor relevans i forhold til brugerens informationsbehov. Det er derved muligt at beregne et numerisk udtryk for graden af relevans.

I sammenhæng hermed er spørgsmålet om, hvorledes systemet finder de dokumenter, der matcher søge-udtrykket. Der kan skelnes mellem 2 hovedtyper:

1. Boolske forespørgsler, hvor brugeren angiver specifikke ord, der er indbyrdes forbundet med boolske operatorer, samt evt. med andre tilsvarende operatorer. Systemet vil herefter returnere dokumenter, der opfylder det boolske udtryk, f.eks. søgemaskiner AND opbygning OR teknik, der skal forstås som dokumenter, der indeholder ordet søgemaskiner og som også indeholder enten ordet opbygning eller ordet teknik. Den boolske forespørgsel er således en simpel matching mellem ord i søge-udtrykket og ord forekommende i dokumenterne. Af andre operatorer end boolske kan nævnes nærheds- og positionelle operatorer.
2. Keyword forespørgsler, hvor brugeren angiver en række ord, der er centrale for beskrivelsen af brugerens informationsbehov. Systemet vil herefter på baggrund af de angivne ord søge at finde de dokumenter med den største grad af overensstemmelse. Teknikken til at foretage denne beregning er identisk med beregningen af den indbyrdes prioritering af de fremfundne dokumenter i relation til graden af relevans.

Keyword forespørgsler opleves ofte af brugerne som værende lettere end boolske forespørgsel, da der ikke kræves noget kendskab til boolsk logik eller til opbygningen af søgeudtrykkene i øvrigt. Til gengæld har brugeren ikke så stor kontrol over forespørgslen i en keyword baseret forespørgsel som i en boolsk forespørgsel. I praksis er der dog ikke den store forskel på de to typer, dels forbi de fleste forespørgsler (som tidligere anført) kun består af 1 til 2 ord, og dels fordi de fleste systemer benytter hybride former, der inkorporerer elementer fra begge typer.

Der skal herefter beskrives nogle af de mere kendte og udbredte algoritmer, der alle har som formål at give et numerisk mål for graden af overensstemmelse mellem to tekster, dvs. her enten mellem to web-dokumenter eller mellem et web-dokument og et søge-udtryk bestående af et eller flere ord.

Notationen i det følgende er:
M : antal ord i søgeudtrykket.
Q_j : det j^te ord i søgeudrykket, hvor 1 < j < M.
N : antal individuelle dokumenter i databasen.
P_i : det i^te dokument i databasen, hvor 1 < i < N.
R_i,q : Relevans-scoren for P_i i forhold til søgeudtrykket Q.
Li_i,k : tilstedeværelsen af et hyperlink pegende fra P_k til P_i, dvs. et indkommende hyperlink.
Li_i,k=1, hvis et sådant hyperlink eksisterer og er ellers 0.
Lo_i,k : tilstedeværelsen af et hypelink pegende fra P_i til P_k, dvs. et udgående hyperlink.
Loi,k=1, hvis et sådant hyperlink eksistere og er ellers 0.
C_i,j : tilstedeværelsen af Q_j i P_i, hvor C_i,j=1 hvis P_i indeholder Q_j og ellers 0.

Boolean Retrieval Model[14][18]
Denne algoritme hænger tæt sammen med den boolske forespørgsel's model og den beregner relevans i forhold til tilstedeværelsen af de enkelte ord i søgeudtrykket., dvs.
Ligning 8:

Relevans-scoren beregnes som summen eller antallet af søgeord, der rent faktisk optræder i dokumentet. Da det gennemsnitlige søgeudtryk kun er på ca. 1,5 ord, har denne algoritme ikke stor praktisk relevans.

Algoritmen kan udvides således at den tager højde for den frekvens, hvormed de enkelte ord i søgeudtrykket optræder i dokumenterne, dvs.

Ligning 9:

hvor Cf_i,j er defineret som tilstedeværelsen af Q_j i P_i, men udtrykt som en numerisk angivelse af antal gange at Q_j optræder i P_i. Dette er den mest anvendte prioriteringsalgoritme i de store søgemaskiner. Algoritmen er nem at implementere og at beregne. Implementeringsmæssigt er der ingen problemer, idet man alligevel - jfr. også eksempel databasen - vil indeksere alle forekomster af ordene i dokumentet i sammenhæng med indekseringen af ordenes placering i teksten. Algoritmen er også relevant i forhold til korte søgeudtryk. Omvendt favoriserer algoritmen tekster skrevet med et ensidigt sprog, ligesom den ikke tager højde for vocabular-problemet.

Algoritmen kan endvidere udvides, således at der tages højde for, at de enkelte ord i søgeudtrykket kan have forskellig grad af betydning, dvs. en forskellig vægtning, dvs.

Ligning 10:

hvor w_j betegner et numerisk udtryk for den vægtning, som Q_j tillægges i søgeudtrykket. Vægtningen af de enkelte søge-ord kan enten sker på baggrund af statistiske analyser over fordelingen og brugen af de forskellige ord i et sprog eller brugeren kan direkte i forbindelse med indtastningen af sit søgeudtryk tillægge de enkelte ord en vægtning.

Citationsanalyse (Most-cited)[13][14][19]
En af den boolske retrieval model's svagheder i forhold til hypertekst er, at den betragter hvert enkelte web-side for sig uden at tage højde for den sammenhæng, der ligger i hypertekst strukturen. Den boolske retrieval model er helt afhængig af tilstedeværelsen af søgeordene i alle dokumenter, dvs. dokumenter, hvori søgeordene ikke optræder, vil slet ikke blive prioriteret (eller fundet!). Et dokument P_i, der ikke indeholder nogle af søgeordene, men som indeholder hyperlinks til dokumentet P_k, der indeholder nogle af søgeordene, vil dog intuitivt blive betragtet som relevant.

Most-cited algoritmen søger at tage højde for dette ved at beregne relevans-scoren som summen af antal søge-ord, der er indeholdt i andre dokumenter, der selv refererer til den pgl. side (indkommende hyperlink), dvs.

Ligning 11:

Algortimen vil beregne en større relevans til dokumenter, som der bliver refereret til, end til dokumenter, der selv indeholder reference til andre dokumenter. Dette er en gammel teknik, der har været benyttet gennem mange år i den videnskabelige litteratur, hvor man har udarbejdet citations indekser[13], ud fra den antagelse at der refereret mest til de centrale og mest vigtige værker.

Vector Space Model[2][14][15][16][17][18]
I vector space modellen betragtes et dokument som repræsenteret af en vektor bestående af nøgleord udtrukket fra dokumentet, dvs. hvis V betegner størrelsen af vocabular-samlingen (dvs. samlingen af distinkte ord/nøgleord i databasen), så kan dokumentet D_i beskrives med en V-dimensional vektor _i,1, w_i,2,...,w_i,v>, hvor w_i,j repræsenterer ordet j i dokument i. Relevansen mellem to dokumenter kan herefter udtrykkes som ligheden mellem de to dokumenters vektor-repræsentation. Tilsvarende kan udtrykkes ligheden mellem et søgeudtryk og et dokument. Der findes flere forskellige formler for beregningen af ligheden, hvor beregningen af cosinus coefficienten er en af dem. Formelt kan dette udtrykkes som:

Ligning 12:

hvor cos(D,Q) er cosinus coefficienten mellem vektorerne D og Q; D•Q betegner det skalare produkt mellem vektorerne og ||D|| betegner længden af vektoren D.

Denne model kan udvides, således at der foretages en vægtning mellem de enkelte ord. Intuitivt vil man opfatte tilstedeværelsen af et meget sjældent ord i en tekst, som værende et ord, der har en høj grad af betydning i forhold til at kunne skelne mellem den pgl. tekst og andre tekster. Omvendt er tilstedeværelse af et meget almindeligt ord (f.eks. et fra de tidligere omtalte stopordslister, se afsnit 3.2.4.1) ikke særligt informationsbetydende i forhold til at adskille den pgl. tekst fra andre tekster. De fleste algoritmer til beregning af vægtning af de enkelte ord bygger på statistiske overvejelser omkring den frekvens, hvorved de enkelte ord optræder og bruges i sproget. I algoritmen TFxIDF beregne vægtningen efter følgende formel:

Ligning 13:

for 1=_i,j betegner den vægt som ordet j tillægges i dokumentet i; tfD_i(t_j) betegner den frekvens, hvorved ordet j optræder i dokumentet i, dvs. antallet af forekomster af ordet i dokumentet. Funktionen idf(t_j) - kaldet den inverse dokument frekvens - beregnes til at være log₂(N/df(t_j)), hvor N er antalllet af dokumenter i databasen og df(t_j) er frekvensen af dokumenter, hvori ordet j findes. Vægtningsberegningen medfører, at ord, der optræder hyppigt i samme dokument tildeles stor vægt, hvorimod ord der optræder i mange forskellige dokumenter tildeles lav vægning.

Ligheden mellem to dokumenter (i den forbindelse kan et søgeudtryk betragtes som et lille dokument, der vægtes og repræsenteres som andre dokumenter) kan herefter beregnes efter følgende formel, hvor ligheden er omregnet på normalformen for derved at tage højde for, at et dokument ikke nødvendigvis skal score højere blot fordi det er langt:

Ligning 14:

hvor w_D,j betegner den vægtede værdi af ordet j i dokumentet D (henholdsvis Q).

Beregningen af ligheden kan algoritmisk beskrives med følgende pseudo-kode:

initialiser alle dokument-score til 0
 for alle ord q i søgeudtrykket Q do
 find alle dokumenter d, der indeholder q
for alle dokumenter d do
beregn: score(d)=score(d)+tfd,q·idfq
  end
end
normaliser scorene
sorter dokumenterne efter beregnet score.

Overordnet set er algoritmen nem at implementere, men normaliseringen af scorene er meget beregningstungt. Algoritmen kan derfor reduceres i flere trin, der gør den lettere at implementere, men som samtidig gør den mindre præcis[15].

Vector space modellen vil styrke præcisionen af de fundne dokumenter, men vil ikke umiddelbart øge recall, da den ikke vil finde relevante dokumenter, der ikke indeholder nogen af søgeordene.

Latent Semantic Indexing[2][14]
For at øge recall er der udarbejdet metoder, der tager højde for vocabular problemet, dvs. metoder der kan udfinde relevante dokumenter, selvom de ikke indeholder nogen af søgeordene. Metoderne bygger ligesom Vektor Space Modellen på en geometrisk repræsentation af de enkelte dokumenter. Ved en afbildning af vektorerne for at alle dokumenterne i databasen vil man kunne se, at de vil samle sig i "klumper" - clustere - hvor de enkelte dokumenter i en cluster vil have stor lighed, også selv om de ikke indeholder de samme ord.

I en søgning kan man derefter først beregne ligheden mellem et søgeudtryk og de forskellige clustere. Dette kan gøres med at beregne centrum af clusterene og derefter af betragte disse beregnede centrum'er som enkelte dokumenter, der kan sammenlignes med søgeudtrykket. Herved kan den mest relevante cluster af dokumenter beregenes. Efterfølgende kan ligheden for de enkelte dokumenter i de den mest relevante cluster sammelignes med søgeudtrykket, således at de enkelte dokumenter kan prioriteres.

En sådan metode er latent semantic indexing, der er i stand til at fremfinde relevante dokumenter, også selv om de ikke indeholder ord fra søgeudtrykket, idet metoden beregner og rublicerer dokumenterne i forhold til deres indbyrdes lighed og indhold. Eksperimenter har vist, at denne metoder kan forøge både præcision og recall med op til 30% i forhold til andre vektor-basede beregninger[2]. Prisen er dog, at metoden er meget beregningstung, hvilket gør den mindre egnet til meget store data-mængder.

Andre metoder[4][14]
Der findes en del andre metoder, der alle søger af øge både præcision og recall på forskellig vis. Kort skal nævnes Fuzzification, Relevans Feedback, Automatic Query Expansion, Vector Space Feedback med flere. Alle har de det problem, at jo mere avancerede beregningerne bliver, jo tungere er de at implementere. Derfor bruges de kun i et begrænset omfang i de eksisterende systemer.

En sidste teknik der kort skal omtales, består ganske kort i, at man betaler sig til en høj relevans. Teknikken findes i flere forskellige udformninger, hvoraf keyword advertising er meget udbredt. Ved keyword adversiting kan man købe sig til, at ens reklame-banner figurerer på siderne med søge-resultater vedr. søgning med bestemte nøgleord, dvs. hvis man sælger hundefoder, kan man købe sig til, at ens reklamebanner med reklame for hundefodret kommer på alle sider med søgeresultater vedr. f.eks. søgning på nøgleordene hunde, hundefoder osv. Hele spørgsmålet omkring betaling i forbindelse med prioriteringen af søgeresultater er et meget følsomt emne for administratorerne af søgemaskinerne, idet det i et vist omfang kan kompromitere troværdigheden af søgeresultaterne.

3.3.2.2: Spamming problemet
I nær tilknytning til de ovenfor gennemgåede teknikker med hensyn til prioritering af de fremfundne web-dokumenter er der udviklet en lang række teknikker, der alle tager sigte på at få et givet dokument til at udløse en høj relevans-score i forbindelse med søgning på bestemte ord, selvom dokumentets egentlige indhold ikke ville udløse en sådan relevans-score. Mere direkte sagt, er det teknikker, der tager sigte på at snyde relevans-beregningen, således at det pgl. web-dokument gives en unaturlig høj score. Fænomenet kaldes spamming.

Der skal her beskrives nogle få af de mere udbredte og kendte spamming-teknikker, men i lighed med andre områder, der handler om "snyd", udfoldes der også på dette område stor kreativitet og energi.

• Den nok mest kendte spamming teknik er at gentage forskellige nøgleord unaturligt mange gange, typisk i starten af dokumentet og gerne i META TAGS. I de fleste systemer vil en høj frekvens af et nøgleord udløse en høj relvans-score ved søgning på samme ord.
  Ofte "gemmes" denne oplistning af nøgleord på forskellig måde, så den ikke vises på skærmen. Ved at sætte font-farve ens med baggrundfarve vil ordene "forsvinde"; ligeledes kan ordene gemmes i HTML-kommentarer og i andre TAGS alt efter hvad er pgl. søgemaskine indeksere.
• En måde at få skubbet "konkurrenterne" ud af top-10 er ved at registrere mange næsten ens sider, der alle hver for sig scorer højt i relevans.
• Hvis man vil drage fuldt udbytte af de forskellige søgemaskiners prioriteringsalgoritmer, udarbejder man specifikke udgave af en offentlig web-sider, således at hver enkelt side er "skrædder-syet" til en enkelt søge-maskine. Når en søgemaskine's web-robot vil indlæse den offentlige side, henvises web-robotten til den "skrædder-syede" side, der herefter indekseres som om det var den offentlige. Teknikken kaldes "bridge-pages" eller "entry-pages".

Administratorerne af de fleste søgemaskiner er meget opmærksomme på spamming-problemmet og holder derfor konstant øje med udviklingen på området. I takt med at der udvikles nye spamming-teknikker, prøver administratorerne af søgemaskinerne at udvikle teknikker, der automatisk kan detektere spamming. En almindelig reaktion på konstateret spamming er udelukkelse fra søge-maskinen (spam penalty). De fleste søgemaskiner vil således i dag automatisk detektere, hvis et ord bare gentages unaturligt mange gange.

3.3.3: User interface
Udformingen af bruger-grænseflader er i dag anerkendt som værende af afgørende betydning for brugbarheden af et EDB-system. Dette gør sig selvfølgelig også gældende for søgemaskinernes bruger-grænseflader.

Standarden i dag er, at bruger-grænsefladen er bygget op som et almindeligt HTML-dokument, der præsenteres og håndteres i en almindelig browser som alle andre web-dokumenter.

Overførelsen af søgeudtrykkene til søgemaskinerne sker ved hjælp af tags, der overføres til CGI-scripts. Siderne er som regel bygget op omkring et enkelt input-felt, der er defineret ved hjælp af et -tag. I dette input-felt kan brugeren så indtaste sit søgeudtryk og derefter sende det til søgemaskinen ved at trykke på en form for knap.