Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


17. Digitales Suchen



Digitale Such-Tries

Sehr oft liegt der Fall vor, daß Suchschlüssel sehr lang sind, vielleicht zwanzig Zeichen oder mehr. In einer solchen Situation können die Kosten, die beim Vergleich eines Suchschlüssels hinsichtlich der Gleichheit mit einem Schlüssel aus der Datenstruktur entstehen, zu dominierenden Kosten werden, die nicht vernachlässigt werden können. Bei der Suche mit Hilfe digitaler Bäume wird ein solcher Vergleich bei jedem Knoten des Baumes vorgenommen; im vorliegenden Abschnitt werden wir sehen, daß es in den meisten Fällen möglich ist, mit nur einem Vergleich pro Suche auszukommen.

Die Idee besteht darin, die Schlüssel überhaupt nicht in Knoten des Baumes zu speichern, sondern stattdessen alle Schlüssel in äußeren Knoten des Baumes anzuordnen. Das heißt, anstatt für äußere Knoten der Struktur z zu verwenden, sehen wir Knoten vor, die die Suchschlüssel enthalten. Demzufolge haben wir zwei Typen von Knoten: innere Knoten, die nur Verkettungen zu anderen Knoten enthalten, und äußere Knoten, die Schlüssel und keine Verkettungen enthalten. (Fredkin nannte diese Methode »trie«, da sie für das Wiederauffinden (retrieval) von Nutzen ist; in der Umgangssprache wird dieses Wort gewöhnlich »try-ee« ausgesprochen, oder - aus offensichtlichen Gründen - nur »try« (Versuch, Experiment).) Um in einer solchen Struktur nach einem Schlüssel zu suchen, zweigen wir einfach entsprechend seinen Bits ab, vergleichen ihn jedoch mit nichts, bis wir zu einem äußeren Knoten gelangen. Jeder Schlüssel im Baum wird in einem äußeren Knoten des Pfads gespeichert, der von dem führenden Bitmuster des Schlüssels beschrieben wird, und jeder Suchschlüssel gelangt zu einem äußeren Knoten, so daß ein vollständiger Vergleich der Schlüssel die Suche beendet.

Abbildung 17.4 zeigt den (binären) digitalen Such-Trie für die Schlüssel A S E R C. Um zum Beispiel E zu erreichen, gehen wir von der Wurzel aus nach links, nach links und nach rechts, da die ersten drei Bits von E 001 lauten. Keiner der Schlüssel in dem Trie beginnt mit den Bits 101, da man einen leeren äußeren Knoten vorfindet, wenn man nach rechts, nach links und nach rechts geht. Bevor wir über das Einfügen nachdenken, sollte sich der Leser die recht überraschende Eigenschaft klarmachen, daß die Struktur des Trie unabhängig von der Reihenfolge ist, in der die Schlüssel eingefügt werden: Für jede gegebene Menge von unterschiedlichen Schlüsseln existiert ein eindeutiger Trie.

Abbildung 17.4
Abbildung 17.4 Ein digitaler Such-Trie.

Wie gewöhnlich können wir nach einer erfolglosen Suche den gesuchten Schlüssel einfügen, indem wir den äußeren Knoten, bei dem die Suche endete, ersetzen, vorausgesetzt, daß er keinen Schlüssel enthält. Dies ist der Fall, wenn H in den Trie in Abbildung 17.4 eingefügt wird, wie es der erste Trie in Abbildung 17.5 zeigt. Falls der äußere Knoten, bei dem die Suche endet, einen Schlüssel enthält, so muß er durch einen inneren Knoten ersetzt werden, unter dem der gesuchte Schlüssel und der Schlüssel, der die Suche beendete, in äußeren Knoten angeordnet werden. Falls diese Schlüssel in weiteren Bitpositionen übereinstimmen, so ist es leider erforderlich, einige äußere Knoten hinzuzufügen, die keinem Schlüssel im Baum entsprechen (oder anders gesagt, einige innere Knoten mit einem leeren äußeren Knoten als Nachfolger). Dieser Fall tritt ein, wenn I eingefügt wird, wie es der zweite Trie in Abbildung 17.5 zeigt. Der Rest von Abbildung 17.5 zeigt die Vervollständigung unseres Beispiels, wenn die Schlüssel N G X M P L hinzugefügt werden.

Abbildung 17.5
Abbildung 17.5 Erzeugung eines digitalen Such-Trie.

Die Implementation dieses Verfahrens in Pascal ist tatsächlich relativ kompliziert, da zwei Typen von Knoten notwendig sind, wobei Verkettungen in inneren Knoten auf Knoten beider Typen zeigen könnten. Dies ist ein Beispiel eines Algorithmus, für den eine Implementation auf niedriger Ebene einfacher sein könnte als eine Implementation auf hoher Ebene. Wir verzichten auf das zugehörige Programm, da wir im folgenden eine Verbesserung kennenlernen, bei der dieses Problem umgangen wird.

Der linke Unterbaum eines binären digitalen Such-Trie enthält alle Schlüssel, die als führendes Bit 0 haben; der rechte Unterbaum enthält alle Schlüssel, die 1 als führendes Bit haben. Dies führt zu einer unmittelbaren Entsprechung zum digitalen Sortieren: Bei der Suche mit binären Tries wird die Datei in genau der gleichen Weise zerlegt wie bei Radix Exchange Sort. (Man vergleiche den obigen Trie mit Abbildung 10.1, dem Zerlegungsdiagramm für Radix Exchange Sort, wenn man davon absieht, daß die Schlüssel sich leicht unterscheiden.) Diese Entsprechung ist analog zu der Entsprechung zwischen der Suche in einem Binärbaum und Quicksort.

Eigenschaft 17.2 Ein Suchen oder Einfügen in einem digitalen Such-Trie erfordert ungefähr lg N Bitvergleiche für eine durchschnittliche Suche und b Bitvergleiche im ungünstigsten Fall, wenn der Baum aus N zufälligen Schlüsseln mit b Bits erzeugt wurde.

Wie oben ergibt sich das Ergebnis für den ungünstigsten Fall unmittelbar aus dem Algorithmus, und das Ergebnis für den durchschnittlichen Fall erfordert eine mathematische Analyse, die über den Rahmen dieses Buches hinausgeht, obwohl es der sehr einfachen intuitiven Überlegung entspricht, daß jedes untersuchte Bit mit gleicher Wahrscheinlichkeit 0 oder 1 sein kann, so daß auf die beiden Seiten eines jeden Knotens im Trie jeweils ungefähr die Hälfte der Schlüssel entfallen müßte. w.z.b.w.

Eine störende Eigenschaft von digitalen Tries, welche sie von den anderen Typen von Suchbäumen, die wir betrachtet haben, unterscheidet, ist die »Einweg«-Verzweigung, die für Schlüssel erforderlich ist, die eine große Anzahl Bits gemeinsam haben. Zum Beispiel erfordern Schlüssel, die sich nur im letzten Bit unterscheiden, einen Pfad, dessen Länge gleich der Länge des Schlüssels ist, gleichgültig, wie viele Schlüssel im Baum vorhanden sind. Die Zahl der inneren Knoten kann um einiges größer sein als die Zahl der Schlüssel.

Eigenschaft 17.3 Ein digitaler Such-Trie, der aus N zufälligen Schlüsseln mit b Bits erzeugt wurde, besitzt im Durchschnitt ungefähr N/ln 2 rund 1,44N Knoten.

Der Beweis dieses Ergebnisses würde wiederum über den Rahmen dieses Buches hinausgehen, obwohl es sich leicht empirisch nachprüfen läßt. Abbildung 17.6 zeigt einen Trie, der aus 95 zufälligen Schlüsseln mit 10 Bits erzeugt wurde und 131 Knoten besitzt. w.z.b.w.

Abbildung 17.6
Abbildung 17.6 Ein umfangreicher digitaler Such-Trie.

Die Höhe von Tries ist zwar durch die Anzahl von Bits in den Schlüsseln begrenzt, doch wäre es wünschenswert, die Möglichkeiten zur Verarbeitung von Datensätzen mit sehr langen Schlüsseln (zum Beispiel 1000 Bits oder mehr) zu betrachten. Die Schlüssel könnten eventuell eine gewisse Einheitlichkeit aufweisen, wie dies bei Daten der Fall sein könnte, die kodierten Text darstellen. Ein Weg, um die Pfade in den Bäumen zu verkürzen, besteht in der Verwendung von deutlich mehr als zwei Verkettungen pro Knoten (obwohl sich dadurch das »Platz«-Problem infolge der Verwendung zu vieler Knoten zuspitzt); ein anderer Weg ist das »Verkürzen« von Pfaden, die Einweg-Abzweigungen zu einzelnen Verkettungen enthalten. Wir untersuchen diese Methoden in den folgenden beiden Abschnitten.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]