Sökmotorer kan verka som magiska. Du skriver vad du letar efter i en textruta, och - ping! - det verkar bara millisekunder senare. Självklart vet vi alla att Google är beroende av mer än en trollstav för att producera relevanta sökresultat. men vad använder den istället?

Tja, en sökmotor har tre olika faser: spider webben för att hitta och läsa webbsidor, indexera de webbsidor som hittats och svara på användarfrågor för att producera en uppsättning rankade resultat.

I den här artikeln kommer vi inte att prata alls om spidering-aktiviteterna, men du kan tänka dig att det är ett speciellt program som läser en webbsida, analyserar källkoden HTML och följer sedan URL-länkarna som hittades. Sidorna lagras sedan och analyseras ytterligare.

Indexering är en intressant algoritm. Syftet med att indexera webbsidor som hittas genom spidering är att producera snabba och exakta sökresultat. Om det inte är snabbt kommer användaren att gå någon annanstans; om det inte är korrekt, då ditto.

Det här var Google Out-gjorde sina konkurrenter i början: det var snabbare (hela vägen från att ladda sidan till produktionen av resultaten) och det var mer exakt (på grund av dess användning av PageRank-algoritmen). När sökmotorn har indexerat ett stort antal sidor kan det börja svara på sökfrågor.

Indexet måste byggas på ett sådant sätt att sökmotorn kan skapa en lista över webbsidor som uppfyller frågan och rangordna resultaten - snabbt - så att de mest relevanta och relevanta resultaten visas först. Så indexet är av största vikt, med rankningsalgoritmen lika stor.

Trots allt, före Google och PageRank, fanns det andra sökmotorer som AltaVista som visste hur man indexerade. Det var Googles ranking som förändrade allt. Standardtypen för datastruktur för textindex är känd som en inverterad fil. Antag att vi har en uppsättning textdokument. Det första steget är att analysera innehållet genom att analysera texten för att identifiera enskilda ord (eller tokens) i texten.

När vi har identifierat orden är det ganska enkelt att skriva en parser. Vi kan använda något som en statlig maskin (eller automat) eller regelbundna uttryck (som visserligen var utformade för denna typ av textparsing-uppgift). Men vad söker vi faktiskt?

Det enkla, intuitiva svaret är "bitarna mellan det vita utrymmet". Men det enkla svaret visar en skillnad mellan hur vi människor skannar text och hur datorn gör det. Ta till exempel en ny titt på första meningen i den här paragrafen. Genom att tillämpa denna definition som ett program (och med hjälp av fältparametrar för att avgränsa symbolerna här) så skulle vi kunna se ord som [simple,], ['bits] och [space.'].

Eftersom det är lite för grundläggande kan vi förfina definitionen till "ord är bitarna mellan det vita utrymmet och skiljetecken". Men igen faller vi i en fälla: För första meningen i denna punkt skulle denna definition nu skapa orden [som] och [s] för ordet "det är".

Sannolikt är det bästa svaret - åtminstone för att indexera engelsk text - att skriva en parsare som, när det ser ett skiljetecken, kontrollerar tecknet efter skiljetecken.

Om det är ett brev, är det troligtvis en förkortning som "det är" eller "det är", och det ska ingå i ordet. Ännu bättre, dagens dokument innehåller saker som e-postadresser och webbadresser. Dessa kan ses som "ord" i sin egen rätt, och denna ordparseralgoritm skulle fungera med dem också.

Självklart, för andra språk kan parsingord kräva andra algoritmer beroende på frågor som teckenuppsättningen som används (ideografisk text, till exempel, skulle vara intressant) eller grammatikreglerna för språket. Vid analys av texten är det troligt att vi hittar dubbla ord.

För ett enkelt index, som det vi använder här, är allt vi behöver veta om ett visst dokument innehåller ett visst ord. Vi är inte särskilt intresserade av om dokumentet använder det ordet en gång, två gånger eller tusen gånger. När allt kommer när vi kommer att visa listan med sökresultat, klickar användaren bara på en viss länk och går till den specifika webbadressen för att bläddra i dokumentet.

I vår parsing övning, då bör vi ignorera dubbletter och sträva efter en lista med använda ord. Nästa steg är att kasta ut orden som inte har sökbar mening eftersom varje dokument kommer att använda dem. Exempel på dessa stoppord (som de kallas) är "de", "a", "är", "jag", "i" och så vidare (och de sista tre orden också!).

Varje tillämpning av en textindexeringsalgoritm kommer att använda sin egen uppsättning stoppord, och dessa listor kommer att byggas upp och bibehållas vid körning från innehållet som ses. När allt är klart kommer vi att ha en tabell med dokumentnamn med en lista med ord för varje dokument, som visas i Figur 1.

Figur 1: Ett framåtriktat index innehåller alla ord som finns i ett visst dokument

Här har jag namngiven dokumenten som nummer, och i praktiken skulle vi ha ett annat bord som korsade dessa nummer till den faktiska webbadressen för dokumentet. Nästa steg är att invertera denna tabell; När allt kommer omkring, för en sökning ska vi få ett ord, och vi måste identifiera de dokument som innehåller detta ord.

Ordet ska vara nyckeln, och för tillfället skrivs bordet med dokumentnummer. Vad vi hamnar med är en tabell som visas i Figur 2. Tabellen är nyckelord med ord och data för varje post i tabellen är en lista över dokumentnummer. Denna struktur är känd som en inverterad fil. Med utgångspunkt från en tabell med ord per dokument slutar vi med en tabell med dokument per ord.

figur 2: Detta inverterade index är en lista som visar vilka dokument som innehåller ett visst ord