prefixträd

Prefixträd, eller prefixträd (trie på engelska), är en datastruktur för lagring av en samling strängar där gemensamma prefix delas mellan ord. Strukturen möjliggör effektiva exakt-sökningar samt prefixbaserade sökningar, vilket gör den särskilt användbar för autokomplettering, stavningskontroll och ordlistor.

I ett prefixträd representeras varje tecken vanligtvis som en nod eller som en kant mellan noder. roten är tom, och varje väg från roten till en nod motsvarar ett prefix. En ordmarkering används för att indikera att det finns ett ord som slutar vid den noden. Noderna lagrar tecken och pekare till sina barn, vanligtvis som listor, mappar eller arrays, vilket gör att gemensamma prefix delas och sparar utrymme relativt att lagra varje ord separat.

Huvudoperationer är infoga ord, söka exakt ord och hitta ord som börjar med ett givet prefix. Inträdes-operationen följer tecken i ordet och skapar nya noder vid behov. Sökning följer samma väg och slutar när tecknen tar slut eller när en nod saknar motsvarande barn. Prefixsökning returnerar alla ord som börjar med det angivna prefix. Den generella tidskomplexiteten är O(L) per operation där L är ordets längd, och platsbehovet beror på det totala antalet tecken som lagras i trädet och hur gemensamma prefix delas.

Varianter och optimeringar inkluderar komprimerade prefixträd (Patricia-träd), radix-träd och ternära sökträd (ternary search trie). Dessa minskar minnesbehovet eller ökar prestanda i specifika scenarier.

Användningar omfattar ordlistor, autokomplettering i sökfält, stavningskontroll, ordbaserad suffix- och prefixhantering samt IP-routing där längsta-prefix-matchning används i vissa implementationer.

Historiskt härrör begreppet prefixträd till arbeten från 1950- och 1960-talen, där René de la Briandais introducerade tidiga trädstrukturer för lagring av ord. Termen trie används ofta som förkortning av prefixträd eller som ordlek för retrieval.