Typo tolerantie

De typo-regels worden gebruikt vóór het sorteren van de documenten. Ze worden gebruikt om documenten samen voegen, om te kiezen welke documenten woorden bevatten die lijken op de opgevraagde woorden.

Instant Search gebruikt een 'prefix Levenshtein algoritme' om te controleren of de woorden overeenkomen. Het enige verschil met een normaal 'Levenshtein algoritme' is dat het elk woord accepteert dat ook met de gezochte woorden begint. Daarom worden woorden geaccepteerd als ze beginnen met of even lang zijn.

De Levenshtein afstand tussen twee woorden M en P heet "de minimale kosten om M in P om te zetten" door de volgende elementaire bewerkingen uit te voeren:

  • vervanging van een teken van M door een ander teken dan P. (b.v. kitten → sitten)
  • invoegen in M van een teken van P. (bv. sitten → zitten)
  • schrapping van een teken uit M. (bv. zaterdag → zatedag)

Er zijn enkele regels over wat als "gelijksoortig" (of typo) beschouwd kan worden. Deze regels gelden per woord en niet voor het gehele zoekwoord.

  • Als het zoekwoord tussen 1 en 4 tekens lang is, is geen typefout toegestaan. Alleen documenten die woorden bevatten die beginnen met of even lang zijn als dit zoekwoord worden als geldig voor dit verzoek beschouwd.
  • Als het zoekwoord tussen 5 en 8 tekens lang is, is één typefout toegestaan. Documenten die woorden bevatten die met één typefout overeenkomen, worden voor de volgende stappen bewaard.
  • Als het zoekwoord meer dan 8 tekens bevat, accepteren we maximaal twee typefouten

Dit betekent dat "zaterdag", dat 7 tekens lang is de tweede regel gebruikt, en dat elk document dat woorden bevat die maar één typefout hebben, overeenkomt. Bijvoorbeeld:

  • "zaterdag" wordt geaccepteerd omdat het hetzelfde woord is.
  • "zat" wordt niet geaccepteerd omdat het zoekwoord er geen voorvoegsel van is (het is het omgekeerde).
  • "zatedag" wordt geaccepteerd omdat het één typefout bevat.
  • "zatudag" wordt niet geaccepteerd omdat het twee typefouten bevat.