Robert Sedgewick: Algorithmen

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


14. Elementare Suchmethoden



Eine grundlegende Operation, die Bestandteil sehr vieler Berechnungsaufgaben ist, ist das Suchen: Das Wiederauffinden eines bestimmten Elements oder bestimmter Informationsteile aus einer großen Menge früher gespeicherter Informationen. Normalerweise stellen wir uns die Information als in Datensätze zerlegt vor, wobei jeder Datensatz einen Schlüssel zur Verwendung beim Suchen hat. Das Ziel des Suchens ist es,
alle Datensätze zu finden, deren Schlüssel mit einem bestimmten Suchschlüssel übereinstimmen. Der Zweck des Suchens besteht gewöhnlich darin, den Zugriff auf die Information im Datensatz (nicht nur auf die Schlüssel) für die Verarbeitung zu ermöglichen.

Die Anwendungen des Suchens sind vielfältig und erfordern eine große Zahl unterschiedlicher Operationen. Beispielsweise muß eine Bank die Kontenbewegungen aller ihrer Kunden verfolgen und sie durchsuchen, um verschiedene Arten von Transaktionen zu prüfen. Ein Reservierungssystem einer Luftverkehrsgesellschaft hat in gewisser Hinsicht ähnliche Aufgaben zu erfüllen, doch sind die meisten dort Daten recht kurzlebig.

Zwei gebräuchliche Begriffe, die zur Beschreibung von Datenstrukturen für das Suchen oft benutzt werden, sind Wörterbücher und Symboltabellen. Zum Beispiel sind in einem Wörterbuch der deutschen Sprache die »Schlüssel« die Wörter, und die »Datensätze« sind die zu den Wörtern gehörenden Eintragungen, die die Definition, Aussprache und sonstigen Informationen enthalten. Man kann sich auf das Erlernen und Beurteilen von Suchmethoden vorbereiten, indem man überlegt, wie man ein System zum Suchen in einem Wörterbuch der deutschen Sprache implementieren würde. Eine Symboltabelle ist das Wörterbuch für ein Programm: Die »Schlüssel« sind die symbolischen Namen, die im Programm verwendet werden, und die »Datensätze« enthalten Informationen, die das bezeichnete Objekt beschreiben.

Beim Suchen gibt es (wie beim Sortieren) Programme, die weit verbreitet sind und häufig benutzt werden, so daß es sich lohnt, eine Reihe von Methoden etwas gründlicher zu untersuchen. Wie beim Sortieren beginnen wir damit, einige elementare Methoden zu betrachten, die für kleine Tabellen und in anderen speziellen Situationen sehr nützlich sind und grundlegende Techniken illustrieren, die in höherentwickelten Methoden genutzt werden. Wir betrachten Verfahren, die Datensätze in Feldern speichern, die entweder mit Schlüsselvergleichen durchsucht oder mit Hilfe des Schlüsselwertes indiziert werden, und wir betrachten eine grundlegende Methode, mit der Strukturen aufgebaut werden, die durch die Werte der Schlüssel definiert sind.

Wie im Falle der Prioritätswarteschlangen ist es am besten, sich Suchalgorithmen als zu Paketen gehörig vorzustellen, mit denen eine Anzahl typischer Operationen implementiert wird und die von speziellen Implementationen getrennt werden können, so daß alternative Implementationen leicht ausgetauscht werden können. Zu den uns interessierenden Operationen gehören:

Wie bei den Prioritätswarteschlangen ist es manchmal zweckmäßig, einige dieser Operationen zu kombinieren. Zum Beispiel wird aus Effizienzgründen oft eine Operation search and insert eingeführt, wenn Datensätze mit gleichen Schlüsseln in der Datenstruktur nicht aufbewahrt werden sollen. Wenn festgestellt wurde, daß ein Schlüssel in der Datenstruktur nicht auftritt, enthält der interne Zustand vieler Methoden bereits alle Informationen, die notwendig sind, um einen neuen Datensatz mit dem vorgegebenen Schlüssel einzufügen.

Datensätze mit gleichen Schlüsseln können je nach Anwendung auf unterschiedliche Weise behandelt werden. Einmal können wir darauf bestehen, daß die primäre Datenstruktur für das Suchen nur Datensätze mit unterschiedlichen Schlüsseln enthält. Dann könnte jeder »Datensatz« in dieser Datenstruktur zum Beispiel eine Verkettung zu einer Liste aller Datensätze enthalten, die diesen Schlüssel besitzen. Dies ist die zweckmäßigste Anordnung vom Standpunkt des Entwicklers von Suchalgorithmen aus, und sie ist für einige Anwendungen zweckmäßig, da alle Datensätze mit einem gegebenen Suchschlüssel bei einem Suchvorgang zurückgegeben werden. Die zweite Möglichkeit besteht darin, Datensätze mit gleichen Schlüsseln in der primären Datenstruktur für das Suchen zu belassen und bei einem Suchvorgang irgendeinen Datensatz mit dem gegebenen Schlüssel zurückzugeben. Dies ist einfacher für Anwendungen, bei denen die Datensätze einer nach dem anderen verarbeitet werden und die Reihenfolge, in der Datensätze mit gleichen Schlüsseln verarbeitet werden, unwesentlich ist. Es ist schwieriger, was die Entwicklung von Algorithmen betrifft, da außerdem noch ein Mechanismus für das Wiederauffinden aller Datensätze mit einem gegebenen Schlüssel vorgesehen werden muß. Eine dritte Möglichkeit besteht darin anzunehmen, daß jeder Datensatz (neben dem Schlüssel) eine eindeutige Kennzeichnung besitzt, und zu fordern, daß ein Suchvorgang den Datensatz mit einem gegebenen Kennzeichen findet, wenn der Schlüssel gegeben ist. Oder es könnte ein noch komplizierterer Mechanismus erforderlich sein.

Jede der oben aufgezählten grundlegenden Operationen hat wichtige Anwendungen, und es wurde eine recht große Zahl von grundlegenden Organisationsformen vorgeschlagen, um die effiziente Anwendung verschiedener Kombinationen dieser Operationen zu unterstützen. In diesem und den nächsten Kapiteln konzentrieren wir uns auf Implementationen der grundlegenden Funktionen search und insert (und natürlich initialize), mit einigen Bemerkungen zu delete und sort an geeigneter Stelle. Wie im Falle der Prioritätswarteschlangen erfordert die Operation join normalerweise weiterentwickelte Techniken, die wir hier nicht betrachten können.


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