Hoe werkt een zoekmachine?

Een zoekmachine kan je gebruiken om een document, een bestand, een webpagina of zelfs foto’s of video’s te zoeken. Sommige zoekmachines staan op gigantische servercomplexen, terwijl andere gewoon op je eigen PC, tablet of smartphone draaien. Het basisprincipe is al veel ouder dan computersystemen: de indexpagina’s achterin een boek zijn een voorloper van de huidige zoeksystemen.

Voordat je zoekresultaten krijgt voorgeschoteld worden er enkele stappen overlopen. Laat ons eerst even kijken hoe je naar een tekst kan zoeken door een woord op te geven dat in die tekst voorkomt.

Stel dat je vijf teksten hebt, waarin telkens een woord voorkomt dat kenmerkend is voor die tekst, het komt dus in die ene tekst voor en niet in de vier andere teksten. We hebben bijvoorbeeld vijf teksten, die uit slechts 1 zin bestaan, met de karakteristieke woorden hond, kat, muis, rat en pony.

  • Een hond heeft vier poten en kwispelt met zijn staart.
  • Een kat heeft vier poten en een staart en kan lang naar je blijven staren.
  • De muis piept van geluk als hij een stukje lekkere kaas ziet.
  • De rat zit in de val, als een …
  • Een pony is geen babypaard, want dat is een veulen.

Als we “hond” intikken en op “zoeken” klikken, willen we de eerste tekst zien. Maar hoe kan een computersysteem nu de link leggen tussen het woord “hond” en de eerste tekst? Hoe kan een computersysteem weten als we “hond” intikken, dat we dan niet een andere tekst willen zien?

Het zoeksysteem werkt met een index. De index geeft de relatie aan tussen mogelijke zoektermen en de originele teksten, of zelfs specifieke locaties in die originele teksten. Voor elk woord dat in de teksten voorkomt is er een sleutel in de index. “hond” is een sleutel en verwijst in dit geval bijvoorbeeld naar document 1, positie 2. Sommige woorden komen in verschillende teksten voor. Het woord “staart” staat bijvoorbeeld zowel in document 1 als in document 2. In de index vertaalt zich dat in 1 sleutel “staart” met 2 bijhorende waarden: document 1, positie 10 en document 2, positie 8. Als je naar “staart” zoekt, krijg je dus 2 documenten terug. De index wordt meestal op schijf opgeslagen, in een formaat dat daar specifiek voor geoptimaliseerd is. Soms wordt een index ook in het werkgeheugen gehouden, als snelheid van zoeken cruciaal is.

Tot nu toe gingen we ervan uit dat het maken van een index piece of cake is. In de praktijk kan dat dik tegenvallen. In bepaalde gevallen heb je zelfs voor iets dat er zo eenvoudig uitziet als het splitsen van een tekst in zinnen en woorden al een diepgaande analyse van de tekst nodig. Soms is zelfs dat onvoldoende om een tekst grondig klaar te maken voor het indexeren. Dat ‘klaarmaken’ heet analyseren, of ook wel tokenizen. Tokenizers of analyzers bestaan er in allerlei varianten qua complexiteit, van het eenvoudig splitsen op spaties tot een uitgebreide linguïstische analyse. In ons eenvoudige voorbeeld kan je al zien dat splitsen op spaties niet volstaat, omdat de tekst ook leestekens bevat.

Behalve de analyse kan ook de grootte van de index een beperkende factor worden. Vanaf een bepaalde grootte kan je gewoon niet meer werken met 1 computer en moet je uitbreiden naar een parallelle index of een cluster. In bepaalde projecten is het verwerven van de inhoud die moet geïndexeerd worden op zich al een uitdaging. Documenten uit verschillende bronnen moeten dan bijvoorbeeld uniek geïdentificeerd worden en je moet je ervan verzekeren dat de meest recente versie geïndexeerd is.

Tenslotte krijg je de resultaten terug voor je zoekopdracht. Meestal krijg je een teaser te zien, met een knop of hyperlink die je naar het volledige document kan brengen. In de presentatie van de zoekresultaten is op zich al menig uur werk gekropen. Als je veel resultaten hebt, is het soms moeilijk om precies dat ene eruit te pikken waarnaar je zocht. De zoekmachine probeert je daarmee te helpen door de documenten (en dus de zoekresultaten) te sorteren op relevantie. De relevantie is een score die aangeeft hoe goed een zoekresultaat past bij de zoekopdracht (en soms ook bij de geschiedenis van zoekopdrachten of bij het profiel van de persoon die de zoekopdracht uitvoert). Voor firma’s die van zoeken hun core business hebben gemaakt is het algoritme voor het bepalen van de relevantie strikt geheim. Voor een off-the-shelf systeem is dat meestal een variant van TF-IDF. Hoe vaker een zoekterm voorkomt in een document, hoe relevanter dat document, en hoe zeldzamer een woord voorkomt in de documentcollectie, hoe meer invloed dat woord heeft op de relevantie.

Samengevat worden de volgende stappen dus overlopen: verwerven en ophalen van de teksten, analyse van de brontekst en indexering van de geanalyseerde tekst. Eenmaal de teksten geïndexeerd zijn kunnen ze doorzocht worden. Het doorzoeken  kent een score toe aan de gevonden documenten. Die worden uiteindelijk gesorteerd volgens relevantie. Tenslotte wordt worden de meest relevante documenten weergegeven.

Als je op zoek bent naar een zoeksysteem dat je volledig aan je wensen wil aanpassen en je weet wel van wanten op vlak van programmeren, dan is Lucene of een van zijn varianten in jouw favoriete programmeertaal zeker een aanrader. Naast Lucene bestaan er nog diverse alternatieven. Zoektechnologie is tegenwoordig zeer geavanceerd. Lucene is dan ook een uitgebreide toolkit waarmee je alle kanten uit kan. Op mijn Github-pagina kan je bijvoorbeeld een tool op basis van Lucene vinden waarmee je kan zoeken naar teksten die verwant zijn met elkaar. Hoogstwaarschijnlijk meer daarover bij een volgende gelegenheid.

Geef een reactie

Het e-mailadres wordt niet gepubliceerd.