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.

Graafdatabanken

Databanken zijn softwarepakketten die ervoor zorgen dat je gegevens kan opslaan. De bekendste databanken zijn relationeel. Oracle, Postgresql, MySQL, MariaDB en SQL Server zijn enkele bekendere voorbeelden. De relationele databanken worden ook wel SQL-databanken genoemd omdat ze met een of andere versie van SQL kunnen beheerd worden. De gegevens worden opgeslagen in tabellen. Elke kolom van een tabel bepaalt een eigenschap en elke rij een item.

Al de andere DB’s worden vaak NoSQL-databanken genoemd, om de evidente reden dat ze niet (voornamelijk) met SQL werken. Iets minder bekend zijn waarschijnlijk key-value stores. De bekendste in zijn soort is waarschijnlijk Berkeley DB. Dat is al een oud beestje, waarvoor diverse alternatieven bestaan. Verder zijn er ook nog documentdatabases, zoals MongoDB, RavenDB en ArangoDB.

De grens tussen SQL- en NoSQL-databanken wordt soms vaag. Postgresql is bijvoorbeeld ook geschikt als documentdatabank en de makers claimen dat het als dusdanig zelfs efficiënter is dan zijn NoSQL-tegenhangers. Aan de andere kant bieden sommige NoSQL databanken ook ondersteuning voor SQL.

Als dat allemaal een belletje doet rinkelen, wel, dan gaat het hier nu over iets anders. Graafdatabanken focussen nog veel meer dan andere databanken op de verbanden die er tussen verschillende eenheden van gegevens kunnen bestaan. Relationele databanken doen dat ook, maar het combineren van tabellen is soms een dure onderneming (in termen van rekentijd). Met documentdatabanken hebben graafdatabanken gemeen dat het schema van de data niet strikt bepaald is. De gegevens in documentdatabases en graafdatabanken moeten niet in een strak keurslijf passen, zoals bij strikt relationele databanken wel het geval is. In sommige gevallen bieden graafdatabanken het beste van de twee werelden.

Misschien is het concept van graafdatabanken wat hoogdrempelig. Ik denk dat je al moet weten wat een graaf is, en al wat ervaring ermee hebben opgedaan om echt optimaal gebruik te maken van een graafdatabank. Neo4J biedt op dat vlak uitstekende documentatie, en zelfs een gratis e-book, maar de vraag is of daarmee niet alleen mensen bereikt worden die al weten dat ze een graaf moeten kunnen opslaan.

Neo4J is een voorbeeld van een graafdatabank. Het is de graafdatabank waar ik het meeste ervaring mee heb. Op mijn GitHub-account kan je bijvoorbeeld een data entry tool vinden voor Neo4J. De verzameling hulpmiddelen die voor Neo4J beschikbaar zijn, zijn wat beperkter dan die voor de meeste relationele databanken. Een programma om efficiënt gegevens in te voeren ontbrak zelfs in mijn ogen, daarom ben ik maar zelf aan eentje begonnen. De markt die Neo4J bespeelt zit misschien eerder in de Big Data branche, waar data entry neerkomt op het schrijven en uitvoeren van een programma dat gegevens in de databank importeert.

Desalniettemin kan ik iedereen met interesse in grafen of databanken warm aanbevelen een kijkje te nemen in de kwalitatieve software die al bestaat en de concepten rond graafdatabanken. De beste start is waarschijnlijk het boek Graph Databases van O’Reilly, waarin de context van graafdatabases nog veel beter en uitvoeriger uitgelegd staat dan hier.