Twitter und Facebook-Anbindung
X
Tweet Follow @twitterapi
!!! Anbindung an twitter und facebook öffnen !!!

Wenn Ihnen mein Online-Buch gefällt,
dann bedanken Sie sich doch mit einer kleinen Spende...

38 Die geläufigsten Suchverfahren

38 Die geläufigsten Suchverfahren

Eine weitere seht häufige auftretende Thematik in der Informatik, ist das Auffinden von Elementen in einem Array oder einer Listen. Auch hierfür gibt es wieder verschiedenste Ansatzmöglichkeiten, welche ich aber nur theoretisch anschneiden werde, damit Sie auch davon mal etwas gehört haben. Eine schnelle Suche setzt allerdings immer eine Vorsortierung der Liste voraus. Wie man dafür sogt, habe ich Ihnen ja im letzten Kapitel gelzeit.

Zum Seitenanfang
Zum Inhaltsverzeichnis

38.1 Einfache lineare Suche

38.1 Einfache lineare Suche

Der trivialste Fall um ein Element zu finden, ist die gesamte Liste, Schritt für Schritt, durchzulaufen, bis man das gewünschte Element gefunden hat. Dies nennt man lineare Suche und wie Sie sich schon denken können, hat jene eine Laufzeit von n, da man im schlimmsten Fall, jedes Element besuchen muss.

Lineare Suchen machen nur dann Sinn, wenn man unsortierte Listen hat, weil der Sortieraufwand zum einen teurer wäre (angenommen ich will nur einmalig was suchen) oder weil man überhaupt kein Kriterium für die Sortierung hat (angenommen man hat eine Liste mit verschiedenen Objekten, die nichts gemeinsam haben, nur gemeinsam verwaltet werden, wie z.B. alle Steuerelemente eines Fensters, also Eingabefelder, Buttons usw. - nach was soll man jene sinnvoll sortieren?) oder weil man die Elemente nicht sortieren darf um die Semantik nicht zu verletzen (es wäre unklug einen Text zu sortieren um ein Wort zu finden). Sobald man aber die Liste sortieren kann und mehrfach Elemente sucht, rechnet sich irgendwann die einmalige Vorsortierung.

Zum Seitenanfang
Zum Inhaltsverzeichnis

38.4 Interpolierende Suche

38.4 Interpolierende Suche

Dieses Verfahren versucht nun folgende Problematik zu umgehen. Angenommen Sie suchen in New York, eine Person mit dem Nachnamen "Zwicker" im Telefonbuch. Nach dem Intervallhalbierungsverfahren, müssten Sie das Buch in der Mitte aufschlagen, dann vom Rest noch einmal die Hälfte und so weiter und so weiter. Somit brauchen Sie trotzdem relativ lange, um ein Element am Ende einer Liste zu finden. Wenn man sich aber selber mal beobachtet, dann sucht man in einem Telefonbuch anders. Man schlägt gleich den Teil auf, in welchem Namen mit Z stehen und dann sucht man nach "Zw", was erheblich schneller geht. Genau dies wird durch dieses Verfahren annähernd realisiert. Bei der Interpolation wird quasi eine bessere "Mitte" geschätzt, so dass man die Liste nicht teilt, sondern drittelt, viertelt oder sogar in einen noch kleineren Bereich teilt.

Dummerweise funktioniert dieses Verfahren aber nicht bei Texten, sondern nur bei Zahlen und dann auch nur, wenn die Zahlen verhältnismäßig gleich verteilt sind. Der Grund ist folgender. Es wird vom ersten und letzten Element der Betrag gebildet und die Länge des Bereiches ermittelt. Anschließend wird eine Art Prozentwert für das zu suchende Element gebildet, welcher der tatsächlichen Position entspricht oder ihr sehr nahe kommt. Stimmt die Position noch nicht, wird der Bereich verkleinert und der Spaß beginnt von vorne. Folgende Grafik wird dies an einem konkreten Beispiel demonstrieren.

Veranschaulichung der interpolierenden Suche

In diesem Beispiel wird das zu suchende Element, bereits im ersten Durchlauf gefunden. Wäre dies nicht der Fall, würde geprüft werden, ob die neue Mitte kleiner oder größer ist, als das zu suchende Element. In dem Fall das es größer ist, wird die linke Grenze auf Mittelwert plus eins gesetzt und im Fall das es kleiner ist, wird die rechte Grenze auf Mittelwert minus eins gesetzt. Entspricht die linke und die rechte Grenze nicht dem gesuchten Wert, wird wieder die Formel angewandt.

Zum Seitenanfang
Zum Inhaltsverzeichnis

38.2 Verbesserte lineare Suche

38.2 Verbesserte lineare Suche

Gerade dann, wenn es sich um Texte handelt, die man nicht sortieren darf, braucht man eine schnellere Möglichkeit, als das Suchwort an den Anfang des Textes anzulegen und dann immer Zeichenweise weiter zu verschiebt, um dann immer die Komplette Zeichenkette zu vergleichen. Gerade bei sehr sehr langen Texten und langen Suchwörtern, würde dies extrem lange dauern. Deswegen möchte ich Ihnen hier den Boyer-Moore-Algorithmus vorstellen, welcher sehr viel schneller das gesuchte Wort findet.

Die Grundidee ist, dass man am Anfang, das zu suchende Wort an den Text anlegt und den letzten Buchstaben mit dem Buchstaben vergleicht, der im Text an dieser Stelle steht. Wenn es eine Übereinstimmung gibt, wird der Buchstabe davor verglichen und wenn es wieder eine Übereinstimmung gibt, wird der Buchstabe davor betrachtet. Wenn alle Buchstaben übereinstimmen ist die Position gefunden. Sobald der Vergleich fehlschlägt, wird geprüft, ob der Buchstabe des Textes im Suchwort vorkommt. Ist dies nicht der Fall, wird das Suchwort um seine Länge verschoben und der Algorithmus beginnt von vorne. Ist der Buchstabe im Suchwort enthalten, wird die Differenz aus der Position des hintersten vorkommenden Buchstabe (vor dem Bereich in welchem es Übereinstimmungen zum Text gab) mit der Position der letzten Übereinstimmung ermittelt und das Suchwort um diese Anzahl verschoben. Da dies jetzt sehr theoretisch klingt, werde ich dies an einem kleinen Beispiel zeigen.

Veranschaulichung des Boyer-Moor-Algorithmus

Im Ersten Schritt wird also das a aus dem Text, mit dem a aus dem Suchwort verglichen und eine Übereinstimmung festgestellt. Dies hat zur Folge, dass das l mit dem r verglichen wird und da sich diese zwei Buchstaben unterscheiden, wird jetzt nach dem hintersten l im Suchwort, vor "ra", linear gesucht. Zwei Positionen weiter vorne, wird jetzt ein l gefunden und somit wird das Suchwort um zwei verschoben.

Im nächsten Schritt wird jetzt das i aus dem Text, mit dem a aus dem Suchwort verglichen. Da es nicht übereinstimmt und das i nicht im Suchwort vorkommt, wird das Suchwort um seine gesamte Länge verschoben.

Der Rest sollte jetzt klar sein und wie Sie sehen, benötigt man weniger Schritte, als würde man das Wort immer Zeichen für Zeichen verschieben und alles Prüfen.

Zum Seitenanfang
Zum Inhaltsverzeichnis

38.3 Logarithmische Intervallhalbierungsverfahren

38.3 Logarithmische Intervallhalbierungsverfahren

Dieses Verfahren sollte Ihnen vieleicht noch aus dem Mathematikunterricht, unter dem Namen "Newtonsches Intervallhalbierungsverfahren", kennen. Es wird In einer sortierten Liste das mittlere Element benommen und mit dem gesuchten verglichen. Ist das gesuchte Element größer, dann wird aus dem hinteren Teil das mittlere Element genommen und mit dem zu suchenden Verglichen. Somit bewegt man sich in dieser Liste, ähnlich wie in einem Binärbaum und somit ist die Suchdauer nur von der Höhe abhängig, also in logarithmischer Zeit zu bewältigen.

Veranschaulichung des Intervallhalbierungsverfahrens

Zum Seitenanfang
Zum Inhaltsverzeichnis

© Copyright by Thomas Weiß, 2009 - 2012