Prefixlängderna

Prefixlängderna är ett begrepp som används inom strängbearbetning och informationsbehandling för att beskriva längderna på prefix av en given sträng eller sekvens. Begreppet används framför allt när man studerar hur en sträng byggs upp ur sina initiala tecken eller i sammanhang där längden på ett prefix påverkar algoritmer och datastrukturer.

Formellt definieras prefixlängderna för en ändlig sträng w över alfabetet Σ som mängden P(w) = {|p| : p är ett prefix till w}. Eftersom varje prefix har en viss längd upp till hela w, är P(w) vanligtvis {1,2,...,|w|}. Om man även räknar med det tomma prefixet kan P(w) inkludera 0.

Exempel: Låt w = "koja". Prefixlängderna är 1, 2, 3 och 4.

Användningar: prefixlängderna används i mönsterigenkänning och sökalgoritmer där man arbetar med prefixfunktioner (i KMP-algoritmen kallad prefixfunktion eller lps-/pi-funktionen), i datastrukturer som prefixträd (trie) där varje ords prefix utgör en nod, samt inom kodningsteori där längderna hos prefixkoder är viktiga för att uppnå avkodningsäkerhet.

Se även: prefixfunktion, border, trie, prefixkod.