Prefixzoeken

Prefixzoeken is een methode voor het terugvinden van items waarvan de termen beginnen met een gegeven prefix. Het is veelvoorkomend bij autocompletion, woord- en woordenboekzoekingen, en zoekinterfaces. Prefixzoeken maakt gebruik van indeksering om efficiënt kandidaten te identificeren.

In een typische implementatie wordt een dataset van strings preprocessen tot een prefix-gewuste structuur, zoals een trie (prefixboom). Een query met prefix P navigeert karakter voor karakter door de structuur tot aan de knoop die P vertegenwoordigt; alle strings in de onderboom onder die knoop zijn geldige matches. De bewerking is snel voor korte prefixen en schaalt met het aantal resultaten.

Veelgebruikte datastructuren zijn tries, gecomprimeerde tries (radix-trees) en Patricia-trees, die geheugen besparen door gemeenschappelijke prefixen te delen. Voor zeer grote catalogs kunnen databankindexen zoals B+-trees met prefix-matching of geïnverteerde indexen aangevuld met prefix-kartering worden gebruikt. Sommige systemen gebruiken ook suffix-arrays of prefix-hashing voor parallelle of aanvullende methoden.

Toepassingsgebieden zijn onder meer autocompletion in zoekmachines, programmeeromgevingen, messaging-apps en spellingswoordenboeken. Het ondersteunt ook incrementeel zoeken in contactlijsten en commandopaletjes.

Beperkingen omvatten het geheugenverbruik bij grote woordenlijsten, de afhandeling van hoofdletters en locale instellingen, de kosten van dynamische updates, en het rangschikken van resultaten wanneer veel matches bestaan. Voor fuzzy of éénvoudige afwijkende prefix-zoekingen zijn geavanceerdere algoritmen nodig.