suffixbomen

Een suffixboom (meervoud: suffixbomen) is een datastructuur die alle suffixes van een tekenreeks op overzichtelijke wijze representeert. De boom is gericht en heeft labels op de randen die substrings voorstellen. Vanuit de wortel leiden paden naar bladknooppunten die elk een suffix van de oorspronkelijke tekenreeks representeren. Door de boom kan men snel informatie over substrings en hun locaties opvragen.

Eigenschappen en structuur: interne knopen representeren gemeenschappelijke prefixes van meerdere suffixes en kunnen meerdere kinderen hebben; randen zijn meestal gelabeld met substrings zodat de som van de labellengten overeenkomt met de lengte van de string. Elk blad komt overeen met een suffix van de oorspronkelijke tekenreeks. Een substringzoek kan door het volgen van de overeenkomstige randen in O(m) tijd gebeuren, waarbij m de lengte van het gezochte substring is.

Constructie en complexiteit: een suffixboom kan in lineaire tijd O(n) worden gebouwd voor een tekenreeks van lengte n, met algoritmes zoals Ukkonen’s algoritme. Bij een naïeve constructie kan de tijd O(n^2) oplopen. De ruimte is O(n) in termen van het aantal knopen en de totale lengte van de randlabels.

Toepassingen: suffixbomen worden gebruikt voor snelle substringzoek, patroonmatching, het vinden van de langste veelvuldige substring, en analyse in bioinformatica (bijv. DNA-sequenties). Ze zijn ook nuttig bij plagiaatdetectie en data-analyse voor repetitieve patronen.

Vergelijking met andere structuren: suffixbomen bieden snelle query’s maar vereisen meer geheugen en complexiteit dan bijvoorbeeld suffixarrays met de LCP-array; suffixarrays zijn vaak alternatief wanneer geheugen een prioriteit is. Geavanceerdere varianten omvatten gegeneraliseerde suffixbomen en gecomprimeerde vormen.