Referat Suchalgorithmen

Suchalgorithmen

1. Definition von 'Suchen'

Suchen ist das Wiederauffinden eines bestimmten Elements oder bestimmter Informationsteile aus einer großen Menge früher gespeicherter Informationen. Normalerweise stellen wir uns die Information 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 übereinstimmt. Der Zweck des Suchens besteht darin, den Zugriff auf die Information im Datensatz (nicht nur auf die Schlüssel) für die Verarbeitung zu ermöglichen.

2. Sequentielle Suche

Anwendung: unsortierte Arrays und Listen, sequentielle Dateien

Die sequentielle Suche ist die einfachste Methode des Suchens. Dabei werden, zB die Datensätze hintereinander in einem Array gespeichert. Ein neuer Datensatz wird einfach ans Ende des Arrays hinzugefügt. Es ist egal, ob das Array sortiert ist oder nicht. Wenn ein Element gesucht werden soll, wird das Array sequentiell durchgelesen, solange bis der gesuchte Datensatz gefunden wird. Die sequentielle Suche benötigt immer n+1 Vergleiche für ein erfolglose Suche und durchschnittlich n/2 Vergleiche für eine erfolgreiche Suche.

Bei der Suche in Dateien ist die sequentielle Suche wichtig, denn nur diese kann angewendet werden, weil Dateien sequentiell gespeichert werden.

n Anzahl der Elemente im Array

Vorteil: Einfach zur programmieren

Nachteil: Nur für sehr kleine Tabellen

3. Binäres Suchen

Anwendung: sortierte Arrays und sortierte Dateien mit Direktzugriff

Auch bei der binären Suche werden die Datensätze in einem Array gespeichert, allerdings sortiert. Um festzustellen ob ein Schlüssel in dem Array vorhanden ist, wird zuerst das Element auf der mittleren Position mit ihm verglichen. Wenn der Schlüssel größer ist, muß sich das gesuchte Element in der ersten Hälfte des Arrays befinden, wenn er kleiner ist in der zweiten Hälfte und wenn er gleich ist, hat man das gesuchte Element gefunden. Ist das Element nicht das mittlere, dann wird das Array geteilt, und der ganze Vorgang wiederholt, bis man das Element gefunden hat.

Um das mittlere Element zu finden, bedient man sich folgender Formel: x = (l + r) / 2

l kleinster Index im Intervall des Arrays

r größter Index im Intervall des Arrays

Beispiel:

Inhalt des Arrays: A A A C E E E G H I L M N P R S X

Gesuchtes Element: M

A A A C E E E G H I L M N P R S X l: 1 r:17 x: 9

I L M N P R S X l:10 r:17 x:14(,5)

I L M l:10 r:12 x:11

M l:12 r:12 x:12

Die binäre Suche erfordert für eine erfolgreiche als auch für eine erfolglose Suche niemals mehr als

ld (n + 1) Vergleiche.

Algorithmus:

int binsearch (int v) // v Suchschlüssel

return -1;

Eine mögliche Verbesserung bei der binären Suche besteht in dem Versuch, genauer zu erraten, wo sich der gesuchte Schlüssel innerhalb des aktuell interessanten Intervalls befinden könnte (anstatt bei jedem Schritt blindlings das mittlere Element zu verwenden). Dies erinnert an die Art und Weise, wie man eine Nummer aus einem Telefonverzeichnis sucht: Falls der gesuchte Name mit B beginnt, schlägt man weiter vorne nach, falls er dagegen mit Y beginnt, such man näher beim Ende. Diese Methode nennt sich Interpolationssuche. Dabei müssen die Schlüssel auf Zahlenwerte abgebildet werden

Vorteil: Schneller als sequentielle Suche

Nachteil: Nur geeignet bei statistischen Datensätzen, d.h. es wird selten etwas hinzugefügt oder gelöscht.

Suchen auf peripheren Speicher

4.1 Indexsequentielle Datei

Besteht im Prinzip aus 2 Dateien. In einer stehen die Daten und in der 2. die Indizes über die man mittels einer Adresse direkt auf die Daten der 1. Datei zugreift. Das Hinzufügen von Daten ist aufwendig, da dann in den Index ein Indexsatz eingefügt werden muß.

4.2 Suche im B-Baum

Beginnend mit der Wurzel wird jeweils ein Knoten vom peripheren Speicher geladen und durchsucht. Entweder man findet den Datensatz, oder man erhält die Adresse der Seite, in dem die Wurzel des Teilbaumes liegt, in dem sich der Datensatz befindet. Diese Seite lädt man in den Hauptspeicher, durchsucht sie, und so weiter. Falls das Suchen in einem Blatt erfolglos ist, dann ist der Datensatz nicht vorhanden.

Hashing

Prinzip:

-) Ein Feld mit direktem Zugriff dient zum Speichern der Daten.

-) Beim Speichern oder Lesen eines Datenelementes wird mittels einer Hashfunktion die Adresse des Elements berechnet und über diese direkt zugegriffen.

-) Gibt es für verschiedene Schlüssel die gleiche Adresse, so muß eine geeignete Kollisionsstrategie eine neue Adresse berechnet werden.

Vorteil: Sehr schnelles Suche möglich. Bei optimaler Hashfunktion und Kollisionsstrategie wird mit 1,5 - 3 Zugriffen ein Datenfeld gefunden, unabhängig der Anzahl der Elemente.

Nachteil: Kein sortierter Zugriff

Probierende Suchverfahren

Es gibt Probleme, für die es kein geradliniges Lösungsverfahren gibt. So läßt sich zB kein Algorithmus und keine Formel finden, mit deren Hilfe man Schach spielen und gewinnen könnte. Es wird also ein andrer Lösungsweg gesucht -> Ausprobieren.

Tiefensuche (depth-first-search)

Bei der Tiefensuche wird ein Baum in die Tiefe gehend durchsucht. Das heiß, der Algorithmus untersucht zuerst einen Teilast bis zum Ende. Ist das Ziel nicht erreicht, erfolgt ein Rückziehen zum letzten besuchten Knoten, und der nächste von dort abzweigende Teilast wird untersucht.

Breitensuche (breadth-first-search)

Es werden zuerst alle Knoten der Rekursionstiefe 1 (Startknoten) überprüft, danach alle Knoten der Tiefe 2, dann Tiefe 3,

Bestensuche

Die Bestensuche ist ein Spezialfall der Breitensuche. Bei ihr wird zuerst immer der Weg untersucht, der die geringsten 'Kosten' verursacht; bei Labyrinthen ist das der jeweils kürzeste Weg. Die Bestensuche findet so immer eine optimalen Weg.

Bergsteigen (hill-climbing)

Das Bergsteigen kann angewandt werden, wenn es sich um ein Problem handelt, bei dem man einem Knoten eine Bewertung zuordnen kann, bei Labyrinthen etwa die Luftlinienentfernung zum Ziel. Es beruht auf dem Prinzip, daß jeder Knoten eine bestimmte Wertigkeit hat und man immer den Knoten mit der höchsten Wertigkeit als ersten aufruft, danach den mit der zweithöchsten Wertigkeit,

Graphsuch-Algorithmen (graph-search)

Graphsuch-Algorithmen sind eine Verbesserung von Tiefensuche und Breitensuche. Diese Algorithmen haben den Vorteil, daß sie Wege, die einmal ausprobiert wurden und nicht zum Ziel geführt haben, nicht vergessen werden.

Heuristische Suchverfahren

Heuristisches Suchen grenzt das sogenannte uninformative Suchen von anderen Suchmethoden ab. Uninformiert soll hier bedeuten, daß dem Algorithmus keine Angaben über die Lage des Zielknotens vorliegen und somit nicht direkt in Richtung Ziel gegangen werden kann. Heuristische Verfahren arbeiten häufig mit Schätzfunktionen. Dadurch ähneln sie in ihrem Ablauf, der Art und Weise, in der auch ein Mensch beim Problemlösen vorgeht. Heuristische Verfahren setzen voraus, daß die Knoten eines Baumes bewertet werden können.

Versuch/Irrtum (Backtracking)

Ahnlich dem heuristischen Suchverfahren. Beim Durchsuchen des Baumes muß man in einer bestimmten Reihenfolge vergehen. Zuerst probiert man es rechts. Sollte dieser Weg fehlschlagen, so versucht man es links. Ist dieser Weg auch nicht erfolgreich, so geht man so lange rückwärts, bis man zur letzten Abzweigung kommt. Dieser Vorgang heißt Backtracking.

Textsuche

Brute Force

Dieser Suchalgorithmus durchsucht einen Text nach einem Muster. Dabei vergleicht er die aktuelle Stelle des Musters mit der aktuellen Stelle im Text. Tritt ein ,Mismatch' auf wird das Muster um eine Stelle verschoben und neu verglichen, sonst wird die aktuelle Stelle des Musters und des Textes um eine Stelle erhöht und weiter verglichen. Selbst wenn das Muster nahezu komplett durchsucht wurde und erst zum Schluß ein ,Mismatch' auftaucht wird das Muster nur um eine Stelle verschoben.

Algorithmus:

int search (char *p, char *a) // p Suchmuster

if (j == m) return i-m;

else return i;

Durch dieses Verfahren kommt es zu vielen doppelten Vergleichen.

Suchaufwand: maximal: n * m

n Länge des Musters

m Länge des Textes

Knuth-Morris-Pratt (KMP)

Der Algorithmus von KMP stellt eine wesentliche Verbesserung gegenüber dem Brute-Force-Algorithmus dar. Diese Verbesserung wird durch eine Vorverarbeitung des Musters erreicht. In dieser Vorverarbeitung wird ermittelt, ab welcher Stelle des Textes frühestens ein nächster Vergleich des gesamten Musters beginnen kann. Es wird ein Array verwendet, um zu bestimmen, an welcher Stelle im Muster zurückzukehren ist, wenn eine Nichtübereinstimmung festgestellt wurde.

Es sind niemals mehr als n + m Zeichenvergleiche notwendig.

Boyer-Moore

Im Gegensatz zu den vorherigen Algorithmen wird das Muster nicht von links nach rechts mit dem Text verglichen, sondern umgekehrt. Der Vergleich beginnt also immer an der letzten Stelle im Muster. Tritt eine Nichtübereinstimmung auf, wird die Distanz berechnet, um die das Muster verschoben wird, bevor ein erneuter Vergleich ausgefü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. Darüber hinaus spielt es eine Rolle, ob und an welcher Position das Zeichen im Muster auftaucht. Dies führt dazu, daß man für jedes Zeichen des Alphabets einen Eintrag in einem Array reserviert, der die Größe der möglichen Verschiebungen nach rechts angibt, wenn das Zeichen eine Nichtübereinstimmung verursacht. Das Array wird mit delta bezeichnet und enthält für jedes Element, das nicht im Muster verkommt m und ansonsten den Abstand des rechtesten Vorkommens des Zeichens bis zum Musterende.

Der Algorithmus von Boyer-Moore kann im ungünstigsten Fall n * m Schritte benötigen. Im Idealfall hingegen nur n / m Schritte.

Algorithmus:

// Berechnung von delta

for (c = ´A´; c <= ´Z´; c++)

delta[c] = 0;

for (i = 1;i <= m; i++)

delta[muster[i] = i; // muster gesuchter Text

// Simple Boyer-Moore

i = 1;

while (i <= n-m+1)

return FALSE;

Beispiel:

Text in dem gesucht wird: 'EINMAL IST KEINMAL ABER ZWEIMAL IST EINMAL ZUVIEL'

Gesuchtes Wort: 'ZWEIMAL'

Berechnen des Arrays delta:

L 0

A 1

M 2

I 3

E 4

W 5

Z 6

sonst 7

Vor: Nach Nichtübereinstimmung:

1: i= 7, j=7 i= 7, j=7, delta[ ]=7

2: i=14, j=7 i=14, j=7, delta[I]=3

3: i=17, j=7 i=17, j=7, delta[A]=1

4: i=18, j=7 i=15, j=4, delta[N]=7

5: i=22, j=7 i=22, j=7, delta[E]=4

6: i=26, j=7 i=26, j=7, delta[W]=5

7: i=31, j=7 gefunden !!!