Robert Sedgewick: Algorithmen

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


17. Digitales Suchen



Patricia

Das Suchverfahren mit digitalen Tries in der oben dargelegten Form hat zwei Unzulänglichkeiten: Das »Einweg-Verzweigen« führt zur Erzeugung von zusätzlichen Knoten im Baum, und es gibt zwei verschiedene Typen von Knoten im Baum, wodurch sich das Programm etwas kompliziert (besonders der Teil für das Einfügen). D. R. Morrison entdeckte einen Weg, wie diese beiden Probleme mit Hilfe einer Methode, die er Patricia nannte (»Practical Algorithm To Retrieve Information Coded In Alphanumeric«, praktischer Algorithmus zum Wiederauffinden von alphanumerisch kodierter Information), umgangen werden können. Der nachfolgend angegebene Algorithmus ist nicht exakt in der gleichen Form dargestellt wie bei Morrison, da diesen Anwendungen beim »Suchen in Zeichenfolgen« des Typs, den wir in Kapitel 19 kennenlernen werden, interessierten. Die hier untersuchten Fragen betreffend gestattet Patricia die Suche nach N beliebig langen Schlüsseln in einem Baum mit nur N Knoten, erfordert jedoch nur einen vollständigen Schlüsselvergleich pro Suche.

Einweg-Verzweigungen werden durch eine einfache Maßnahme vermieden: Jeder Knoten enthält den Index des Bits, das zu testen ist, um zu entscheiden, welcher Pfad von diesem Knoten aus zu benutzen ist. Äußere Knoten werden vermieden, indem Verkettungen zu äußeren Knoten durch Verkettungen ersetzt werden, die im Baum nach oben zeigen, zurück zu unserem normalen Baumknotentyp mit einem Schlüssel und zwei Verkettungen. Bei Patricia werden die Schlüssel in den Knoten jedoch auf dem Weg im Baum nach unten nicht benutzt, um die Suche zu steuern; sie werden erst dann betrachtet, wenn die unterste Ebene des Baumes erreicht wurde. Um zu sehen, wie Patricia abläuft, betrachten wir zunächst, wie das Verfahren an einem typischen Baum abläuft, und untersuchen dann, wie der Baum anfangs erzeugt wird. Der Patricia-Baum, den die Abbildung 17.8 zeigt, wird erzeugt, wenn unsere Beispielschlüssel nacheinander eingefügt werden.

Abbildung 17.8
Abbildung 17.8 Ein Patricia-Baum.

Um in diesem Baum zu suchen, beginnen wir bei der Wurzel und bewegen uns im Baum abwärts, wobei wir den Bitindex in jedem Knoten benutzen, um festzustellen, welches Bit im Suchschlüssel zu untersuchen ist; wir wenden uns nach rechts, wenn dieses Bit 1 ist, und nach links, wenn es 0 ist. Die Schlüssel in den Knoten werden auf dem Weg im Baum abwärts überhaupt nicht betrachtet. Schließlich wird eine aufwärts zeigende Verkettung vorgefunden: jede aufwärts zeigende Verkettung zeigt auf den eindeutigen Schlüssel im Baum, welcher das Bitmuster hat, das dafür sorgen würde, daß bei einer Suche diese Verkettung genommen wird. Zum Beispiel ist S der einzige Schlüssel im Baum, der mit dem Bitmuster 10*11 zur Übereinstimmung gebracht werden kann. Somit ist die Suche erfolgreich, wenn der Schlüssel bei dem Knoten, auf den die erste vorgefundene aufwärts zeigende Verkettung zeigt, gleich dem Suchschlüssel ist; andernfalls ist sie erfolglos. Bei Tries enden alle Suchvorgänge bei äußeren Knoten, woraufhin ein vollständiger Schlüsselvergleich vorgenommen wird, um zu bestimmen, ob die Suche erfolgreich war oder nicht; bei Patricia enden alle Suchvorgänge bei aufwärts gerichteten Verkettungen, woraufhin ein vollständiger Schlüsselvergleich durchgeführt wird, um zu bestimmen, ob die Suche erfolgreich war oder nicht. Außerdem ist es leicht zu testen, ob eine Verkettung nach oben zeigt, da die Bitindizes in den Knoten (per Definition) kleiner werden, wenn wir uns im Baum abwärts bewegen. Dies führt zu dem folgenden Suchprogramm für Patricia, das ebenso einfach ist wie das Programm für das Suchen mit digitalen Bäumen oder Tries:

    type link=^node;
         node=record key,info,b: integer; l,r: link end;
    var head,z: link;
    function patriciasearch(v: integer; x: link): link;
      var p: link;
      begin
      repeat
        p:=x;
        if bits(v,x^.b,1)=0 then x:=x^.l else x:=x^.r;
      until p^.b<=x^.b;
      patriciasearch:=x
      end;

Diese Funktion gibt eine Verkettung zu dem eindeutig bestimmten Knoten zurück, der den Datensatz mit dem Schlüssel v enthalten könnte. Die aufrufende Routine kann anschließend testen, ob die Suche erfolgreich war oder nicht. Demzufolge müssen wir, um in dem obigen Baum nach Z=11010 zu suchen, zunächst nach rechts und dann bei der rechten Verkettung von X nach oben gehen. Der dort befindliche Schlüssel ist nicht Z, somit ist die Suche erfolglos.

Abbildung 17.9 zeigt das Ergebnis des Einfügens von Z=11010 in den Patricia-Baum in Abbildung 17.8. Wie oben beschrieben, endet die Suche nach Z bei dem Knoten, der X=11000 enthält. Gemäß der den Baum definierenden Eigenschaft ist X der einzige Schlüssel im Baum, für den eine Suche bei diesem Knoten enden würde. Wenn Z eingefügt wird, würden zwei derartige Knoten existieren; daher muß die nach oben zeigende Verkettung, die auf den X enthaltenden Knoten zeigt, dahingehend geändert werden, daß sie auf einen neuen, Z enthaltenden Knoten zeigt. Dieser neue Knoten erhält dann einen Bitindex, der der am weitesten links befindlichen Stelle entspricht, in der sich X und Z unterscheiden. Außerdem erhält er zwei nach oben führende Verkettungen: eine, die auf X zeigt, und eine andere, die auf Z zeigt. Dies entspricht exakt dem Ersetzen des X enthaltenden äußeren Knotens durch einen neuen inneren Knoten (mit X und Z als Nachfolger) beim Einfügen in digitale Tries. Dabei wurde die Einweg-Verzweigung beseitigt, indem der Bitindex eingeführt wurde.

Abbildung 17.9
Abbildung 17.9 Äußeres Einfügen in einen Patricia-Baum.

Das Einfügen von T=10100 veranschaulicht einen komplizierteren Fall, wie Abbildung 17.10 zeigt. Die Suche nach T endet bei P=10000, was besagt, daß P der einzige Schlüssel im Baum mit dem Bitmuster 10 * 0 * ist. Nun unterscheiden sich T und P in Bit 2, einer Position, die während der Suche übersprungen wurde. Die Forderung, daß die Bitindizes fallen müssen, wenn wir uns im Baum abwärts bewegen, macht es notwendig, T zwischen X und P einzufügen, mit einem nach oben auf T selbst gerichteten Zeiger, der seinem eigenen Bit 2 entspricht. Man beachte, daß die Tatsache, daß Bit 2 vor dem Einfügen von T übersprungen wurde, impliziert, daß P und R den gleichen Wert von Bit 2 besitzen.

Abbildung 17.10
Abbildung 17.10 Inneres Einfügen in einen Patricia-Baum.

Diese Beispiele illustrieren die beiden einzigen Fälle, die für Patricia beim Einfügen auftreten. Die folgende Implementation enthält alle Details:

    function patriciainsert(v: integer; x: link): link;
      label 0;
      var t,p: link; i: integer;
      begin
      t:=patriciasearch(v,x);
      if v=t^.key then goto 0;
      i:=maxb;
      while bits(v,i,1)=bits(t^.key,i,1) do i:=i-1;
      repeat
        p:=x;
        if bits(v,x^.b,1)=0 then x:=x^.l else x:=x^.r;
      until (x^.b<=i) or (p^.b<=x^.b);
      new(t); t^.key:=v; t^.b:=i;
      if bits(v,t^.b,1)=0
        then begin t^.l:=t; t^.r:=x end
        else begin t^.r:=t; t^.l:=x end
      if bits(v,p^.b,1)=0 then p^.l:=t else p^.r:=t;
   0: patriciainsert:=t
      end;

(Bei diesem Programm wird vorausgesetzt, daß head mit dem Schlüsselfeld 0, einem Bitindex maxb und beiden Verkettungen als auf sich selbst zeigend initialisiert wurde.) Zuerst führen wir eine Suche durch, um den Schlüssel zu finden, der von v unterschieden werden muß. Die Bedingungen x^.b<=i und p^.b<=x^.b charakterisieren die Situationen, die in den Abbildungen 17.10 bzw. 17.9 dargestellt sind. Danach bestimmen wir die am weitesten links befindliche Bitposition, in der sich die Schlüssel unterscheiden, bewegen uns im Baum abwärts bis zu dem betreffenden Punkt und fügen an dieser Stelle einen neuen Knoten ein, der v enthält.

Patricia stellt die Quintessenz der digitalen Suchmethoden dar: Es gestattet, die Bits zu identifizieren, die die Suchschlüssel von anderen unterscheiden, und sie in eine Datenstruktur (ohne überflüssige Knoten) einzubauen, die schnell von einem beliebigen Suchschlüssel zu dem einzigen Schlüssel in der Datenstruktur führt, der gleich sein könnte. Natürlich kann die gleiche Technik, die bei Patricia verwendet wird, bei der Suche mit binären digitalen Tries benutzt werden, um Einweg-Verzweigungen zu beseitigen, doch hierdurch würde das Problem vieler Typen von Knoten noch mehr zugespitzt. Abbildung 17.11 zeigt den Patricia-Baum für die gleichen Schlüssel, die zur Erzeugung des Trie von Abbildung 17.6 verwendet wurden; dieser Baum hat nicht nur 44% weniger Knoten, sondern ist auch sehr gut ausgeglichen.

Abbildung 17.11
Abbildung 17.11 Ein umfangreicher Patricia-Baum.

Im Unterschied zu der standardmäßigen Suche in einem Binärbaum sind die digitalen Methoden unempfindlich gegenüber der Reihenfolge, in der Schlüssel eingefügt werden; sie hängen nur von der Struktur der Schlüssel selbst ab. Bei Patricia hängt die Anordnung der aufwärts zeigenden Verkettungen von der Reihenfolge des Einfügens ab, doch die Baumstruktur hängt wie bei den anderen Methoden nur von den Bits in den Schlüsseln ab. Demzufolge würde selbst Patricia mit einer Schlüsselmenge der Art 001, 0001, 00001, 000001 usw. Probleme haben, doch für normale Schlüssel dürfte der Baum relativ gut ausgeglichen sein, so daß die Anzahl der Untersuchungen von Bits selbst für sehr lange Schlüssel annähernd proportional zu lg N ist, wenn N Knoten im Baum enthalten sind.

Eigenschaft 17.4 Ein Patricia-Trie, der aus N zufälligen Schlüsseln mit b Bits erzeugt wurde, hat N Knoten und erfordert für eine durchschnittliche Suche lg N Bitvergleiche.

Wie bei den anderen Methoden in diesem Kapitel ist die Analyse des durchschnittlichen Falles recht kompliziert; es erweist sich, daß Patricia im Durchschnitt einen Vergleich weniger erfordert als ein gewöhnlicher Trie. w.z.b.w.

Das nützlichste Merkmal der Suche mit digitalen Tries besteht darin, daß sie bei Schlüsseln mit variabler Länge effizient ausgeführt werden kann. Bei allen anderen Suchmethoden, die wir kennengelernt haben, ist die Länge der Schlüssel in irgendeiner Weise in die Suchprozedur »eingebaut«, so daß die Laufzeit ebenso von der Länge wie von der Zahl der Schlüssel abhängt. Die tatsächlich realisierbaren Einsparungen hängen von der verwendeten Methode des Zugriffs auf die Bits ab. Nehmen wir zum Beispiel an, daß wir einen Computer haben, der effizient auf aus 8 Bits bestehenden »Bytes« von Daten zugreifen kann, und daß wir unter Hunderten von aus 1000 Bits bestehenden Schlüsseln zu suchen haben. Dann würde Patricia für die Suche nur den Zugriff auf etwa 9 oder 10 Bytes des Suchschlüssels erfordern, sowie einen 125 Bytes betreffenden Vergleich auf Gleichheit, während Hashing den Zugriff auf alle 125 Bytes des Suchschlüssels für die Berechnung der Hash-Funktion sowie einige Vergleiche auf Gleichheit erfordern würde. Auf Vergleichen basierende Verfahren würden gleich mehrere lange Vergleiche erfordern. Diese Tatsache macht Patricia (oder das Suchen mit digitalen Tries mit beseitigter Einweg-Verzweigung) zur bevorzugten Suchmethode, wenn sehr lange Schlüssel auftreten.


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