Algorithmen & Datenstrukturen mit Java: Patricia-Bäume

Patricia-Baum	Radix Tree, (Compact) Prefix Tree

Ziel	Effiziente Implementierung für Mengen und Verzeichnisse mit Zeichenketten über einem Alphabet A als Schlüssel.

O(1)	Die Laufzeit für das Suchen und Einfügen ist ∈ O(1) bezüglich der Anzahl der Elemente in einer Menge/Map
	Die Laufzeit hängt nur noch von der Länge (Anzahl Zeichen im Schlüssel) ab.
Präfix-Suche	Diese Datenstruktur ist sehr gut geeignet für eine Präfixsuche
	Berechnung aller Schlüssel(-Wert-Paare) für ein Wort
Alphabet	endliche, nicht leere Menge von Zeichen
	Unicode, ASCII, {0,1}, ...

Datenstruktur	Baumstruktur (also wieder rekursiv)
Knoten	es gibt innere Knoten und Blätter
Blatt	besteht aus dem Schlüssel k und dem zugeordneten Wert v
	Optimierung: Der Schlüssel k muss nicht zwingend explizit im Blatt gespeichert werden
innere Knoten	bestehen aus einer Tabelle von Nachfolgern
	ein Nachfolger besteht aus einem Präfix p über dem Alphabet und einem Teilbaum t_p
	außerdem kann optional noch ein Schlüssel-Wert-Paar (k,v) in dem inneren Knoten enthalten sein
leerer Baum	Der leere Baum wird durch einen Spezialwert (Empty) dargestellt. Nur die Wurzel eines Baumes kann diesen Wert enthalten.

Invariante
.1	Alle inneren Knoten besitzen mindestens einen Nachfolger
.2	Alle inneren Knoten, an denen kein Wert gespeichert ist, besitzen mindestens zwei Nachfolger Diese Einschränkung gilt nicht für die Wurzel.
.3	Alle Nachfolger-Wörter (Präfixe) bestehen mindestens aus einem Zeichen
.4	Es gibt keine zwei Nachfolger-Wörter, die mit dem gleichen Zeichen beginnen

Klassenstruktur (Skizze)	public abstract class PatriciaTree implements Map { ... static class Empty extends PatriciaTree { ... } static class Leaf extends PatriciaTree { String k; Value v; ... } static class Node extends PatriciaTree { SubTreeMap st; Leaf mark; // null: not there ... } static class SubTreeMap { java.util.Map<String,PatriciaTree> trees; ... } // or something more specialized, e.g. static class SubTreeMap { String [] prefixes; PatriciaTree [] subtrees; // same length as prefixes ... } }

Suchen	eines Schlüssels k in einem Baum t
.1	wenn k = "" und t ein Blatt mit einem v oder ein innerer Knoten mit Zusatzinformation v ist, dann ist die Suche erfolgreich und v ist das Resultat
.2	wenn k = "x..." und t ein innerer Knoten ist und es unter den Nachfolgern ein p gibt, der ein echter Präfix von k ist, dann wird mit dem p zugeordneten Teilbaum t_p und dem um p verkürztem Schlüssel k_p die Suche fortgesetzt.
.3	in allen anderen Fällen ist die Suche gescheitert
	In .2 gibt es wegen Invariante .4 höchstens einen Nachfolger-Baum mit der Präfix-Eigenschaft

Einfügen	eines Schlüssel(-Wert-Paare)s (k,v) in einen Baum t
	Der Baum wird wie bei der Suche auf einem Pfad besucht
.0	wird der Schlüssel k im Baum t gefunden, so wird der Wert im Baum an dieser Stelle mit v überschrieben
.1	sei t₁ der innerer Knoten, an dem die Suche scheitert und k_i der während der Suche aus k schrittweise verkürzte Schlüssel
.a	ist k_i = "", so wird das Paar (k, v) im Knoten t₁ als Zusatzinformation gespeichert
.b	sei k_i = "x..." und x kommt nicht als 1. Zeichen in den Nachfolger-Wörtern von t₁ vor, so wird (k_i = "", l) in die Nachfolger-Menge von t₁ aufgenommem, wobei l ein Blatt bestehend aus (k,v) ist
.c	sei k_j mit k_j = "x..." das Nachfolger-Wort mit dem gleichen Anfangszeichen, so wird der längste gemeinsame Präfix p_ij von k_i und k_j berechnet und ein neuer innerer Knoten t_ij mit p_ij als Nachfolger-Wort eingefügt. Der neue Baum t_ij hat als Teilbäume den alten Nachfolger-Baum und ein neues Blatt für (k,v). Als Präfixe für diese Bäume werden die Reste bezüglich p_ij genommen.

Laufzeitanalyse
Suchen
.1	läuft in konstanter Zeit
.2	Sei n die Anzahl der Zeichen im Alphabet.
	Da ein innerer Knoten höchstens n Nachfolger besitzt und für die Suche nach dem Nachfolger mit gemeinsamem Präfix nur das 1. Zeichen verglichen werden muss, ist die Suche in der Zeit beschränkt.
	Für die Berechnung des längsten Präfixes müssen die Folgezeichen nur einmal verglichen werden, also pro Zeichen wieder eine beschränkte Zeit.
Rekursion	Der Prozess des Suchens wird maximal m mal wiederholt mit m = Länge von k.
	Die Suchzeit ist bezüglich der Länge der Schlüssel in O(m).
	Die Suchzeit hängt nicht von der Anzahl der Einträge in der Menge/Map ab. Grund dafür ist die endliche Anzahl von Zeichen in A.

Einfügen	Die Argumentation für die Suche kann 1-1 übertragen werden.
.1a und .1b	Die Arbeit für das Einfügen an dem Knoten, an dem die Suche scheitert, enthält keinerlei Wiederholungen, sondern besteht aus einer Sequenz von elementaren Operationen.
	Beim Einfügen wird höchstens ein neuer Knoten erzeugt.
	Gleiche Laufzeitabschätzungen wie bei der Suche.

Alphabet	{0,1}
Konsequenzen
.1	maximal 2 Nachfolger, binäre Suche
	Struktur der inneren Knoten wird stark vereinfacht
	Platzbedarf für die inneren Knoten wird verringert
.2	Innere Knoten mit nur einem Nachfolger besitzen immer einen zusätzlichen (k,v)-Wert
Konsequenzen	Werden die an den inneren Knoten gespeicherten Werte in extra Objekte ausgelagert, kann die Struktur weiter vereinfacht werden, da dann alle Verzeigungen immer binär sind.
	Struktur der inneren Knoten wird stark vereinfacht
	Platzbedarf für die inneren Knoten wird verringert
?	Praxisrelevant

Klassenstruktur (Skizze)	public abstract class BinPatriciaTree implements Map { // boring case for empty tree static class Empty extends BinPatriciaTree { ... } static class Leaf extends BinPatriciaTree { String k; Value v; ... } static class Mark extends BinPatriciaTree { Leaf mark; BitString prefix; BinPatriciaTree subTree; ... } static class Fork extends BinPatriciaTree { BinPatriciaTree l; BinPatriciaTree r BitString prefix; ... } static class BitString { boolean [] theBits; ... } }

Patricia-Bäume

1. Spezialfall

2. Spezialfall