Prefixmatchning

Prefixmatchning är en operation inom text- och datastrukturteori som avgör om en given sträng börjar med ett specifikt prefix. Den används för snabb filtrering, sökning och organisering av data och är central i autocompletion, sökförslag och ordlistor. Inom nätverk och programmering används ibland Longest Prefix Matching för att välja det längsta matchande prefix.

Tekniskt används flera olika metoder. Prefixträd (tries) ger effektiva uppslag där tiden är proportional med inmatningens längd. Andra tillvägagångssätt omfattar sorterade listor med binär sökning eller radix-träd som minimerar minnesanvändningen. För flera mönster samtidigt används automata såsom Aho-Corasick, vilka möjliggör effektiv övervakning av många prefix samtidigt.

Vanliga tillämpningar inkluderar Longest Prefix Matching i IP-routning, där en rutt väljs baserat på det längsta överenskomna prefixet i adressen; autocompletion i textredigerare eller sökmotorer; filtrering och segmentering av dataflöden i program och nätverk samt kommando- och filnamnsförslag i operativsystemens skal.

Prestanda och begränsningar: uppslag i en trie är vanligtvis O(m) där m är längden på inmatningen, men minneskrav kan bli stort. Dynamisk uppdatering av prefixset måste hanteras effektivt. Behandling av teckenkodning och fältvariationer påverkar jämförelser. I vissa scenarier används komprimerade eller radix-träd för att reducera minnesanvändningen och förbättra cache-prestanda.

Se även: prefixträd, trie, longest prefix matching, autocompletion, text- och språkmatching.