substringzoek

Substringzoek is het proces waarbij een patroonstring P gezocht wordt in een grotere tekststring T. Het omvat het vinden van alle (of een enkel) voorkomen van P in T en speelt een centrale rol in tekstverwerking, data-analyse en bioinformatica. Het wordt toegepast in zoekfuncties, patroonherkenning en string matching in applicaties zoals editors, databases en compilers.

Eenvoudige aanpak: de brute-force of naive methode vergelijkt P op elke positie in T. Dit kan tot O(|T|·|P|) tekentijd leiden in het slechtste geval.

Belangrijke algoritmen: Knuth–Morris–Pratt (KMP) elimineert onnodige herhalingsvergelijkingen en draait in O(|T|+|P|) tijd; Rabin–Karp gebruikt hashing op substrings en biedt gemiddeld O(|T|+|P|) tijd, met een kans op worst-case verschuivingen afhankelijk van de hashfunctie; Boyer–Moore zoekt vanaf het einde van P en maakt gebruik van slechte-tegenwerkende en good-suffix-heuristieken, wat in de praktijk vaak zeer snel is.

Voor meerdere patronen en grote tekstbestanden worden suffix-constructies zoals suffix trees en suffix arrays gebruikt. Deze data-structuren maken snelle substringzoek mogelijk na voorbewerking van de tekst, met bouwtijden variërend van O(|T|) tot O(|T| log |T|) en zoektnelheden die vaak O(|P|) of O(|P| log |T|) bedragen, afhankelijk van de structuur. Voor meerdere patronen kan ook Aho-Corasick automatisaat worden toegepast.

Varianten en praktische overwegingen: het verschil tussen exact substringzoek en approximate matching (bijv. op basis van Levenshteinafstanden), tekstcodering, case sensitivity en Unicode-ondersteuning spelen een rol. In softwarebibliotheken wordt substringzoek doorgaans geïmplementeerd via efficiënt geoptimaliseerde algoritmen en vervolgde indexing.

Zie ook: string matching, pattern matching, suffix array, suffix tree, Aho-Corasick.