Een zoekfunctie die typefouten vergeeft: hoe foutentolerantie echt werkt

Het probleem, nauwkeurig geformuleerd

Een klant die zoekt op “hummingbrid” bedoelt vrijwel zeker “hummingbird”. Een zoekvak dat voor die zoekopdracht geen enkel resultaat teruggeeft, is niet om een goede reden streng: het faalt op het enige waarvoor het bestaat, namelijk vinden wat de persoon bedoelde, en niet alleen wat hij typte. Foutentolerantie is de algemene naam voor de mechanismen die die kloof dichten. Het lijkt één functie. In werkelijkheid zijn het ten minste twee verschillende mechanismen, met verschillende kosten en verschillende manieren om te falen, en juist door ze te verwarren gaan de meeste naïeve implementaties de fout in.

De basisbouwsteen: de bewerkingsafstand

Bijna alle mechanismen voor foutentolerantie, welke zoekmachine ook, berusten op hetzelfde onderliggende idee: de bewerkingsafstand tussen twee tekenreeksen, meestal de Levenshtein-afstand, die het minimale aantal invoegingen, verwijderingen of vervangingen van één teken telt dat nodig is om de ene reeks in de andere om te zetten. “Overhemt” ligt één vervanging van “overhemd”. “Overhmed” in plaats van “overhemd”, met twee naast elkaar liggende letters verwisseld, is één transpositie: twee bewerkingen volgens de klassieke definitie van Levenshtein, slechts één in de Damerau-Levenshtein-variant, die de omkering als één enkele bewerking telt. Het getal alleen beslist niets; wat telt, is wat het systeem ermee doet.

Het detail dat u vanaf het begin moet regelen: een afstand van één of twee bewerkingen is royaal voor een lang woord en gevaarlijk voor een kort woord. Twee bewerkingen op een woord van tien letters veranderen het nauwelijks. Twee bewerkingen op een woord van drie letters kunnen er een heel ander woord van maken: “zee” en “zes” liggen één bewerking uit elkaar, maar “zee” en “tee” ook, net als “zee” en “zeg”. Een systeem voor foutentolerantie dat dezelfde afstandsdrempel toepast ongeacht de lengte van het woord, zal korte, verschillende woorden vrolijk in elkaar “corrigeren”. De eerlijke correctie is een drempel die met de lengte meeschaalt: geen correctie op zeer korte woorden, één bewerking toegestaan vanaf een paar letters, twee bewerkingen alleen als het woord lang genoeg is om na twee wijzigingen herkenbaar te blijven.

Twee verschillende mechanismen, vaak verward tot één functie

“Foutentolerantie” verwijst meestal naar een van twee werkelijk verschillende dingen, en welke een systeem biedt, bepaalt wat het wel en niet kan.

1. Fuzzy matching op het moment van de zoekopdracht

Elasticsearch, OpenSearch en vergelijkbare zoekmachines kunnen een fuzzy-query uitvoeren (of de parameter fuzziness van een match-query gebruiken) die de gezochte term met de geïndexeerde termen vergelijkt via de bewerkingsafstand, op het moment van de zoekopdracht, zonder vooraf te hoeven weten welke fouten er bestaan. Dat werkt omdat de zoekmachine al een omgekeerde index heeft van alle termen die in de catalogus voorkomen; een fuzzy-query komt er grofweg op neer dat “de geïndexeerde termen worden gezocht die hoogstens N bewerkingen van deze term verwijderd zijn, en de resultaten worden gerangschikt naar hun nabijheid”. Ze vergt geen aparte onderhoudsstap en degradeert geleidelijk: een licht onjuiste zoekopdracht rangschikt nog steeds de dichtstbijzijnde geïndexeerde termen bovenaan. De echte kosten verschijnen bij een veld met hoge kardinaliteit of een zeer grote woordenschat, waar het berekenen van de bewerkingsafstand over een grote verzameling kandidaat-termen zwaarder is dan een zoekopdracht op een exacte term; daarom wordt fuzzy matching meestal selectief toegepast (het hoofdveld met vrije tekst, niet elk trefwoordveld) in plaats van overal standaard.

2. Correctie met een woordenboek, alleen toegepast wanneer het nodig is

Een systeem zonder zoekmachine die fuzzy-overeenkomsten van nature scoort, bijvoorbeeld een eenvoudige zoekfunctie op basis van SQL, moet het mechanisme zelf bouwen: een woordenboek van geldige termen, opgebouwd uit de product- en merknamen van de catalogus, waarmee een zoekterm die niets opleverde wordt vergeleken om het dichtstbijzijnde echte woord te vinden. Het woordenboek wordt gewoonlijk geïndexeerd op trigrammen van tekens (fragmenten van drie letters) in plaats van bij elk woord letter voor letter te worden vergeleken, zowel omdat een trigramindex de lijst van kandidaten beperkt tot waarschijnlijk nabije woorden voordat de exacte bewerkingsafstand over een veel kleinere verzameling wordt berekend, als omdat er geen externe zoekmachine voor nodig is.

Het detail dat deze aanpak in de praktijk zuinig maakt, in plaats van er een prestatievalkuil van te maken, is het moment waarop het zoeken in het woordenboek wordt uitgevoerd. Als elke zoekopdracht de kosten van een raadpleging van het woordenboek moest betalen, zou foutentolerantie alle zoekopdrachten vertragen, ook de correct getypte die al resultaten vonden. De raadpleging hoeft pas te worden uitgevoerd nadat de exacte zoekopdracht leeg is teruggekomen: een correcte zoekopdracht komt er nooit mee in aanraking, en alleen het geval zonder resultaten betaalt de meerkosten. Gemeten op een echte catalogus namen een goed gespelde zoekopdracht en een verkeerd gespelde zoekopdracht die de raadpleging van het woordenboek activeert in beide gevallen dezelfde, korte tijd in beslag (beide tussen 0,16 en 0,19 seconde op deze specifieke installatie): het pad via het woordenboek voegt alleen kosten toe aan zoekopdrachten die anders helemaal niets hadden opgeleverd.

Het woordenboek vraagt ook onderhoud waar een fuzzy-query geen behoefte aan heeft: het moet nieuwe woorden leren naarmate de catalogus groeit en de woorden van producten die niet meer bestaan vergeten, anders veroudert het langzaam en gaat het correcties voorstellen naar producten die zijn opgegeven. Een woordenboek dat volgens een schema wordt herbouwd (bijvoorbeeld wekelijks, plus een aanvulling op verzoek de eerste keer dat een zoekopdracht zonder resultaten een woord nodig heeft dat het nog niet kent) blijft op de catalogus afgestemd zonder bij elke zoekopdracht te worden herbouwd.

Waar de eenvoudige versie breekt

• Een vaste drempel voor de bewerkingsafstand voor woorden van alle lengtes, zoals hierboven gezien: een royale correctie op korte woorden verandert verschillende woorden in elkaar.
• Een zoekopdracht corrigeren die al resultaten heeft. Als een zoekopdracht die al producten vond ook naar een andere, populairdere term wordt “gecorrigeerd”, kan de klant worden weggeleid van wat hij werkelijk typte en worden gestuurd naar wat de zoekmachine nabij en populair vindt. De correctie hoort thuis na een echte zoekopdracht zonder resultaten, niet als een permanente herschrijving van elke zoekopdracht op de achtergrond.
• Een correctie die ongemerkt wordt geactiveerd wanneer dat niet zou moeten. Op een zoekpagina met facetten kan een selectie van filters legitiem nul resultaten opleveren (een klant heeft een combinatie van maat en kleur gekozen die niemand op voorraad heeft). Dat is geen spellingprobleem, en een laag voor foutentolerantie die het verschil niet kan zien, zal proberen een perfect gespelde term te “corrigeren” omdat de filters, en niet het woord, de pagina hebben leeggemaakt.
• Erop rekenen dat fuzzy matching ook juiste facetten garandeert. Ervoor zorgen dat een verkeerd gespelde zoekopdracht toch producten vindt, is een ander probleem dan correct tellen hoeveel producten bij elke filterwaarde horen. Een foutentolerante zoekmachine die resultaten vindt voor “hummingbrid” berekent zonder aarzelen de aantallen van de facetten voor diezelfde fuzzy-overeenkomst; als een element verderop (bijvoorbeeld een autocompletelijst van “populaire zoekopdrachten”) ervan uitgaat dat “minstens één product gevonden” betekent “het was een echte, correct gespelde term”, zal het de typefouten van de webwinkel gewillig opnieuw aan elke bezoeker tonen. Juist omdat de tolerante zoekmachine haar werk goed doet, wordt die fout elders in hetzelfde systeem gemakkelijk gemaakt.
• Stilte in plaats van transparantie. Een zoekfunctie die de getypte term ongemerkt door een andere vervangt, zonder aan te geven dat er een vervanging heeft plaatsgevonden, laat de klant zich afvragen waarom de resultaten niet helemaal overeenkomen met wat hij zocht. Een zichtbare, eerlijke regel, “Geen resultaten voor X. Dit zijn de resultaten voor Y”, kost één zin en voorkomt die verwarring volledig.

Een korte checklist

• Stem de toegestane bewerkingsafstand af op de lengte van het woord; pas niet dezelfde drempel toe op een woord van drie letters en op een van twaalf.
• Corrigeer alleen na een echte zoekopdracht zonder resultaten, nooit door een stille herschrijving van een zoekopdracht die al iets had gevonden.
• Maak onderscheid tussen “het woord was verkeerd gespeld” en “de filters hebben de pagina leeggemaakt”: beide vragen een andere behandeling, en ze verwarren leidt tot een poging tot correctie waar die niet op haar plaats was.
• Als u een eigen woordenboek onderhoudt in plaats van te steunen op de ingebouwde fuzzy-scoring van een zoekmachine, houd het dan actueel: herbouw het volgens een schema en laat het van de catalogus leren naarmate die verandert, anders gaat het woorden voorstellen die niet meer bestaan.
• Zeg de klant wanneer er een vervanging heeft plaatsgevonden. Laat een “geslaagde” fuzzy-overeenkomst niet verbergen dat wat hij typte en wat hij kreeg niet hetzelfde woord zijn.

Kort samengevat

Foutentolerantie is geen aan/uit-schakelaar: het is een keuze tussen twee verschillende mechanismen, de eigen fuzzy matching van de zoekmachine op het moment van de zoekopdracht, of een onderhouden woordenboek dat alleen bij een echte zoekopdracht zonder resultaten wordt geraadpleegd, elk met eigen kosten en een eigen manier om zich stilzwijgend te vergissen. De twee fouten om op te letten zijn het corrigeren van woorden die helemaal niet verkeerd gespeld waren, en erop rekenen dat fuzzy matching vragen beantwoordt waarvoor ze niet is ontworpen, zoals een exacte telling van facetten. Wij regelen dit in cll_essearch, onze module voor zoeken en gefacetteerde navigatie voor PrestaShop, zowel met de eigen fuzzy matching van Elasticsearch als met ons eigen trigramwoordenboek voor webwinkels die de eigen zoekmachine van de database gebruiken, als u dit onderscheid wilt zien toegepast op een echte webwinkel.

Elasticsearch-zoekfunctie & gefacetteerde navigatieRazendsnelle zoekfunctie met typfouttolerantie en moderne gefacetteerde navigatie in een venster, met de…€ 99,99Bekijk product