Suchalgorithmen

Suchen ist das Wiederauffinden eines bestimmten Elementes 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 beum Suchen hat. Das Ziel des Suchens ist es, alle Datensätze zu finden, deren Schlüssel mit einem bestimmten Suchschlüssel übereinstimmen.

Die Anwendungen des Suchens sind vielfältig und erfordern eine große Zahl unterschiedlicher Operationen.

Beim Suchen gibt es (wie beim Sortieren) Programme, die weit verbreitet sind und häufig benutzt werden.

1. Sequentielle Suche:

Die sequentielle Suche ist die einfachste Methode des Suchens. Hier werden die Datensätze hintereinander in einem Array gespeichert. Es ist egal, ob das Array sortiert ist oder nicht. Wenn eine Suche ausgeführt werden soll, wird das Array solange sequentiell durchgelesen, bis das gesuchte Element gefunden wird.

Die sequentielle Suche benötigt immer

n + 1 Vergleiche für eine erfolglose Suche

n/2 Vergleiche für eine erfolgreiche Suche

n .. Anzahl der Elemente im Array

Anwendung: Suche in Arrays, Listen und sequentiellen Dateien

2. Binäre Suche:

Bei der binären Suche werden die Datensätze sortiert in einem Array gespeichert.

Um festzustellen, ob ein gegebener Schlüssel k im Array enthalten ist, vergleicht man ihn zuerst mit dem mittleren Element des Arrays. Wenn k kleiner ist, muss sich das gesuchte Element in der ersten Hälfte des Arrays befinden, wenn k größer ist, muss sich das Element in der zweiten Hälfte des Array befinden.

Danach wird wieder das mittlere Element ermittelt und mit dem Suchbegriff verglichen (Rekursion). Dieser Vorgang wird solange wiederholt, bis man das Element gefunden hat.

Mittleres Element:      (kleinster Index im Intervall + größter Index im Intervall) / 2

Die binäre Suche erfordert (sowohl für erfolgreiche als auch erfolglose Suche) niemals mehr als

ld (n + 1) Vergleiche.

Anwendung: sortierte Arrays und sortierte Dateien

Beispiel:

Gesuchtes Element: M

Eine mögliche Verbesserung bei der binären Suche besteht in dem Versuch, genauer zu erraten, wo sich der gesuchte Schlüssel innerhalb des aktuellen interessierenden Intervalle befinden könnte. Dies ist ähnlich der Art und Weise, wie man eine Nummer in einem Telefonbuch sucht: Falls der Name mit B beginnt, schlägt man weiter vorn nach, falls er aber mit Y beginnt sucht man weiter hinten. Diese Methode nennt man Interpolationsuche.

Beispiel:

3. Hashing:

Hashing bedeutet Zerhacken. Dabei handelt es sich um eine Methode für die direkte Bezugnahme auf Datensätze in einer Tabelle durch Ausführung arithmetischer Transformationen, die Schlüssel in Tabellenadressen umwandeln. Wenn wir wissen, dass die Schlüssel unterschiedliche ganze Zahlen von 1 bis n sind, können wir den Datensatz mit dem Schlüssel i in der Tabellenposition i speichern, bereit für den unmittelbaren Zugriff mit Hilfe des Schlüsselwertes. Hashing ist eine Verallgemeinerung dieser einfachen Methode für typische Suchanwendungen, wenn wir solche speziellen Kenntnisse über die Schlüsselwerte nicht haben.

4. Externes Suchen:

Indexsequentieller Zugriff:

Die Datensätze werden entsprechend der wachsenden Reihenfolge ihrer Schlüssel gespeichert, und Suchvorgänge werden einfach realisiert, indem die Datensätze der Reihe nach so lange eingelesen werden, bis ein Datensatz gefunden wird, der einen Schlüssel enthält, der größer oder gleich dem Suchschlüssel ist.

5. Volltextsuche (Suchen in einer Zeichenfolge):

Eine grundlegende Operation mit Zeichenfolgen ist das pattern matching (Musteranpassung): Es ist eine Zeichenfolge der Länge n und ein Muster der m gegeben; zu suchen ist das Auftreten des Musters innerhalb des Textes.

Brute-Force-Algorithmus:

Die offensichtliche Methode für das Pattern Matching, an die man sofort denkt, besteht darin, für jede mögliche Position im Text, an der das Muster passen könnte, zu prüfen, ob es tatsächlich paßt.

int brutesearch (char *p, char *a)

return j == m ? i - m : -1

Laufzeitverhalten:

Im ungünstigsten Fall können ca. n*m Vergleiche erforderlich werden

Bei normalen Texten proportional zu n + m

Knuth-Morris-Pratt (KMP) Algorithmus:

Die Idee, die dem von Knuth Morris und Pratt entdeckten Algorithmus zugrunde liegt, ist die folgende: Die "Kenntnis" der bereits durchsuchten Zeichenfolge soll so genutzt werden, dass bei einer Nichtübereinstimmung die Startposition im Text (für den nächsten Suchschritt) nicht nur um 1 erhöht wird.

Indealfall: 1. Zeichen im Muster kommt im Rest des Musters nicht mehr vor, d. h. i muß überhaupt nicht zurückgesetzt werden.

Beispiel:

Suche Abcdxyz in Abcd12AbcdxyAbcdxyz

Im Realfall muß man aber berücksichtigen, dass der "Anfang" des Suchmusters am "Ende" der bisher durchsuchten Folge vorkommt.

Beispiel:

Suche AbcAbcX in AbcAbcAbAbcAbcX

int kmpsearch (char *p, char * a)

Um wieviel man die "Startposition" im Text für den nächsten Suchschritt erhöhen darf, wird mit der sogenannten next-Tabelle bestimmt. Die Werte der Tabelle können in einem Verarbeitungsschritt vor dem eigentlichen Suchen, nur aufgrund des Suchmusters, bestimmt werden.

Initnext (char *p)

Werte der next-Tabelle für das obige Beispiel:

Im ungünstigsten Fall werden für den KMP-Algorithmus n + m Vergleiche benötigt.

Boyer-Moore Algorithmus:

Bei diesem Algorithmus wird das Muster von rechts nach links durchgelesen (bei den vorigen Algorithmen immer von links nach rechts). Der Vergleich beginnt also immer an der letzten Stelle im Muster. Bei einer Nichtübereinstimmung wird die Distanz, um die das Muster verschoben wird, berechnet bevor der nächste Vergleich durchgeführt wird.

Die Berechnungen für die Verschiebung des Musters sind nur von dem Zeichen im Text abhängig das die Nichtübereinstimmung verursacht hat. Es spielt auch eine Rolle, ob und an welcher Position das Zeichen im Muster auftritt. Es wird für jedes Zeichen im Alphabet, ein Eintrag in einem Array gemacht, der angibt, wie weit zu springen ist, wenn dieses Zeichen im Text auftritt und eine Nichtübereinstimmung während der Suche verursacht.

Im Idealfall benötigt der Algorithmus nur n/m Schritte, im ungünstigsten Fall jedoch n + m Schritte.

Int bmsearch (char *p, char *a)

return i;

Beispiel:

Gesuchtes Wort: ZWEIMAL

Berechnung des Arrays:

EINMAL IST KEINMAL ABER ZWEIMAL

ZWEIMAL

ZWEIMAL

ZWEIMAL

ZWEIMAL

ZWEIMAL

ZWEIMAL

ZWEIMAL