prefixbomen

Prefixbomen, ook wel prefixbomen of tries genoemd, zijn een boomgebaseerde datastructuur die een dynamische verzameling strings opslaat. In een prefixboom komt elke knoop overeen met een prefix van een of meer opgeslagen sleutels, en elke rand draagt een teken. De wortel stelt de lege prefix voor en een sleutel wordt meestal gemarkeerd op de knoop waar de volledige string eindigt. Doordat gemeenschappelijke prefixes worden gedeeld, kan de structuur grote verzamelingen strings met overlappende prefixes efficiënt vertegenwoordigen.

Kernbewerkingen zijn onder meer invoegen (insert), exacte zoekopdracht (lookup) en prefix-zoekopdracht (startsWith). De bewerkingstijd is O(m), waarbij m de lengte van de sleutel is. Prefixzoeken kan snel zijn doordat gedeelde prefixes eerder gevonden worden. Het geheugen is in het ergste geval recht evenredig met het totaal aantal tekens van alle opgeslagen sleutels, maar gedeelde prefixes verminderen redundantie.

Varianten en optimalisaties omvatten compacte prefixbomen (Patricia- of radix-tries), die lange vertakkingen verkorten door opeenvolgende knopen met één kind samen te voegen. Andere varianten richten zich op specifieke toepassingen, zoals suffix-tries of DAWGs. Sommige implementaties gebruiken arrays of hashmaps voor de kinderen, wat snelheid of geheugenbalans beïnvloedt.

Toepassingen omvatten autocompletion, spellingscontrole en woordenboeken, evenals IP-routing en andere netwerktechnieken waar prefix-matching vereist is. Ze komen ook voor in tekstindexering en verschillende stringverwerkingsopgaven waar snelle prefixopzoeken nuttig is.

Historisch gezien dateren de ideeën uit de jaren vijftig en zestig. Een vroege variant, de b-trie, werd geïntroduceerd door René de la Briandais, en de term trie is afgeleid van retrieval. Tegenwoordig blijven prefixbomen eenFundamentele datastructuur in informatica en taalverwerking.