Robert Sedgewick: Algorithmen

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


17. Digitales Suchen



Digitales Mehrwege-Suchen

Beim digitalen Sortieren stellten wir fest, daß wir eine beträchtliche Erhöhung der Geschwindigkeit erzielen können, wenn wir jedesmal mehr als ein Bit betrachten. Dies gilt auch für die digitale Suche: Indem wir jedesmal m Bits betrachten, können wir die Suche um den Faktor 2m beschleunigen. 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, daß die gleichzeitige Betrachtung von m Bits der Verwendung von Knoten mit M = 2m Verkettungen in einem Baum entspricht, was zu einer beträchtlichen Menge von vergeudetem Platz für nicht benutzte Verkettungen führen kann.

Wenn zum Beispiel M = 4 ist, wird für unsere Beispielschlüssel der in Abbildung 17.7 dargestellte Trie erzeugt. Um in diesem Trie zu suchen, betrachte man jeweils zwei Bits im Schlüssel auf einmal: Falls die ersten beiden Bits 00 sind, nehme man beim ersten Knoten die linke Verkettung; wenn sie 01 sind, nehme man die zweite Verkettung; wenn sie 10 sind, nehme man die dritte Verkettung; wenn sie 11 sind, nehme man die rechte Verkettung. Danach verzweige man auf der nächsten Ebene entsprechend dem dritten und vierten Bit usw. Um zum Beispiel in dem Trie in Abbildung 17.7 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 daß 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.

Abbildung 17.7
Abbildung 17.7 Ein digitaler 4-Wege-Trie.

Man erkennt, daß 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, daß 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 logMN. Ein sinnvoller Kompromiß 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 (zum Beispiel 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, da dann wahrscheinlich (nur) wenige Schlüssel pro Kategorie vorhanden sind. Andererseits wäre ein kleineres M für Dateien geeignet, die nur Hunderte von Schlüsseln enthalten, da sonst die meisten Kategorien leer wären und zu viel Platz vergeudet würde. Ein noch größeres M wäre für Dateien mit Millionen von Schlüsseln geeignet, da sonst die meisten Kategorien zu viele Schlüssel haben würden und zu viel Zeit vergeudet würde.

Interessant ist, daß »Hybrid«-Suchmethoden der Art und Weise entsprechen, wie Menschen nach Dingen suchen, zum Beispiel Namen in einem Telefonbuch. Der erste Schritt ist eine Mehrwege-Entscheidung (»Sehen wir nach, das Wort beginnt mit 'A'«), der vielleicht einige Zweiweg-Entscheidungen folgen (»Es kommt vor 'Andrews', doch nach 'Aitken'«), wonach sequentielles Suchen erfolgt (»'Algonquin' ...'Algren' ...Nein, 'Algorithms' steht nicht drin!«). Natürlich dürften Computer eine Mehrwege-Suche um einiges besser als Menschen ausführen, so daß 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 (zum Beispiel in einem Wörterbuch).

Im nächsten Kapitel betrachten wir einen systematischen Weg zur Anpassung der Struktur mit dem Ziel, die Vorzüge des digitalen Mehrwege-Suchens für beliebige Dateigrößen zu nutzen.


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