TBGsearch - Vectorbased Search Engine



In english:

Download source code and readme: tbgsearch.zip

Download just the readme: readme.txt

The description at this page is currenly only available in swedish. For english please see readme.txt.


In swedish:

När man skapar en egen sökmotor för tex ett forum eller annan datakälla som man vill ha indexerad finns det främst två dominerande tekniker, reversed index och vector space.

Nedan beskrivs både reversed index och vector space modellerna samt TBGsearch modellen som man kan säga är en kombination mellan reversed index och vector space.


Reversed index


Reversed index bygger på att man har en wordtabell som innehåller dom unika sökord som man har påträffat i datakällan vilka får ett unikt wordid. Wordtabellen har sedan en relation till själva matchtabellen som talar om vilka wordid förekommer i vilka messageid där messageid är det unika löpnumret som ett inlägg innehar i tex forumet.

Detta kan se tex ut på föjande sätt:

wordtabell:

[wordid], [word]
1, kalle
2, ska
3, åka
4, cykel

matchtabell:

[wordid], [messageid]
1, 1
1, 2
2, 1
3, 1
4, 2

Ovanstående ger då att inlägg nummer 1 (messageid) i forumet innehåller dom unika orden "kalle, ska, åka" medan inlägg nummer 2 (messageid) innehåller dom unika orden "kalle, cykel".

Ett av flera problem med reversed index är att själva matchtabellen snabbt blir väldigt stor och otymplig (vilket i sin tur påverkar prestandan). Om man har 1.000.000 inlägg att indexera och varje inlägg i snitt innehåller 100 unika ord ger detta att matchtabellen blir minst (wordid och messageid antas vara 32 bitars unsigned int) 1.000.000 * 100 * (4 + 4) = 800.000.000 bytes. Dvs ett index som är minst 800 megabytes stort (och då har inte databasens styrkoder räknats med då 4 + 4 bytes är en grov förenkling av diskutrymmet som krävs).

När man sedan nyttjar reversed index till själva sökningen behöver man använda sig av GROUP BY, dvs gruppera sökträffarna per wordid och endast plocka ut dom messageid som innehåller samtliga sökord man söker efter (om vi förutsätter en AND sökning likt hur Google fungerar, dvs att samtliga sökord ur sökningen skall finnas med i sökresultatet).

Detta leder till att man behöver "fuska" för att minska datamängderna som databasen måste bearbeta i sin GROUP BY (tex om klientens sökord är vanligt förekommande i indexet).

Ett av dessa "fusk" är att nyttja en stopwordlista. Dvs att man exkluderar vanligt förekommande bindeord såsom "och", "men", "att" osv. Problemet med denna optimering är att det finns olika stoppord beroende på vilket språk man bearbetar (stopwordlistan för engelska skiljer sig från stoppwordlistan för svenska). Ett annat problem med detta är att klienten trots allt vill i vissa situationer ändå kunna söka på stoppord vilket då inte går om man nyttjar en stopwordlista för att minska ner på indexstorleken.

Ett annat "fusk" är att begränsa antalet träffar som hämtas från indexet för att på så vis ha mindre data att bearbeta. Om vi tex i slutändan begränsar sökningen till dom 200 bästa träffarna kan vi i subfrågan hämta ut dom 2000 bästa träffarna (dvs 10x slutresultatet). Om vi då söker på 3st sökord och plockar ut dom 2000 första träffarna för respektive sökord och sedan drar ett tvärsnitt mellan sökorden där vi plockar ut dom 200 första träffarna som alla sökorden har gemensamt har vi på ett effektivt sätt minimerat datamängderna som databasen måste bearbeta för en GROUP BY. Problemet med detta är att om första svepet ger färre än 200 träffar så måste vi upprepa proceduren tills alla sökord har bearbetats om klienten vill vara säker på att denne får samtliga sökträffar i retur vilket naturligtvis ökar söktiden.

För att optimera ovanstående "fusk" kan man införa ett tredje "fusk" där man under indexeringsfasen räknar hur ofta respektive sökord förekommer i datakällan, dvs sökordets frekvens. När sökningen påbörjas tittar man då först i wordtabellen om alla sökord som klienten söker på förekommer. Därefter tittar man på det sökord som har lägst frekvens. Om ett av sökorden då har färre än 200 i frekvens så vet vi att det är endast dom messageid för det aktuella sökordet vi behöver matcha mot övriga sökord som klienten har skickat in till sökmotorn.

Förenklat kan man säga att bristerna för reversed index är att den tar en betydande storlek gällande diskutrymme samt ger en hel del knepiga SQL problem som måste lösas (förutsatt att man lagrar tabellerna i en sqlmotor som tex MySQL eller vilken sqlmotor man nu föredrar).


Vector space


Med vector space är uppbyggnaden istället för en grund i en wordtabell så är grunden en messagetabell. Dvs varje inlägg har en egen rad i messagetabellen. Sökdatat utgörs av en bitvektor (som lagras som en binär sträng) där varje position i bitvektorn innebär vilka sökord aktuella inlägget innehar.

Detta kan se tex ut på föjande sätt:

messagetabell:

[messageid], [bitvector]
1, 00110
2, 00101
3, 10001

wordtabell:

[wordid], [word]
1, kalle
2, ska
3, åka
4, cykel
5, imorgon

Syftet med vector space är att man med hjälp av dom satta bitarna i bitvektorn kan beräkna en vinkel (kallad för relevans) för hela vektorn. Vinkeln är ett tal mellan 0 till 1. Genom att matcha sökbegreppet från klienten mot wordtabellen får man ut en sökvektor som beräknas om till en vinkel. Denna vinkel matchar man sedan mot messagetabellen för att se vilka inlägg som har samma eller snarlik vinkel.

Dom inlägg som har en differans av 0.0 vet man har exakt matchning därefter ökar differensen (skillnaden) gällande hur många av dom sökord man söker på som inlägget inhåller. Här får man begränsa sig till om man tex endast tillåter differensen 0.0 eller om man tillåter en differens upp till säg 0.1 (vilket skulle tex innebära att inlägget innehåller 4 av dom 5 sökorden klienten har i sitt sökbegrepp).

För att slippa beräkna vinkeln för tex 1 miljon inlägg vid varje sökning så beräknar man vinkeln (relevansen) på förhand och lagrar tillsammans med inläggsnumret. Detta är även vector space modellens svaghet. Eftersom när ett nytt unikt sökord dyker upp kommer bitvektorn att förändras för samtliga inlägg vilket i sin tur gör att vinkeln för samtliga inlägg förändras. Dvs indexeringsfasen blir väldigt långsam samtidigt som man måste lagra en betydande andel information för varje inlägg. Dvs om det förekommer 200.000 unika sökord i datakällan leder det till att varje inläggsnummer får en bitvektor som är 200.000 bitar stor (25 kilobyte). Visserligen kan man här nyttja datakomprimering för lagring av vektorn men den stora nackdelen blir att hela tiden behöva räkna om vinkeln (relevansen) för samtliga inlägg så fort ett nytt sökord dyker upp.

Utan datakomprimering leder det till att indexet blir något i stil med 1.000.000 * (25.000 + 4) = 25.004.000.000 bytes (cirka 25 gigabyte), men då det är glesa vektorer (på engelska sparse vectors) det handlar om (om vi nyttjar storleksberäkningen från reversed index exemplet dvs att varje inlägg innehåller 100 unika sökord) kan dessa komprimeras effektivt med tex LZF metoden vilket leder till att varje bitvektor i snitt tar på en höft 100 bytes i diskutrymme. Det diskutrymme som då krävs blir något i stil med 1.000.000 * (100 + 4) = 104.000.000 dvs 104 megabyte eller ännu mindre beroende på vad snittstorleken på dom LZF komprimerade bitvektorerna blir.


TBGsearch


TBGsearch tar det bästa ur två världar, dvs reversed index och vector space och slår ihop dessa till en ny sökmotoregenskap.

Det innebär att man nyttjar lagringseffektiviteten från att bruka bitvektorer (och då dom är glesa komprimera dessa med LZF eller motsvarande komprimeringsalgoritm) med indexeringshastigheten från reversed index metoden. En bieffekt är även att man kan dela upp bitvektorerna i chunks (delar) om tex 100.000 bitar per chunk.

Detta kan se tex ut på föjande sätt:

wordtabell:

[wordid], [word]
1, kalle
2, ska
3, åka
4, cykel

vektortabell:

[wordid], [chunkid], [bitvector]
1, 1, 00110
1, 2, 10000
2, 1, 00001
3, 1, 00100
4, 2, 11111

Bitvektorns positioner i kombination med chunkid motsvarar det unika inläggsnumret som inlägget där träffen finns innehar.

Om vi har en sökning innehållandes två sökord innebär detta att TBGsearch först tittar i vektortabellen vilka chunkid som är gemensamma för samtliga sökord (vi använder fortfarande AND sökningen precis som Google).

Därefter plockas dom matchande vektorerna ut antingen för det högsta gemensamma chunkid (senaste/nyaste inlägg) eller lägsta gemensamma chunkid (äldsta inlägg) beroende på om klienten har begärt att slutresultatet skall vara sorterade i descending mode eller ascending mode.

Dom vektorer som har plockats ut kommer att genomgå en bitvis AND operation mellan varandra vilket leder till att resultatvektorn innehåller 1:or på dom positioner där samtliga involverade vektorer för aktuella chunkid har gemensamt.

Tex:

Vektor för sökord 1: 001001011 och vektor för sökord 2: 111000001.

Resultatvektorn vid en AND operation blir då:

001001011
&111000001
----------
001000001

Om ovanstående var för chunkid = 2 där varje vektor är 9 bitar lång innebär det att positionerna 3 och 9 som har 1:or i resultatvektorn i själva verket motsvarar inlägg nummer (2 * 9) + 3 = 21 och (2 * 9) + 9 = 27. Dvs sökorden har en gemensam träff i inlägg nummer 21 och inlägg nummer 27. Om vi ännu inte uppnått 200 träffar (eller vad vi använder som maxvärde för träffar som skall returneras till klienten) upprepar vi proceduren tills alla gemensamma chunkid har processats eller tills vi uppnår 200 träffar.

Ett verkligt test med TBGsearch har givit följande mätvärden för 1.000.000 indexerade inlägg på http://www.tbg.nu:

* 601.288 unika sökord.
* wordtabellen är på 24,05 megabyte och 5,88 megabyte sqlindex.
* 1,39 miljoner sökvektorer.
* vektortabellen är på 251,17 meg och 18,44 meg sqlindex.

Snittstorleken på dom komprimerade vektorerna är 169 bytes (jämfört med 12,5 kilobyte om man inte hade komprimerat dessa). Där största komprimerade vektorn är 12501 bytes och den minsta komprimerade vektorn är 2 bytes.

En "worstcase" sökning som har använts för att jämföra dom olika sökmotorerna och deras prestanda (där sökbegreppet innehåller dom 10 mest förekommande sökorden ur sökindexet) har givit följande mätvärden för en dual p2 333MHz maskin:

* reversed index utan "fusk" (dvs ingen begränsning till 2000 träffar i första svepet): 24.0 sekunder.
* reversed index med "fusk" (dvs första svepet begränsas till 2000 träffar): 1.66 sekunder.

I ovanstående fall ockuperade reversed index metoden 1800 megabyte i diskutrymme där rådatat för forumet var på cirka 755 megabyte.

TBGsearch metoden gav en söktid på 0.06 sekunder på dual p2 333MHz maskinen samt 0.01 sekunder på en amd xp3200+ maskin.

Detta ger att TBGsearch till skillnad från reversed index tar betydligt mindre diskutrymme i anspråk samtidigt som söktiderna är betydligt lägre/snabbare. Som jämförelse kan nämnas att en sökning mot Google på dessa 10 sökord där det dessutom lagts till "site:www.tbg.nu" för att begränsa sökresultatet till det som Google har indexerat av www.tbg.nu tar 0.37 sekunder första gången och 0.07 sekunder i cachat läge.

Diskussion kring TBGsearch och hur den har utvecklats finns tillgängligt på http://www.tbg.nu/news_show/84370/1 där även eventuella frågor kan ställas.

/Apachez