Sökmotor People
FEATURED KUNDER
Certifieringar
Välkommen! Tack för besök!
Prenumerera på full feed
Hur Sök verkligen fungerar: Komprimerade Index
av Ruud Hein.
Det här inlägget är en del av en pågående serie: Hur Sök verkligen fungerar.
Förra veckan: tolka detta index?
Minne är mycket snabbare än att titta upp.
För en sökmotor i hög efterfrågan att dess användare effektivt det ska hålla saker i minnet istället för att titta upp på en disk.
Traditionellt stora sökmotorer kommer att behålla sina kompletta ordlistan i minnet och utstationering lista på disk.
Ineffektiv Lagring
Givetvis desto mer kan du hålla i minnet och mer information kan läsas tillbaka med en skiva insatser, desto bättre.
Tyvärr datainformation blir ineffektivt förvaras i lådor med fasta dimension: Om en ruta är 10 tecken bred 4 tecken ordet fortfarande tar upp 1 låda med 10 tecken.
Komprimering
Lösningen är att pressa information tillsammans så minst utrymme innehåller högst mängd information.
Big String Compressed Dictionary
kan bli:
Genom att lägga till längden på varje ord på varje post som vi kan göra listan över ord hundratals tecken kortare.
Gap Compressed Spikblad Lista
kan bli:
Genom att lagra skillnaden mellan dokument ID (luckorna) vi kan spara hundratals tecken.
Samma sak kan göras för att lagra luckorna mellan indexnummer för uppkomst positioner i varje dokument.
Denna "komprimerad representation kodar förekomster av en term som en pekare till nästa förekomst av termen för att underlätta snabb uppräkning av de förekomster av ordet".
Du kan söka "förekomster av termer i den uppsättning av handlingar genom att följa pekare genom komprimerad representation".
Partiellt dekompression
Ett index som lagras på detta sätt är helt förlustfri: den behåller all information från dokument identitetsbeteckningen att dokumentera positionella identifikationskod.
Genom att börja med de minst ofta används termen för att söka det är mycket lätt att riva upp att göra en partiell tryckfall i detta index från
"Identifiera förekomster av termer i den uppsättning av handlingar"
(ordlista) - för att sedan använda;
"Motsvarande term identitetsbeteckningar för villkoren i sökfrågan för att slå upp en sikt kompenseras tabellen för en pekare till en första förekomsten av termerna i komprimerad representation av den uppsättning av handlingar"
(de allra första meddelanden dokument ID);
"Och efter en kedja av referenser börjar vid den första händelsen för att identifiera andra förekomster av termer i komprimerad representation av den uppsättning av handlingar"
(skillnaden komprimerade dokument ID list)
Rekommenderad läsning:
Jag hänger på Twitter där jag njuta av företaget, buzz, den nuggets av info och yttrande passerar vi tillsammans. Gå med mig på Twitter!
Som utsänd Hur Search verkligen fungerar på den 14 mars 2008.
8 Svaren hittills: 6 kommentarer och 2 trackback
Trackback / Pingbacks
[...] Hur Search verkligen fungerar: Komprimerade Index - Även en liten avancerad, fortfarande ett mycket trevligt att titta på hur en sökmotor fungerar genom att analysera Index [...]
[...] Det här inlägget är en del av en pågående serie: Hur Sök verkligen fungerar. Förra veckan: Komprimerade Index. [...]
Friend Connect
SENASTE LÄSARNA
Författarna
SEP blogginlägg visa alla
Populäraste DENNA MÅNAD
Populäraste ALL TIME
Nice post du kommer hit. Fortsätt med det goda arbetet, du har verkligen fina artiklar.
Tack för att jag vet, Benny. Du har en stor blogg kommer det, förresten. Funny foto alltför
Du får gärna slå mig på Twitter som helst.
Ruud, I Kinda har förlorat på detta. Rätt om här:
"Komprimerad representation kodar förekomster av en term som en pekare till nästa förekomst av termen för att underlätta snabb uppräkning av de förekomster av termen" ... Jag hatar att vara blond!
Kim, det talas om lagring av skillnader mellan siffrorna (det pekare).
Varje gång du arbetar med stora / långa tal, lagring av skillnaden mellan dessa siffror kostnader, i genomsnitt mindre utrymme än lagra de faktiska siffrorna.
Det kan även hjälpa till att snabba upp saker och ting.
Så istället för att säga "detta ord förekommer i dokumentet 1040, 1050 och 1052" som du säger "detta ord förekommer i dokumentet 1040, 10 dokument efter detta och 2 dokument efter att en".
Varje rad punkter till nästa plats: gå 2 gator ner .... 5 husen ytterligare ... 10 dollar extra etc.
Nice tekniska post Ruud:).
Tack Gabriel - tackar för kommentaren!