Robert Sedgewick: Algorithmen

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


17. Digitales Suchen



Verschiedene Suchverfahren laufen in der Weise ab, daß 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 (siehe
Kapitel 10) gilt, daß 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.

Die Hauptvorteile digitaler Suchverfahren sind, daß sie ohne die Komplikationen, die bei ausgeglichenen Bäumen auftreten, ein annehmbares Verhalten im ungünstigsten Fall gewährleisten, daß sie einen einfachen Weg zur Behandlung von Schlüsseln mit variabler Länge bieten, daß einige von ihnen Einsparungen von Speicherplatz ermöglichen, indem sie einen Teil des Schlüssels innerhalb der Suchstruktur speichern, und daß sie einen sehr schnellen Zugriff auf die Daten realisieren können, der sowohl mit binären Suchbäumen als auch mit Hashing vergleichbar ist. Die Nachteile sind, daß Daten mit einer gewissen Systematik zu entarteten Bäumen mit schlechtem Verhalten führen können (und Daten, die aus Zeichen bestehen, sind mit einer solchen Systematik behaftet) und daß 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; da sie digitale Eigenschaften der Schlüssel verwenden, ist es schwierig oder unmöglich, in Sprachen wie Pascal effiziente Implementationen zu erzeugen.

Wir werden eine Reihe von Methoden betrachten, wobei jede von ihnen ein Problem korrigiert, das der vorangehenden innewohnte, und wobei wir schließlich zu einem wichtigen Verfahren gelangen, das für solche Suchanwendungen sehr nützlich ist, in denen sehr lange Schlüssel auftreten. Außerdem lernen wir das Analogon zum »Sortieren in linearer Zeit« aus Kapitel 10 kennen, ein Suchen »in konstanter Zeit«, das auf dem gleichen Prinzip beruht.


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