Prefixlängen

PrefixLängen ist ein Begriff aus der Informatik, der die Längen möglicher Präfixe einer Menge von Sequenzen beschreibt. Ein Präfix ist dabei ein Anfangsteil einer Sequenz. Die PrefixLängen einer Datenmenge S ⊆ A ergibt sich als die Menge aller Längen j, für die es ein Präfix p mit der Länge j gibt, das zu einem Element von S gehört. Formal ausgedrückt: PL(S) = { |p| : p ist ein Präfix von s ∈ S }. Die Werte können von 0 bis zur maximalen Sequenzlänge reichen. In der Praxis dienen PrefixLängen dazu, Strukturen zu optimieren oder zu analysieren, z. B. bei Trie-Datenstrukturen, in denen die Länge eines Präfix die Tiefe eines Knotens bestimmt, oder bei prädiktiven Indizes in Suchsystemen.

Beispiel: Aus der Menge S = {„apfel“,„apriot“,„banana“} ergeben sich Präfixe unter anderem wie "", "a", "ap", "apr", "apri" sowie "b", "ba", "ban" usw. Die resultierenden Längenmenge PL(S) enthält mindestens 0 und die Längen von 1 bis zur maximalen Wortlänge, je nachdem welche Längen tatsächlich als Präfix auftreten. In vielen Anwendungen werden nur Prismaprefixe entlang bestimmter Pfade betrachtet, wodurch die effektive PrefixLänge-Information stark variiert.

Neben der allgemeinen Bedeutung in der Trie- und Textverarbeitung wird der Begriff Präfixlänge in der Netzwerktechnik häufig als Synonym für die Länge eines Präfix verwendet. Dort gibt die Präfixlänge in Bits an, wie viele führende Bits einer Adresse zur Identifikation eines Netzwerks verwendet werden, etwa 192.0.2.0/24, wobei die 24 die Präfixlänge ist.

Siehe auch: Präfix, Trie, IP-Präfix, Prefix-Operationen.