Hvordan en Søkemotor Fungerer og Indekserer

Av: Sverre Bech-Sjøthun, February 8, 2007

Dette er definitivt ikke en artikkel for nybegynnere i faget – men vil gi en dyptgående innsikt i hvordan søkemotorene faktisk behandler et elektronisk dokument – fra de blir funnet av en søkerobot til det er indeksert og rangert.

Kort fortalt om hvordan en søkemotor fungerer

En søkemotor har kun ett formål – presentere det mest mulig relevante resultat for et gitt søk.

For å finne ut hva som er det mest relevante dokumentet, det vil si en HTML side på et nettsted, Word eller PDF dokument – en eller annen form for elektronisk dokument på internett, har disse algoritmer som regner ut relevans i henhold til sine interne rangeringskriterier. Google, for eksempel, har i skrivende stund i overkant av 300 slike rangeringskriterier i sin algoritme.

For å finne et dokument sender søkemotorene ut en ”robot” eller en ”spider” som følger lenker fra ett sted til ett annet, enten fra nettsted til nettsted eller internt på et nettsted. Lenker er med andre ord en vital del i en hver søkemotoralgoritme.

Når roboten er ferdig med å følge lenker på ditt nettsted vil den legge siden din til i sin indeks. Når en person så foretar et søk, vil søkemotoren returnere sitt resultat og rangere de forskjellige websidene basert på hvor relevant ditt nettsted oppfattes i forhold til søkemotorens rangeringskriterier – algoritmene.

Slik ser søkerobotene din webside

I dette avsnittet vil jeg beskrive hvordan søkemotorene faktisk ser på de enkelte sidene eller dokumentene på et nettsted, og prosessen fra en robot finner en side til den er indeksert.

Det er i utgangspunktet fem steg i denne prosessen:

  • Linearisering
  • Tokenisering
  • Filtrering
  • Stemming
  • Vekting

Linearisering

Linearisering er prosessen hvor søkemotoren stripper ned dokumentet, fjerner all markup slik at dokumentets innhold blir omgjort til en tekststreng. Denne prosessen blir utført tag for tag fortløpende som tagger blir identifisert i dokumentet.

I eksempelet under har du en webside som består av to tabeller – toppen og selve innholdstabellen med tre kolonner. Tallene indikerer rekkefølgen på hvordan søkeroboten leser dokumentet.

Etter linearisering blir dokumentet seende slik ut for søkemotorene:

Legg nå merke til den fullstendige mangel på tematisering og sammenheng i innholdet, eksempelvis sekvensene ”fedmefaktor 10 på topp” og ”vin og katter og hunder”. Det er helt åpenbart at linearisering har en degraderende effekt på stikkordposisjonering og tematisering.

Effekten blir faktisk enda verre jo mer tabeller og kode som blir lagt til i dokumentet. Der hvor vanlige besøkende ser en fin og organisert webside kan søkemotorene ende opp med å bare se støy og søppel.

Resultatet av linearisering er at man får et leksikografisk tre, og avslører den faktiske sammenhengen, slik søkemotorene ser dokumentet mellom verb, adjektiver og fraser – det viser den faktiske informasjonsstrukturen som er brukt.

I mange tilfeller vil linearisering avdekke dokumentkonsepter og skjulte grammatiske mønstre. Disse konseptene og mønstrene vil, med bakgrunn i “stemming”, senere bli brukt i forbindelse med LSI (Latent Semantisk Indeksering) eller lignende teknikker i de søkemotorene som støtter dette.

Konklusjonen er at linearisering understreker viktigheten av å følge en av W3C’s anbefalinger: at HTML tabeller skal brukes til å presentere tabelldata og ikke for å posisjonere elementer på et nettsted – da ska du heller benytte CSS.

Tokenisering, Filtrering og Stemming

Dokumentindeksering er prosessen som brukes for å omforme faktisk dokument tekst til en representasjon av tekst.

Tokeniseringen fjerner all unødig informasjon fra dokumentet; punktum og komma, utropstegn, apostrof, aksenttegn og så videre.

Etter at tokeniseringen er ferdig følger filtreringen. Det som skjer nå er at søkemotorene fjerner stoppord – vanlige, hyppig brukte ord som ikke gir noen verdi og som ikke gjør et dokument unikt: “og”, “i”, “om” og så videre. For robotsimulatoren jeg bruker for analyser av websider har jeg ca 120 norske stoppord.

Figuren under representerer prosessen fra tokenisering til fullført tekstrepresentasjon

Det er denne tekstrepresentasjonen som faktisk er basis for resultatsidene i henhold til gjeldende rangeringsalgoritmer.

Legg ellers merke til at jeg har hoppet over punktet stemming. Årsaken til dette er at moderne søkemotorer ikke benytter seg av stemming i akkurat denne sammenhengen.

For å gi mest mulig nøyaktige resultater bruker ikke disse “stemming” og støtter ikke bruk av jokertegn. Med andre ord så søker Google og andre moderne søkemotorer etter nøyaktig de ordene du skriver inn i søkeboksen. Et søk etter “googl” eller “googl*” vil ikke inkludere “googler” eller “googlin”.

Stemming vil si å strippe et ord slik at du får grunnstammen for ordet:

  • Markedsføring – Marked
  • Søkemotoroptimalisering – Søkemotor
  • Kataloger – Katalog
  • Strategisk – Strateg
  • Plassering – Plass

…og så videre

Vekting og indeksering

Nøyaktig hvordan vektingen foregår er umulig å si med sikkerhet – både fordi de forskjellige søkemotorene har forskjellige algoritmer, og selvsagt også fordi disse algoritmene er topp hemmelige. Men det er selvsagt likhetstrekk, og dette er en generalisert beskrivelse av prosessen basert på, og fritt oversatt fra Googles offentliggjorte beskrivelser.

Google har en URL server som sender en liste over URLer som skal bli besøkt av søkeroboten. Søkerobotene sender så innholdet, antageligvis etter linearisering, til en lagringsserver i denne komprimerte tilstanden. Hvert dokument får så et eget ID nummer som kalles docID.

Indekseringen blir foretatt av en indekseringsenhet og en sorteringsenhet, hvor indekseringsenheten utfører en rekke oppgaver; den leser innholdet, dekomprimerer og parser det. Hvert dokument blir så konvertert til et sett av ordforekomster kalt “hits” (ref. mitt poeng om tekstrepresentasjon).

Hit-oversikten inneholder informasjon om posisjon og prominens i dokumentet, font størrelse og kapitalisering. Denne informasjonen blir så distribuert til en rekke “beholdere” og på den måten opprettes en “forward indeks“.

I tillegg til dette lagres alle lenker ut fra og inn til dokumentet, samt informasjonen disse lenkene inneholder, det vil si ankertekst og eventuelle andre attributter.

URL “resolveren” (i mangel av et bedre norsk ord) leser denne informasjonen og konverterer relative URLer til absolutte URLer og på den måten oppretter docIDer. Så legges ankertekst i forward index’en og lager en oversikt over lenker til hvert docID.

Disse linkene blir så brukt til å regne ut PageRank for alle dokumentene. I Googles tilfelle er det snakk om Hilltop algoritmen, men beskrivelsene i dette opprinnelige dokumentet avviker nok noe fra dagens algoritme.

For de som alikevel ønsker å sette seg inn i hvordan Google regner dette ut kan dokumentet Block Rank anbefales. Men du er herved advart – dette er svært tunge greier. MSN har tilsvarende dokument om BlockRank tilgjengelig her.

Identifisering av felles navigasjonselementer

I tillegg, og som ikke er nevnt i “The Anatomy of a Large-Scale Hypertextual Web Search Engine”, prøver søkemotorene å identifisere faste navigasjonselementer, det vil si menypunkter som går igjen over hele nettstedet eller i seksjoner på nettstedet.

Årsaken til dette er at slike navigasjonselementer konsekvent blit tillagt adskillig mindre vekt da de ikke er relevant for det individuelle dokumentets viktighet – i stedenfor prøver søkemotorene å identifisere lenker unike for, og relatert til, det enkelte dokument og til den enkelte seksjon.

Nettopp på grunn av dette vil en typisk landingssidestrategi ofte ikke har noen kjangs til å hevde seg i konkurranseutsatte søk. Og det er derfor en solid intern lenkestrategi har så utrolig mye mer å si enn flisespikking på stikkortetthet og så videre.

Det var alt jeg hadde om søkemotorer og indeksering for i dag – jeg har kanskje til og med fått enkelte skeptikere til å endre mening om bloggen.

Har du noen kommentarer eller spørsmål er det bare å fyre løs ;)


9 kommentarer

Av bjorn@skitX , February 9, 2007



Av Eivind , February 9, 2007



Av Admin , February 9, 2007



Av Nils , February 20, 2007



Av Admin , February 20, 2007



Av Trond , May 10, 2007



Av Sverre Sjøthun , May 12, 2007



Av Websiden , May 26, 2007



Av Morten Østby , July 1, 2008





Legg inn en kommentar

Din email adresse vil aldri bli publisert eller misbrukt - Bortsett fra om du legger igjen kommentarspam.
Da blir vi sinte

Ndvendige felt er merket med *

*

*





Du burde følge oss på

RSS Feed Twitter

Mailoppdatering

(dette med spam gidder vi virkelig ikke, så du kan ta det helt med ro)