Transcript
Page 1: Digitales Suchen / Digitale Suchbäume

G.Heyer Algorithmen und Datenstrukturen II1

Digitales Suchen / Digitale Suchbäume

Verschiedene Suchverfahren laufen in der Weise ab, dass sie die Suchschlüssel bitweise untersuchen, anstatt in jedem Schritt vollständige Vergleiche zwischen Schlüsseln durchzuführen.Diese Methoden, die digitale Suchverfahren (radix-searching methods) genannt werden, arbeiten mit den Bits der Schlüssel selbst, im Gegensatz zu der transformierten Variante der Schlüssel, die beim Hashing verwendet wird.

Ebenso wie im Falle der digitalen Sortierverfahren gilt, dass diese Methoden von Nutzen sein können, wenn die Bits der Suchschlüssel leicht zugänglich und die Werte der Suchschlüssel gut verteilt sind.

Page 2: Digitales Suchen / Digitale Suchbäume

G.Heyer Algorithmen und Datenstrukturen II2

Die Hauptvorteile sind, dass

• sie ohne Komplikationen, die bei ausgeglichenen Bäumen auftreten, ein annehmbares Verhalten im ungünstigsten Fall gewährleisten,

• sie einen einfachen Weg zur Behandlung von Schlüsseln mit variabler Länge bieten,

• einige von ihnen Einsparungen von Speicherplatz ermöglichen, indem sie einen Teil des Schlüssels innerhalb der Suchstruktur speichern und dass

• sie einen sehr schnellen Zugriff auf die Daten realisieren können, der sowohl mit binären Suchbäumen als auch mit Hashing vergleichbar ist.

Page 3: Digitales Suchen / Digitale Suchbäume

G.Heyer Algorithmen und Datenstrukturen II3

Die Nachteile sind, dass

• Daten mit einer gewissen Systematik zu entarteten Bäumen mit schlechtem Verhalten führen können und

• dass einige der Verfahren den Platz sehr ineffizient ausnutzen.

Wie die digitalen Sortierverfahren sind auch diese Methoden dazu bestimmt, spezielle Eigenschaften der Architektur eines Computers auszunutzen.

Page 4: Digitales Suchen / Digitale Suchbäume

G.Heyer Algorithmen und Datenstrukturen II4

Digitale SuchbäumeDas einfachste digitale Suchverfahren ist die Suche mit digitalen Bäumen; der Algorithmus ist genau der gleiche wie der für die Suche in einem Binärbaum, mit dem Unterschied, dass in dem Baum nicht entsprechend dem Ergebnis des Vergleiches zwischen den Schlüsseln verzweigt wird, sondern entsprechend den Bits des Schlüssels.

Auf der ersten Ebene wird das führende Bit benutzt, auf der zweiten Ebene das zweite führende Bit usw., bis ein äußerer Knoten vorgefunden wird.

Das Programm hierfür ist praktisch das gleiche wie für die Suche in einem Binärbaum. Der einzige Unterschied ist, dass die Vergleiche der Schlüssel durch Aufrufe der Funktion bits ersetzt werden, die beim digitalen Sortieren verwendet wurde.

Page 5: Digitales Suchen / Digitale Suchbäume

G.Heyer Algorithmen und Datenstrukturen II5

unsigned bits ( unsigned x, int k, int j ){ return (x >> k ) & ~ (~ 0 << j) ; } j sind Bits, die k Stellen von rechts in x erscheinen.Die Funktion kann in Maschinensprache effizient implementiert werden, indem um k Bits nach rechts geschoben wird und dann alle Bits außer den rechts befindlichen j Bits auf 0 gesetzt werden.

int digitalsearch ( int v) {

struct node *x = head;int b = maxb;z -> key = v ;while ( v != x -> key) x = ( bits (v, b--,1)) ? x -> r : x -> l ;return x -> info;

}

Page 6: Digitales Suchen / Digitale Suchbäume

G.Heyer Algorithmen und Datenstrukturen II6

Datenstruktur:die gleiche wie die für elementare binäre Suchbäume

Die Konstante maxb ist die Anzahl der Bits in den Schlüsseln, die zu sortieren sind. Für das Programm wird angenommen, dass das erste Bit in jedem Schlüssel ( das (maxb + 1) -te von rechts) 0 ist, so dass die Suche bei head beginnt, welches eine Verkettung ist, die auf den Kopfknoten eines Baumes mit dem Schlüssel 0 und mit einer auf den Suchbaum zeigenden linken Verkettung zeigt.

Daher ist die Prozedur zur Initialisierung für dieses Programm die gleiche wie für die Suche in einem Binärbaum, abgesehen davon, dass man mit

head -> l = z anstatt mit head -> r = z beginnt.

Hier wird vorausgesetzt, dass alle Schlüssel, die in der Datenstruktur auftreten, unterschiedlich sind.

Page 7: Digitales Suchen / Digitale Suchbäume

G.Heyer Algorithmen und Datenstrukturen II7

Annahme: der i-te Buchstabe des Alphabets wird durch die aus fünf Bits bestehende Binärdarstellung von i repräsentiert.

Um Konsistenz mit bits zu erreichen, betrachten wir die Bits von rechts nach links mit 0 bis 4 durchnumeriert.

( demnach ist Bit 0 das einzige von 0 verschiedene Bit von A, und Bit 4 ist das einzige von 0 verschiedene Bit von P)

A 0 0 0 0 1S 1 0 0 1 1E 0 0 1 0 1R 1 0 0 1 0C 0 0 0 1 1H 0 1 0 0 0 I 0 1 0 0 1N 0 1 1 1 0G 0 0 1 1 1X 1 1 0 0 0M 0 1 1 0 1P 1 0 0 0 0L 0 1 1 0 0

Page 8: Digitales Suchen / Digitale Suchbäume

G.Heyer Algorithmen und Datenstrukturen II8

Ein digitaler Suchbaum

A

S

X

L

M

NI

H

G

C

E

P

R

0

0 1

0

1

1

1

0

0 0

0

1

11

1

1

1

0

0

0

1

10 10

0

Page 9: Digitales Suchen / Digitale Suchbäume

G.Heyer Algorithmen und Datenstrukturen II9

Prozedur für das Einfügen in digitale Suchbäumedigitalinsert (int v, int info )

{struct node *p, *x = head;int b = maxb;while (x != z ) {

p = x ;x = ( bits ( v, b--, 1 )) ? x--> r : x --> l ;

}x = (struct node *) malloc (sizeof *x);x --> key = v ; x --> info = info ; x --> l = z ; x --> r = z ;if ( bits ( v, b+1, 1 ) ) p --> r = x ; else p --> l = x;

}

Page 10: Digitales Suchen / Digitale Suchbäume

G.Heyer Algorithmen und Datenstrukturen II10

Beispiel: Einfügen eines neuen Knotens,wenn der Schlüssel Z = 11010 zu dem Baum hinzugefügt wird.

Durchlaufen des digitalen Suchbaums:

• zweimal nach rechts wenden, da die beiden führenden Bits

von Z 1 sind,

• dann nach links, wo der äußere Knoten links von X liegt, wo Z eingefügt wird.

Der ungünstigste Fall für Bäume, die mit digitaler Suche erzeugt werden, ist viel besser als für binäre Suchbäume, wenn die Anzahl der Schlüssel groß ist und die Schlüssel nicht lang sind. Die Länge des längsten Pfades in einem digitalen Suchbaum ist gleich der längsten Übereinstimmung in den führenden Bits zwischen zwei beliebigen Schlüsseln im Baum, und diese ist für viele Anwendungen meist relativ klein (z. B. wenn die Schlüssel aus zufälligen Bits bestehen ).

Page 11: Digitales Suchen / Digitale Suchbäume

G.Heyer Algorithmen und Datenstrukturen II11

Eigenschaften eines digitalen Suchbaumes:Ein Suchen oder Einfügen in einem digitalen Suchbaum erfordert durchschnittlich ungefähr lg N Vergleiche und im ungünstigsten Fall b Vergleiche, wenn der Baum aus N zufälligen Schlüsseln mit b Bits erzeugt wurde.

Es ist offensichtlich, dass kein Pfad jemals länger sein kann als die Anzahl der Bits in den Schlüsseln; z. B. kann ein digitaler Suchbaum, der aus Schlüsseln mit acht Zeichen erzeugt wurde, mit beispielsweise sechs Bits pro Zeichen, keinen Pfad besitzen, der länger als 48 ist, selbst wenn es Hunderttausende von Schlüsseln gibt. Aus einer Analyse geht hervor, dass digitale Suchbäume nahezu ausgeglichen sind, da das „nächste“ Bit eines zufälligen Schlüssels mit der gleichen Wahrscheinlichkeit 0 oder 1 sein kann, so dass auf beide Seiten eines jeden Knotens jeweils die Hälfte entfällt.

Page 12: Digitales Suchen / Digitale Suchbäume

G.Heyer Algorithmen und Datenstrukturen II12

Digitale Such-TriesSehr oft liegt der Fall vor, dass 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.

Ziel: Verringerung der Vergleiche

Page 13: Digitales Suchen / Digitale Suchbäume

G.Heyer Algorithmen und Datenstrukturen II13

Neue Idee: die Schlüssel nicht im 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, sieht man Knoten vor, die die Suchschlüssel enthalten.

Es entstehen 2 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.)

Page 14: Digitales Suchen / Digitale Suchbäume

G.Heyer Algorithmen und Datenstrukturen II14

Suchen eines Schlüssels in einer solchen Struktur:Entsprechend seiner Bits abzweigen (aber kein Vergleich ) bis man an einen äußeren Knoten gelangt. 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 dass ein vollständiger Vergleich der Schlüssel die Suche beendet. Beispiel eines (binären) digitalen Such-Tries für die Schlüssel A S E R C

A CE

R S

Page 15: Digitales Suchen / Digitale Suchbäume

G.Heyer Algorithmen und Datenstrukturen II15

Interessante Eigenschaften eines digitalen Such-TrieDie Struktur des Trie ist unabhängig von der Reihenfolge, in der die Schlüssel eingefügt werden. Für jede gegebene Menge von unterschiedlichen Schlüsseln existiert ein eindeutiger Trie.

Für die Implementation dieses Verfahrens in C sind zwei Typen von Knoten erforderlich, wobei Verkettungen in inneren Knoten auf Knoten beider Typen zeigen können.

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. Diese Entsprechung ist analog zu der Entsprechung zwischen der Suche in einem Binärbaum und Quicksort.

Page 16: Digitales Suchen / Digitale Suchbäume

G.Heyer Algorithmen und Datenstrukturen II16

Weitere Eigenschaften von digitalen Such-TriesEin 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.

Eine störende Eigenschaft von digitalen Tries, welche sie von den anderen Typen von Suchbäumen 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.

Page 17: Digitales Suchen / Digitale Suchbäume

G.Heyer Algorithmen und Datenstrukturen II17

Ein digitaler Such-Trie, der aus N zufälligen Schlüsseln mit b Bits erzeugt wurde, besitzt im Durchschnitt ungefähr N/ln2 = 1,44 N Knoten.Beispiel: Ein Such-Trie, der aus 95 zufälligen Schlüsseln mit 10 Bits erzeugt wurde, besitzt 131 Knoten.

Ziel: 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öglichkeit zur Verarbeitung von Datensätzen mit sehr langen Schlüsseln (z. B. 1000 Bits oder mehr ) zu betrachten.

Die Schlüssel könnten evtl. 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 dadurch ein „Platz“-Problem infolge der Verwendung zu vieler Knoten entstehen kann; ein anderer Weg ist das „Verkürzen“ von Pfaden, die Einweg-Abzweigungen zu einzelnen Verkettungen enthalten.

Page 18: Digitales Suchen / Digitale Suchbäume

G.Heyer Algorithmen und Datenstrukturen II18

Digitales Mehrwege-SuchenBeim digitalen Sortieren stellte man fest, dass eine

beträchtliche Erhöhung der Geschwindigkeit erzielt wurde, wenn jedesmal mehr als ein Bit betrachtet wurde.

Dies gilt auch für die digitale Suche:

Indem jedesmal m Bits betrachtet werden, kann die Suche um den Faktor 2m beschleunigt werden. Es gibt jedoch ein Hindernis, das es erforderlich macht, bei der Anwendung dieser Idee vorsichtiger zu sein als beim digitalen Sortieren.

Das Problem besteht darin, dass die gleichzeitige Betrachtung von m Bits der Verwendung von Knoten mit M = 2 m Verkettungen in einem Baum entspricht, was zu einer beträchtlichen Menge von vergeudetem Platz für nicht benutzte Verkettungen führen kann.

Page 19: Digitales Suchen / Digitale Suchbäume

G.Heyer Algorithmen und Datenstrukturen II19

Beispiel:M = 4, für Beispielschlüssel wird folgender Trie erzeugt:

GECA

I LH M R

XN

S

P

Um in diesem Trie zu suchen, betrachte man jeweils zwei Bits im Schlüssel auf einmal:00 nehme man beim ersten Knoten die linke Verkettung,01 nehme man die zweite Verkettung,10 nehme man die dritte Verkettung,11 nehme man die vierte Verkettung.Danach verzweige man auf der nächsten Ebene entsprechend dem dritten und dem vierten Bit.

Page 20: Digitales Suchen / Digitale Suchbäume

G.Heyer Algorithmen und Datenstrukturen II20

Um z. B. in dem abgebildeten Trie nach T = 10100 zu suchen,nehme man von der Wurzel ausgehend, die dritte Verkettung

und danach die dritte Verkettung vom dritten Nachfolger der Wurzel, womit man zu einem äußeren Knoten gelangt, so dass die Suche erfolglos ist. Um T einzufügen, könnte dieser Knoten durch einen neuen Knoten ersetzt werden, der T (und vier äußere Verkettungen ) enthält.

Man erkennt, dass in diesem Baum aufgrund der großen Zahl nicht benutzter äußerer Verkettungen relativ viel Platz vergeudet wird.

Wenn M größer wird, spitzt sich dieser Effekt zu; es zeigt sich, dass die Anzahl der verwendeten Verkettungen für zufällige Schlüssel ungefähr MN / ln M beträgt.

Andererseits ist dies eine sehr effiziente Suchmethode:

Die Laufzeit beträgt ungefähr logM N .

Page 21: Digitales Suchen / Digitale Suchbäume

G.Heyer Algorithmen und Datenstrukturen II21

Ein sinnvoller Kompromiss zwischen der Zeiteffizienz von Mehrwege-Tries und der Platzeffizienz anderer Methoden kann gefunden werden, indem eine „Hybrid“-Methode mit einem großen Wert von M an der Spitze (z. B. auf den ersten beiden Ebenen) und einem kleinen Wert von M (oder irgendeiner elementaren Methode ) auf den unteren Ebenen angewandt wird.

Effiziente Implementationen derartiger Methoden können jedoch auch hier aufgrund mehrerer unterschiedlicher Typen von Knoten sehr kompliziert sein.

Beispielsweise teilt ein Baum mit zwei Ebenen mit je 32 Abzweigungen die Schlüssel in 1024 Kategorien ein, von denen jede in zwei Schritten im Baum abwärts erreicht werden kann. Dies wäre für Dateien mit Tausenden von Schlüsseln sehr zweckmäßig.

Page 22: Digitales Suchen / Digitale Suchbäume

G.Heyer Algorithmen und Datenstrukturen II22

Interessant ist, dass „Hybrid“-Suchmethoden der Art undWeise entsprechen, wie Menschen nach Dingen suchen, z. B. Namen in einem Telefonbuch.Der erste Schritt ist eine Mehrwege-Entscheidung („Nachsehen, das Wort beginnt mit ‚A‘ „), der vielleicht einige Zweiweg-Entscheidungen folgen --> „Andrews“ kommt nach „Aitken“, --> danach erfolgt sequentiellen Suche

„Algonquin“ ...“ Algren“ nein „Algorithmus“ steht nicht drin.

Natürlich dürften Computer eine Mehrwege-Suche um einiges besser als Menschen ausführen, so dass zwei Ebenen zweckmäßig sind. Weiterhin ist ein 26-Wege-Verzweigen (sogar mit noch mehr Ebenen) eine sehr sinnvolle Alternative, die für Schlüssel in Betracht gezogen werden sollte, die einfach aus Buchstaben bestehen (z. B. in einem Wörterbuch).

Page 23: Digitales Suchen / Digitale Suchbäume

G.Heyer Algorithmen und Datenstrukturen II23

PatriciaDas Suchverfahren mit digitalen Tries in der oben

dargestellten 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 des Einfügens).

D. R. Morrisson 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 nachfolgende Algorithmus ist nicht in der gleichen Form dargestellt wie bei Morrison.

Page 24: Digitales Suchen / Digitale Suchbäume

G.Heyer Algorithmen und Datenstrukturen II24

Hier werden Fragen untersucht, in denen mit Patricia die Suche nach N beliebig langen Schlüsseln in einem Baum mit nur N Knoten erfolgt. Das erfordert 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 zum 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.

Page 25: Digitales Suchen / Digitale Suchbäume

G.Heyer Algorithmen und Datenstrukturen II25

Ein Patricia-Baum

S

R

P

X

A

C

E

H

L

MI

N

G0

43

2

1

0

0

2

1

1

1 0

3

Page 26: Digitales Suchen / Digitale Suchbäume

G.Heyer Algorithmen und Datenstrukturen II26

Um in diesem Baum zu suchen, beginnt man bei der Wurzel und bewegt sich im Baum abwärts, wobei man den Bitindex in jedem Knoten benutzt, um festzustellen, welches Bit im Schlüssel zu unterstützen ist; man wendet sich nach rechts, wenn das 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, dass bei einer Suche diese Verkettung genommen wird.

Z. B. ist S der einzige Schlüssel im Baum, der mit dem Bitmuster 10*11 zur Übereinstimmung gebracht werden kann.

Page 27: Digitales Suchen / Digitale Suchbäume

G.Heyer Algorithmen und Datenstrukturen II27

Somit ist die Suche erfolgreich, wenn der Schlüssel bei demKnoten, 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 man sich im Baum abwärts bewegt.

Page 28: Digitales Suchen / Digitale Suchbäume

G.Heyer Algorithmen und Datenstrukturen II28

Suchprogramm für Patriciastatic struct node { int key, info, b ; struct node *l, *r ; } ;static struct node *head ;int patriciasearch ( int v ) { struct node *p, *x ;

p = head ; x = head --> l ;while (p --> b > x --> b )

{ p = x ;x = ( bits (v, x --> b, l)) ? x --> r : x --> l ;

}if ( v == x --> key) return x --> info ; else return -1 ;

}

Page 29: Digitales Suchen / Digitale Suchbäume

G.Heyer Algorithmen und Datenstrukturen II29

Diese Funktion realisiert das Auffinden des eindeutigbestimmten Knotens, der den Datensatz mit dem Schlüssel v enthalten könnte, und testet anschließend, ob die Suche tatsächlich erfolgreich ist.

Demzufolge muss man, 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.

In der nachfolgenden Abbildung wird das Ergebnis des Einfügens von Z = 11010 in den Patricia-Baum gezeigt.

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.

Page 30: Digitales Suchen / Digitale Suchbäume

G.Heyer Algorithmen und Datenstrukturen II30

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

S

R

P

X

A

C

E

H

L

MI

N

G0

43

2

1

0

0

2

1

1

1 0

3

Z1

Wenn Z eingefügt wird, würden zwei derartige Knoten existieren; daher muss die nach oben zeigende Verkettung, die auf den X enthaltenden Knoten zeigt, dahingehend geändert werden, dass sie auf einen neuen, Z enthaltenden Knoten zeigt.

Page 31: Digitales Suchen / Digitale Suchbäume

G.Heyer Algorithmen und Datenstrukturen II31

Das Einfügen von T = 10100 veranschaulicht einenkomplizierteren Fall.

Die Suche nach T endet bei P = 10000, was besagt, dass 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, dass die Bitindizes fallen müssen, wenn man sich im Baum abwärts bewegt, macht es notwendig, T zwischen X und P einzufügen, mit einem nach oben auf T selbst gerichteten Zeiger, der seinem eigenem Bit 2 entspricht.

Man beachte, dass die Tatsache, dass Bit 2 vor dem Einfügen von T übersprungen wurde, impliziert, dass P und R den gleichen Wert von Bit 2 besitzen.

Diese Beispiele illustrieren die beiden einzigen Fälle, die für Patricia beim Einfügen auftreten.

Page 32: Digitales Suchen / Digitale Suchbäume

G.Heyer Algorithmen und Datenstrukturen II32

Inneres Einfügen in einen Patricia-Baum

SX

A

C

E

H

L

MI

N

G0

43

2

1

0

0

2

1 1

R

P1

0

3

Z1

T2

Page 33: Digitales Suchen / Digitale Suchbäume

G.Heyer Algorithmen und Datenstrukturen II33

Implementation zum Einfügen in einen Patricia-Baumpatriciainsert ( int v, int info ){ struct node *p, *t, *x ;

int i = maxb ;p = head; t = head --> l ;while ( p --> b > t --> b ) { p = t ; t = (bits (v , t --> b, 1 )) ? t --> r : t --> l ; }if ( v == t --> key ) return ;while ( bits ( t --> key, i , 1) == bits (v, i , 1 )) i-- ;p = head ; x = head --> l; while ( p --> b > x -->b && x --> b > i ) { p = x ; x = ( bits ( v, x --> b, 1 ) ) ? x --> r : x --> l; }t = ( struct node * ) malloc (sizeof *t) ;t --> key = v ; t --> info = info ; t --> b = i ;t --> l = ( bits ( v , t --> b , 1 )) ? x : t ;t --> r = ( bits ( v, t --> b , 1 )) ? t : x ;if ( bits (v , p --> b , 1 )) p --> r = t ; else p --> l = t ;

}

Page 34: Digitales Suchen / Digitale Suchbäume

G.Heyer Algorithmen und Datenstrukturen II34

Bei diesem Programm wird vorausgesetzt, dass head mit dem

Schlüssel 0, einen Bitindex maxb und beide Verkettungen als auf sich selbst zeigend initialisiert wurde.

Zuerst führt man eine Suche durch, um den Schlüssel zu finden, der von v unterschieden werden muss. Die Bedingungen x --> b <= i und p --> b <= x --> b charakterisieren die Situationen, die in den vorangegangenen Abbildungen dargestellt wurden.

Danach bestimmt man die am weitesten links befindlichen Bitpositionen, in der sich die Schlüssel unterscheiden, bewegt man sich im Baum abwärts bis zu dem betreffenden Punkt und fügen an dieser Stelle einen neuen Knoten ein, der v enthält.

Page 35: Digitales Suchen / Digitale Suchbäume

G.Heyer Algorithmen und Datenstrukturen II35

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.

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.

Page 36: Digitales Suchen / Digitale Suchbäume

G.Heyer Algorithmen und Datenstrukturen II36

Patricia würde mit einer Schlüsselmenge der Art001 0001 00001 000001 usw.

Probleme haben, doch für normale Schlüssel dürfte der Baum relativ gut ausgeglichen sein, so dass 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: 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.

Das nützlichste Merkmal der Suche mit digitalen Tries besteht darin, dass sie bei Schlüsseln mit variabler Länge effizient ausgeführt werden kann.

Page 37: Digitales Suchen / Digitale Suchbäume

G.Heyer Algorithmen und Datenstrukturen II37

Bei allen anderen Suchmethoden ist die Länge der Schlüsselin irgendeiner Weise in die Suchprozedur „eingebaut“, so dass

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. Nimmt man z. B. an, dass man einen Computer hat, der effizient auf aus 8 Bits bestehenden „Bytes“ von Daten zugreifen kann, und dass man unter Hunderten von aus 1000 Bits bestehenden Schlüsseln zu suchen hat. 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 Suchen mit digitalen Tries mit beseitigten Einweg-Verzweigungen) zur bevorzugten Suchmethode, wenn sehr lange Schlüssel auftreten.


Recommended